From 4d30a1e4f1edecff86d5066ce4653a370e59e5e1 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Wed, 30 Jan 2008 08:01:00 -0800 Subject: Version abc80130 --- src/opt/lpk/lpk.h | 84 ------ src/opt/lpk/lpkAbcDec.c | 290 -------------------- src/opt/lpk/lpkAbcDsd.c | 603 ----------------------------------------- src/opt/lpk/lpkAbcMux.c | 235 ---------------- src/opt/lpk/lpkAbcUtil.c | 244 ----------------- src/opt/lpk/lpkCore.c | 659 --------------------------------------------- src/opt/lpk/lpkCut.c | 683 ----------------------------------------------- src/opt/lpk/lpkInt.h | 246 ----------------- src/opt/lpk/lpkMan.c | 122 --------- src/opt/lpk/lpkMap.c | 205 -------------- src/opt/lpk/lpkMulti.c | 495 ---------------------------------- src/opt/lpk/lpkMux.c | 247 ----------------- src/opt/lpk/lpkSets.c | 440 ------------------------------ src/opt/lpk/lpk_.c | 48 ---- src/opt/lpk/module.make | 11 - 15 files changed, 4612 deletions(-) delete mode 100644 src/opt/lpk/lpk.h delete mode 100644 src/opt/lpk/lpkAbcDec.c delete mode 100644 src/opt/lpk/lpkAbcDsd.c delete mode 100644 src/opt/lpk/lpkAbcMux.c delete mode 100644 src/opt/lpk/lpkAbcUtil.c delete mode 100644 src/opt/lpk/lpkCore.c delete mode 100644 src/opt/lpk/lpkCut.c delete mode 100644 src/opt/lpk/lpkInt.h delete mode 100644 src/opt/lpk/lpkMan.c delete mode 100644 src/opt/lpk/lpkMap.c delete mode 100644 src/opt/lpk/lpkMulti.c delete mode 100644 src/opt/lpk/lpkMux.c delete mode 100644 src/opt/lpk/lpkSets.c delete mode 100644 src/opt/lpk/lpk_.c delete mode 100644 src/opt/lpk/module.make (limited to 'src/opt/lpk') diff --git a/src/opt/lpk/lpk.h b/src/opt/lpk/lpk.h deleted file mode 100644 index 2a642db2..00000000 --- a/src/opt/lpk/lpk.h +++ /dev/null @@ -1,84 +0,0 @@ -/**CFile**************************************************************** - - FileName [lpk.h] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Fast Boolean matching for LUT structures.] - - Synopsis [External declarations.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - April 28, 2007.] - - Revision [$Id: lpk.h,v 1.00 2007/04/28 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#ifndef __LPK_H__ -#define __LPK_H__ - -#ifdef __cplusplus -extern "C" { -#endif - -//////////////////////////////////////////////////////////////////////// -/// INCLUDES /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// PARAMETERS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// BASIC TYPES /// -//////////////////////////////////////////////////////////////////////// - -typedef struct Lpk_Par_t_ Lpk_Par_t; -struct Lpk_Par_t_ -{ - // user-controlled parameters - int nLutsMax; // (N) the maximum number of LUTs in the structure - int nLutsOver; // (Q) the maximum number of LUTs not in the MFFC - int nVarsShared; // (S) the maximum number of shared variables (crossbars) - int nGrowthLevel; // (L) the maximum increase in the node level after resynthesis - int fSatur; // iterate till saturation - int fZeroCost; // accept zero-cost replacements - int fFirst; // use root node and first cut only - int fOldAlgo; // use old algorithm - int fVerbose; // the verbosiness flag - int fVeryVerbose; // additional verbose info printout - // internal parameters - int nLutSize; // (K) the LUT size (determined by the input network) - int nVarsMax; // (V) the largest number of variables: V = N * (K-1) + 1 -}; - -//////////////////////////////////////////////////////////////////////// -/// MACRO DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// ITERATORS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -/*=== lpkCore.c ========================================================*/ -extern int Lpk_Resynthesize( Abc_Ntk_t * pNtk, Lpk_Par_t * pPars ); - - -#ifdef __cplusplus -} -#endif - -#endif - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - diff --git a/src/opt/lpk/lpkAbcDec.c b/src/opt/lpk/lpkAbcDec.c deleted file mode 100644 index aa2d4bc0..00000000 --- a/src/opt/lpk/lpkAbcDec.c +++ /dev/null @@ -1,290 +0,0 @@ -/**CFile**************************************************************** - - FileName [lpkAbcDec.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Fast Boolean matching for LUT structures.] - - Synopsis [The new core procedure.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - April 28, 2007.] - - Revision [$Id: lpkAbcDec.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "lpkInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Implements the function.] - - Description [Returns the node implementing this function.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Abc_Obj_t * Lpk_ImplementFun( Lpk_Man_t * pMan, Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, Lpk_Fun_t * p ) -{ - extern Hop_Obj_t * Kit_TruthToHop( Hop_Man_t * pMan, unsigned * pTruth, int nVars, Vec_Int_t * vMemory ); - unsigned * pTruth; - Abc_Obj_t * pObjNew; - int i; - if ( p->fMark ) - pMan->nMuxes++; - else - pMan->nDsds++; - // create the new node - pObjNew = Abc_NtkCreateNode( pNtk ); - for ( i = 0; i < (int)p->nVars; i++ ) - Abc_ObjAddFanin( pObjNew, Abc_ObjRegular(Vec_PtrEntry(vLeaves, p->pFanins[i])) ); - Abc_ObjSetLevel( pObjNew, Abc_ObjLevelNew(pObjNew) ); - // assign the node's function - pTruth = Lpk_FunTruth(p, 0); - if ( p->nVars == 0 ) - { - pObjNew->pData = Hop_NotCond( Hop_ManConst1(pNtk->pManFunc), !(pTruth[0] & 1) ); - return pObjNew; - } - if ( p->nVars == 1 ) - { - pObjNew->pData = Hop_NotCond( Hop_ManPi(pNtk->pManFunc, 0), (pTruth[0] & 1) ); - return pObjNew; - } - // create the logic function - pObjNew->pData = Kit_TruthToHop( pNtk->pManFunc, pTruth, p->nVars, NULL ); - return pObjNew; -} - -/**Function************************************************************* - - Synopsis [Implements the function.] - - Description [Returns the node implementing this function.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Abc_Obj_t * Lpk_Implement_rec( Lpk_Man_t * pMan, Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, Lpk_Fun_t * pFun ) -{ - Abc_Obj_t * pFanin, * pRes; - int i; - // prepare the leaves of the function - for ( i = 0; i < (int)pFun->nVars; i++ ) - { - pFanin = Vec_PtrEntry( vLeaves, pFun->pFanins[i] ); - if ( !Abc_ObjIsComplement(pFanin) ) - Lpk_Implement_rec( pMan, pNtk, vLeaves, (Lpk_Fun_t *)pFanin ); - pFanin = Vec_PtrEntry( vLeaves, pFun->pFanins[i] ); - assert( Abc_ObjIsComplement(pFanin) ); - } - // construct the function - pRes = Lpk_ImplementFun( pMan, pNtk, vLeaves, pFun ); - // replace the function - Vec_PtrWriteEntry( vLeaves, pFun->Id, Abc_ObjNot(pRes) ); - Lpk_FunFree( pFun ); - return pRes; -} - -/**Function************************************************************* - - Synopsis [Implements the function.] - - Description [Returns the node implementing this function.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Abc_Obj_t * Lpk_Implement( Lpk_Man_t * pMan, Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, int nLeavesOld ) -{ - Abc_Obj_t * pFanin, * pRes; - int i; - assert( nLeavesOld < Vec_PtrSize(vLeaves) ); - // mark implemented nodes - Vec_PtrForEachEntryStop( vLeaves, pFanin, i, nLeavesOld ) - Vec_PtrWriteEntry( vLeaves, i, Abc_ObjNot(pFanin) ); - // recursively construct starting from the first entry - pRes = Lpk_Implement_rec( pMan, pNtk, vLeaves, Vec_PtrEntry( vLeaves, nLeavesOld ) ); - Vec_PtrShrink( vLeaves, nLeavesOld ); - return pRes; -} - -/**Function************************************************************* - - Synopsis [Decomposes the function using recursive MUX decomposition.] - - Description [Returns the ID of the top-most decomposition node - implementing this function, or 0 if there is no decomposition satisfying - the constraints on area and delay.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Lpk_Decompose_rec( Lpk_Man_t * pMan, Lpk_Fun_t * p ) -{ - static Lpk_Res_t Res0, * pRes0 = &Res0; - Lpk_Res_t * pResMux, * pResDsd; - Lpk_Fun_t * p2; - int clk; - - // is only called for non-trivial blocks - assert( p->nLutK >= 3 && p->nLutK <= 6 ); - assert( p->nVars > p->nLutK ); - // skip if area bound is exceeded - if ( Lpk_LutNumLuts(p->nVars, p->nLutK) > (int)p->nAreaLim ) - return 0; - // skip if delay bound is exceeded - if ( Lpk_SuppDelay(p->uSupp, p->pDelays) > (int)p->nDelayLim ) - return 0; - - // compute supports if needed - if ( !p->fSupports ) - Lpk_FunComputeCofSupps( p ); - - // check DSD decomposition -clk = clock(); - pResDsd = Lpk_DsdAnalize( pMan, p, pMan->pPars->nVarsShared ); -pMan->timeEvalDsdAn += clock() - clk; - if ( pResDsd && (pResDsd->nBSVars == (int)p->nLutK || pResDsd->nBSVars == (int)p->nLutK - 1) && - pResDsd->AreaEst <= (int)p->nAreaLim && pResDsd->DelayEst <= (int)p->nDelayLim ) - { -clk = clock(); - p2 = Lpk_DsdSplit( pMan, p, pResDsd->pCofVars, pResDsd->nCofVars, pResDsd->BSVars ); -pMan->timeEvalDsdSp += clock() - clk; - assert( p2->nVars <= (int)p->nLutK ); - if ( p->nVars > p->nLutK && !Lpk_Decompose_rec( pMan, p ) ) - return 0; - return 1; - } - - // check MUX decomposition -clk = clock(); - pResMux = Lpk_MuxAnalize( pMan, p ); -pMan->timeEvalMuxAn += clock() - clk; -// pResMux = NULL; - assert( !pResMux || (pResMux->DelayEst <= (int)p->nDelayLim && pResMux->AreaEst <= (int)p->nAreaLim) ); - // accept MUX decomposition if it is "good" - if ( pResMux && pResMux->nSuppSizeS <= (int)p->nLutK && pResMux->nSuppSizeL <= (int)p->nLutK ) - pResDsd = NULL; - else if ( pResMux && pResDsd ) - { - // compare two decompositions - if ( pResMux->AreaEst < pResDsd->AreaEst || - (pResMux->AreaEst == pResDsd->AreaEst && pResMux->nSuppSizeL < pResDsd->nSuppSizeL) || - (pResMux->AreaEst == pResDsd->AreaEst && pResMux->nSuppSizeL == pResDsd->nSuppSizeL && pResMux->DelayEst < pResDsd->DelayEst) ) - pResDsd = NULL; - else - pResMux = NULL; - } - assert( pResMux == NULL || pResDsd == NULL ); - if ( pResMux ) - { -clk = clock(); - p2 = Lpk_MuxSplit( pMan, p, pResMux->Variable, pResMux->Polarity ); -pMan->timeEvalMuxSp += clock() - clk; - if ( p2->nVars > p->nLutK && !Lpk_Decompose_rec( pMan, p2 ) ) - return 0; - if ( p->nVars > p->nLutK && !Lpk_Decompose_rec( pMan, p ) ) - return 0; - return 1; - } - if ( pResDsd ) - { -clk = clock(); - p2 = Lpk_DsdSplit( pMan, p, pResDsd->pCofVars, pResDsd->nCofVars, pResDsd->BSVars ); -pMan->timeEvalDsdSp += clock() - clk; - assert( p2->nVars <= (int)p->nLutK ); - if ( p->nVars > p->nLutK && !Lpk_Decompose_rec( pMan, p ) ) - return 0; - return 1; - } - return 0; -} - -/**Function************************************************************* - - Synopsis [Removes decomposed nodes from the array of fanins.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Lpk_DecomposeClean( Vec_Ptr_t * vLeaves, int nLeavesOld ) -{ - Lpk_Fun_t * pFunc; - int i; - Vec_PtrForEachEntryStart( vLeaves, pFunc, i, nLeavesOld ) - Lpk_FunFree( pFunc ); - Vec_PtrShrink( vLeaves, nLeavesOld ); -} - -/**Function************************************************************* - - Synopsis [Decomposes the function using recursive MUX decomposition.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Abc_Obj_t * Lpk_Decompose( Lpk_Man_t * p, Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, unsigned * pTruth, unsigned * puSupps, int nLutK, int AreaLim, int DelayLim ) -{ - Lpk_Fun_t * pFun; - Abc_Obj_t * pObjNew = NULL; - int nLeaves = Vec_PtrSize( vLeaves ); - pFun = Lpk_FunCreate( pNtk, vLeaves, pTruth, nLutK, AreaLim, DelayLim ); - if ( puSupps[0] || puSupps[1] ) - { -/* - int i; - Lpk_FunComputeCofSupps( pFun ); - for ( i = 0; i < nLeaves; i++ ) - { - assert( pFun->puSupps[2*i+0] == puSupps[2*i+0] ); - assert( pFun->puSupps[2*i+1] == puSupps[2*i+1] ); - } -*/ - memcpy( pFun->puSupps, puSupps, sizeof(unsigned) * 2 * nLeaves ); - pFun->fSupports = 1; - } - Lpk_FunSuppMinimize( pFun ); - if ( pFun->nVars <= pFun->nLutK ) - pObjNew = Lpk_ImplementFun( p, pNtk, vLeaves, pFun ); - else if ( Lpk_Decompose_rec(p, pFun) ) - pObjNew = Lpk_Implement( p, pNtk, vLeaves, nLeaves ); - Lpk_DecomposeClean( vLeaves, nLeaves ); - return pObjNew; -} - - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/opt/lpk/lpkAbcDsd.c b/src/opt/lpk/lpkAbcDsd.c deleted file mode 100644 index f4095914..00000000 --- a/src/opt/lpk/lpkAbcDsd.c +++ /dev/null @@ -1,603 +0,0 @@ -/**CFile**************************************************************** - - FileName [lpkAbcDsd.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Fast Boolean matching for LUT structures.] - - Synopsis [LUT-decomposition based on recursive DSD.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - April 28, 2007.] - - Revision [$Id: lpkAbcDsd.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "lpkInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Cofactors TTs w.r.t. all vars and finds the best var.] - - Description [The best variable is the variable with the minimum - sum total of the support sizes of all truth tables. This procedure - computes and returns cofactors w.r.t. the best variable.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Lpk_FunComputeMinSuppSizeVar( Lpk_Fun_t * p, unsigned ** ppTruths, int nTruths, unsigned ** ppCofs, unsigned uNonDecSupp ) -{ - int i, Var, VarBest, nSuppSize0, nSuppSize1, nSuppTotalMin, nSuppTotalCur, nSuppMaxMin, nSuppMaxCur; - assert( nTruths > 0 ); - VarBest = -1; - Lpk_SuppForEachVar( p->uSupp, Var ) - { - if ( (uNonDecSupp & (1 << Var)) == 0 ) - continue; - nSuppMaxCur = 0; - nSuppTotalCur = 0; - for ( i = 0; i < nTruths; i++ ) - { - if ( nTruths == 1 ) - { - nSuppSize0 = Kit_WordCountOnes( p->puSupps[2*Var+0] ); - nSuppSize1 = Kit_WordCountOnes( p->puSupps[2*Var+1] ); - } - else - { - Kit_TruthCofactor0New( ppCofs[2*i+0], ppTruths[i], p->nVars, Var ); - Kit_TruthCofactor1New( ppCofs[2*i+1], ppTruths[i], p->nVars, Var ); - nSuppSize0 = Kit_TruthSupportSize( ppCofs[2*i+0], p->nVars ); - nSuppSize1 = Kit_TruthSupportSize( ppCofs[2*i+1], p->nVars ); - } - nSuppMaxCur = ABC_MAX( nSuppMaxCur, nSuppSize0 ); - nSuppMaxCur = ABC_MAX( nSuppMaxCur, nSuppSize1 ); - nSuppTotalCur += nSuppSize0 + nSuppSize1; - } - if ( VarBest == -1 || nSuppMaxMin > nSuppMaxCur || - (nSuppMaxMin == nSuppMaxCur && nSuppTotalMin > nSuppTotalCur) ) - { - VarBest = Var; - nSuppMaxMin = nSuppMaxCur; - nSuppTotalMin = nSuppTotalCur; - } - } - // recompute cofactors for the best var - for ( i = 0; i < nTruths; i++ ) - { - Kit_TruthCofactor0New( ppCofs[2*i+0], ppTruths[i], p->nVars, VarBest ); - Kit_TruthCofactor1New( ppCofs[2*i+1], ppTruths[i], p->nVars, VarBest ); - } - return VarBest; -} - -/**Function************************************************************* - - Synopsis [Recursively computes decomposable subsets.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -unsigned Lpk_ComputeBoundSets_rec( Kit_DsdNtk_t * p, int iLit, Vec_Int_t * vSets, int nSizeMax ) -{ - unsigned i, iLitFanin, uSupport, uSuppCur; - Kit_DsdObj_t * pObj; - // consider the case of simple gate - pObj = Kit_DsdNtkObj( p, Kit_DsdLit2Var(iLit) ); - if ( pObj == NULL ) - return (1 << Kit_DsdLit2Var(iLit)); - if ( pObj->Type == KIT_DSD_AND || pObj->Type == KIT_DSD_XOR ) - { - unsigned uSupps[16], Limit, s; - uSupport = 0; - Kit_DsdObjForEachFanin( p, pObj, iLitFanin, i ) - { - uSupps[i] = Lpk_ComputeBoundSets_rec( p, iLitFanin, vSets, nSizeMax ); - uSupport |= uSupps[i]; - } - // create all subsets, except empty and full - Limit = (1 << pObj->nFans) - 1; - for ( s = 1; s < Limit; s++ ) - { - uSuppCur = 0; - for ( i = 0; i < pObj->nFans; i++ ) - if ( s & (1 << i) ) - uSuppCur |= uSupps[i]; - if ( Kit_WordCountOnes(uSuppCur) <= nSizeMax ) - Vec_IntPush( vSets, uSuppCur ); - } - return uSupport; - } - assert( pObj->Type == KIT_DSD_PRIME ); - // get the cumulative support of all fanins - uSupport = 0; - Kit_DsdObjForEachFanin( p, pObj, iLitFanin, i ) - { - uSuppCur = Lpk_ComputeBoundSets_rec( p, iLitFanin, vSets, nSizeMax ); - uSupport |= uSuppCur; - if ( Kit_WordCountOnes(uSuppCur) <= nSizeMax ) - Vec_IntPush( vSets, uSuppCur ); - } - return uSupport; -} - -/**Function************************************************************* - - Synopsis [Computes the set of subsets of decomposable variables.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Vec_Int_t * Lpk_ComputeBoundSets( Kit_DsdNtk_t * p, int nSizeMax ) -{ - Vec_Int_t * vSets; - unsigned uSupport, Entry; - int Number, i; - assert( p->nVars <= 16 ); - vSets = Vec_IntAlloc( 100 ); - Vec_IntPush( vSets, 0 ); - if ( Kit_DsdNtkRoot(p)->Type == KIT_DSD_CONST1 ) - return vSets; - if ( Kit_DsdNtkRoot(p)->Type == KIT_DSD_VAR ) - { - uSupport = ( 1 << Kit_DsdLit2Var(Kit_DsdNtkRoot(p)->pFans[0]) ); - if ( Kit_WordCountOnes(uSupport) <= nSizeMax ) - Vec_IntPush( vSets, uSupport ); - return vSets; - } - uSupport = Lpk_ComputeBoundSets_rec( p, p->Root, vSets, nSizeMax ); - assert( (uSupport & 0xFFFF0000) == 0 ); - // add the total support of the network - if ( Kit_WordCountOnes(uSupport) <= nSizeMax ) - Vec_IntPush( vSets, uSupport ); - // set the remaining variables - Vec_IntForEachEntry( vSets, Number, i ) - { - Entry = Number; - Vec_IntWriteEntry( vSets, i, Entry | ((uSupport & ~Entry) << 16) ); - } - return vSets; -} - -/**Function************************************************************* - - Synopsis [Prints the sets of subsets.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static void Lpk_PrintSetOne( int uSupport ) -{ - unsigned k; - for ( k = 0; k < 16; k++ ) - if ( uSupport & (1<> 16)) ) - continue; - if ( Kit_WordCountOnes(Entry & 0xffff) <= nSizeMax ) - Vec_IntPush( vSets, Entry ); - } - return vSets; -} - -/**Function************************************************************* - - Synopsis [Performs DSD-based decomposition of the function.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Lpk_FunCompareBoundSets( Lpk_Fun_t * p, Vec_Int_t * vBSets, int nCofDepth, unsigned uNonDecSupp, unsigned uLateArrSupp, Lpk_Res_t * pRes ) -{ - int fVerbose = 0; - unsigned uBoundSet; - int i, nVarsBS, nVarsRem, Delay, Area; - - // compare the resulting boundsets - memset( pRes, 0, sizeof(Lpk_Res_t) ); - Vec_IntForEachEntry( vBSets, uBoundSet, i ) - { - if ( (uBoundSet & 0xFFFF) == 0 ) // skip empty boundset - continue; - if ( (uBoundSet & uNonDecSupp) == 0 ) // skip those boundsets that are not in the domain of interest - continue; - if ( (uBoundSet & uLateArrSupp) ) // skip those boundsets that are late arriving - continue; -if ( fVerbose ) -Lpk_PrintSetOne( uBoundSet ); - assert( (uBoundSet & (uBoundSet >> 16)) == 0 ); - nVarsBS = Kit_WordCountOnes( uBoundSet & 0xFFFF ); - if ( nVarsBS == 1 ) - continue; - assert( nVarsBS <= (int)p->nLutK - nCofDepth ); - nVarsRem = p->nVars - nVarsBS + 1; - Area = 1 + Lpk_LutNumLuts( nVarsRem, p->nLutK ); - Delay = 1 + Lpk_SuppDelay( uBoundSet & 0xFFFF, p->pDelays ); -if ( fVerbose ) -printf( "area = %d limit = %d delay = %d limit = %d\n", Area, (int)p->nAreaLim, Delay, (int)p->nDelayLim ); - if ( Area > (int)p->nAreaLim || Delay > (int)p->nDelayLim ) - continue; - if ( pRes->BSVars == 0 || pRes->nSuppSizeL > nVarsRem || (pRes->nSuppSizeL == nVarsRem && pRes->DelayEst > Delay) ) - { - pRes->nBSVars = nVarsBS; - pRes->BSVars = (uBoundSet & 0xFFFF); - pRes->nSuppSizeS = nVarsBS + nCofDepth; - pRes->nSuppSizeL = nVarsRem; - pRes->DelayEst = Delay; - pRes->AreaEst = Area; - } - } -if ( fVerbose ) -{ -if ( pRes->BSVars ) -{ -printf( "Found bound set " ); -Lpk_PrintSetOne( pRes->BSVars ); -printf( "\n" ); -} -else -printf( "Did not find boundsets.\n" ); -printf( "\n" ); -} - if ( pRes->BSVars ) - { - assert( pRes->DelayEst <= (int)p->nDelayLim ); - assert( pRes->AreaEst <= (int)p->nAreaLim ); - } -} - - -/**Function************************************************************* - - Synopsis [Finds late arriving inputs, which cannot be in the bound set.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -unsigned Lpk_DsdLateArriving( Lpk_Fun_t * p ) -{ - unsigned i, uLateArrSupp = 0; - Lpk_SuppForEachVar( p->uSupp, i ) - if ( p->pDelays[i] > (int)p->nDelayLim - 2 ) - uLateArrSupp |= (1 << i); - return uLateArrSupp; -} - -/**Function************************************************************* - - Synopsis [Performs DSD-based decomposition of the function.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Lpk_DsdAnalizeOne( Lpk_Fun_t * p, unsigned * ppTruths[5][16], Kit_DsdNtk_t * pNtks[], char pCofVars[], int nCofDepth, Lpk_Res_t * pRes ) -{ - int fVerbose = 0; - Vec_Int_t * pvBSets[4][8]; - unsigned uNonDecSupp, uLateArrSupp; - int i, k, nNonDecSize, nNonDecSizeMax; - assert( nCofDepth >= 1 && nCofDepth <= 3 ); - assert( nCofDepth < (int)p->nLutK - 1 ); - assert( p->fSupports ); - - // find the support of the largest non-DSD block - nNonDecSizeMax = 0; - uNonDecSupp = p->uSupp; - for ( i = 0; i < (1<<(nCofDepth-1)); i++ ) - { - nNonDecSize = Kit_DsdNonDsdSizeMax( pNtks[i] ); - if ( nNonDecSizeMax < nNonDecSize ) - { - nNonDecSizeMax = nNonDecSize; - uNonDecSupp = Kit_DsdNonDsdSupports( pNtks[i] ); - } - else if ( nNonDecSizeMax == nNonDecSize ) - uNonDecSupp |= Kit_DsdNonDsdSupports( pNtks[i] ); - } - - // remove those variables that cannot be used because of delay constraints - // if variables arrival time is more than p->DelayLim - 2, it cannot be used - uLateArrSupp = Lpk_DsdLateArriving( p ); - if ( (uNonDecSupp & ~uLateArrSupp) == 0 ) - { - memset( pRes, 0, sizeof(Lpk_Res_t) ); - return 0; - } - - // find the next cofactoring variable - pCofVars[nCofDepth-1] = Lpk_FunComputeMinSuppSizeVar( p, ppTruths[nCofDepth-1], 1<<(nCofDepth-1), ppTruths[nCofDepth], uNonDecSupp & ~uLateArrSupp ); - - // derive decomposed networks - for ( i = 0; i < (1<nVars ); -if ( fVerbose ) -Kit_DsdPrint( stdout, pNtks[i] ); - pvBSets[nCofDepth][i] = Lpk_ComputeBoundSets( pNtks[i], p->nLutK - nCofDepth ); // try restricting to those in uNonDecSupp!!! - } - - // derive the set of feasible boundsets - for ( i = nCofDepth - 1; i >= 0; i-- ) - for ( k = 0; k < (1<nLutK - nCofDepth ); - // compare bound-sets - Lpk_FunCompareBoundSets( p, pvBSets[0][0], nCofDepth, uNonDecSupp, uLateArrSupp, pRes ); - // free the bound sets - for ( i = nCofDepth; i >= 0; i-- ) - for ( k = 0; k < (1<BSVars ) - { - pRes->nCofVars = nCofDepth; - for ( i = 0; i < nCofDepth; i++ ) - pRes->pCofVars[i] = pCofVars[i]; - } - return 1; -} - -/**Function************************************************************* - - Synopsis [Performs DSD-based decomposition of the function.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Lpk_Res_t * Lpk_DsdAnalize( Lpk_Man_t * pMan, Lpk_Fun_t * p, int nShared ) -{ - static Lpk_Res_t Res0, * pRes0 = &Res0; - static Lpk_Res_t Res1, * pRes1 = &Res1; - static Lpk_Res_t Res2, * pRes2 = &Res2; - static Lpk_Res_t Res3, * pRes3 = &Res3; - int fUseBackLooking = 1; - Lpk_Res_t * pRes = NULL; - Vec_Int_t * vBSets; - Kit_DsdNtk_t * pNtks[8] = {NULL}; - char pCofVars[5]; - int i; - - assert( p->nLutK >= 3 ); - assert( nShared >= 0 && nShared <= 3 ); - assert( p->uSupp == Kit_BitMask(p->nVars) ); - - // try decomposition without cofactoring - pNtks[0] = Kit_DsdDecomposeExpand( Lpk_FunTruth( p, 0 ), p->nVars ); - if ( pMan->pPars->fVerbose ) - pMan->nBlocks[ Kit_DsdNonDsdSizeMax(pNtks[0]) ]++; - vBSets = Lpk_ComputeBoundSets( pNtks[0], p->nLutK ); - Lpk_FunCompareBoundSets( p, vBSets, 0, 0xFFFF, Lpk_DsdLateArriving(p), pRes0 ); - Vec_IntFree( vBSets ); - - // check the result - if ( pRes0->nBSVars == (int)p->nLutK ) - { pRes = pRes0; goto finish; } - if ( pRes0->nBSVars == (int)p->nLutK - 1 ) - { pRes = pRes0; goto finish; } - if ( nShared == 0 ) - goto finish; - - // prepare storage - Kit_TruthCopy( pMan->ppTruths[0][0], Lpk_FunTruth( p, 0 ), p->nVars ); - - // cofactor 1 time - if ( !Lpk_DsdAnalizeOne( p, pMan->ppTruths, pNtks, pCofVars, 1, pRes1 ) ) - goto finish; - assert( pRes1->nBSVars <= (int)p->nLutK - 1 ); - if ( pRes1->nBSVars == (int)p->nLutK - 1 ) - { pRes = pRes1; goto finish; } - if ( pRes0->nBSVars == (int)p->nLutK - 2 ) - { pRes = pRes0; goto finish; } - if ( pRes1->nBSVars == (int)p->nLutK - 2 ) - { pRes = pRes1; goto finish; } - if ( nShared == 1 ) - goto finish; - - // cofactor 2 times - if ( p->nLutK >= 4 ) - { - if ( !Lpk_DsdAnalizeOne( p, pMan->ppTruths, pNtks, pCofVars, 2, pRes2 ) ) - goto finish; - assert( pRes2->nBSVars <= (int)p->nLutK - 2 ); - if ( pRes2->nBSVars == (int)p->nLutK - 2 ) - { pRes = pRes2; goto finish; } - if ( fUseBackLooking ) - { - if ( pRes0->nBSVars == (int)p->nLutK - 3 ) - { pRes = pRes0; goto finish; } - if ( pRes1->nBSVars == (int)p->nLutK - 3 ) - { pRes = pRes1; goto finish; } - } - if ( pRes2->nBSVars == (int)p->nLutK - 3 ) - { pRes = pRes2; goto finish; } - if ( nShared == 2 ) - goto finish; - assert( nShared == 3 ); - } - - // cofactor 3 times - if ( p->nLutK >= 5 ) - { - if ( !Lpk_DsdAnalizeOne( p, pMan->ppTruths, pNtks, pCofVars, 3, pRes3 ) ) - goto finish; - assert( pRes3->nBSVars <= (int)p->nLutK - 3 ); - if ( pRes3->nBSVars == (int)p->nLutK - 3 ) - { pRes = pRes3; goto finish; } - if ( fUseBackLooking ) - { - if ( pRes0->nBSVars == (int)p->nLutK - 4 ) - { pRes = pRes0; goto finish; } - if ( pRes1->nBSVars == (int)p->nLutK - 4 ) - { pRes = pRes1; goto finish; } - if ( pRes2->nBSVars == (int)p->nLutK - 4 ) - { pRes = pRes2; goto finish; } - } - if ( pRes3->nBSVars == (int)p->nLutK - 4 ) - { pRes = pRes3; goto finish; } - } - -finish: - // free the networks - for ( i = 0; i < (1<ppTruths[0][0], Lpk_FunTruth(p, 0), p->nVars ); - // get the vacuous variable - iVacVar = Kit_WordFindFirstBit( uBoundSet ); - // compute the cofactors - for ( i = 0; i < nCofVars; i++ ) - for ( k = 0; k < (1<ppTruths[i+1][2*k+0], pMan->ppTruths[i][k], p->nVars, pCofVars[i] ); - Kit_TruthCofactor1New( pMan->ppTruths[i+1][2*k+1], pMan->ppTruths[i][k], p->nVars, pCofVars[i] ); - } - // decompose each cofactor w.r.t. the bound set - nCofs = (1<ppTruths[nCofVars][k], p->nVars ); - Kit_DsdTruthPartialTwo( pMan->pDsdMan, pNtkDec, uBoundSet, iVacVar, pMan->ppTruths[nCofVars+1][k], pMan->ppTruths[nCofVars+1][nCofs+k] ); - Kit_DsdNtkFree( pNtkDec ); - } - // compute the composition/decomposition functions (they will be in pMan->ppTruths[1][0]/pMan->ppTruths[1][1]) - for ( i = nCofVars; i >= 1; i-- ) - for ( k = 0; k < (1<ppTruths[i][k], pMan->ppTruths[i+1][2*k+0], pMan->ppTruths[i+1][2*k+1], p->nVars, pCofVars[i-1] ); - - // derive the new component (decomposition function) - pNew = Lpk_FunDup( p, pMan->ppTruths[1][1] ); - // update the old component (composition function) - Kit_TruthCopy( Lpk_FunTruth(p, 0), pMan->ppTruths[1][0], p->nVars ); - p->uSupp = Kit_TruthSupport( Lpk_FunTruth(p, 0), p->nVars ); - p->pFanins[iVacVar] = pNew->Id; - p->pDelays[iVacVar] = Lpk_SuppDelay( pNew->uSupp, pNew->pDelays ); - // support minimize both - p->fSupports = 0; - Lpk_FunSuppMinimize( p ); - Lpk_FunSuppMinimize( pNew ); - // update delay and area requirements - pNew->nDelayLim = p->pDelays[iVacVar]; - pNew->nAreaLim = 1; - p->nAreaLim = p->nAreaLim - 1; - return pNew; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/opt/lpk/lpkAbcMux.c b/src/opt/lpk/lpkAbcMux.c deleted file mode 100644 index d6f579ee..00000000 --- a/src/opt/lpk/lpkAbcMux.c +++ /dev/null @@ -1,235 +0,0 @@ -/**CFile**************************************************************** - - FileName [lpkAbcMux.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Fast Boolean matching for LUT structures.] - - Synopsis [LUT-decomposition based on recursive MUX decomposition.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - April 28, 2007.] - - Revision [$Id: lpkAbcMux.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "lpkInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Checks the possibility of MUX decomposition.] - - Description [Returns the best variable to use for MUX decomposition.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Lpk_Res_t * Lpk_MuxAnalize( Lpk_Man_t * pMan, Lpk_Fun_t * p ) -{ - static Lpk_Res_t Res, * pRes = &Res; - int nSuppSize0, nSuppSize1, nSuppSizeS, nSuppSizeL; - int Var, Area, Polarity, Delay, Delay0, Delay1, DelayA, DelayB; - memset( pRes, 0, sizeof(Lpk_Res_t) ); - assert( p->uSupp == Kit_BitMask(p->nVars) ); - assert( p->fSupports ); - // derive the delay and area after MUX-decomp with each var - and find the best var - pRes->Variable = -1; - Lpk_SuppForEachVar( p->uSupp, Var ) - { - nSuppSize0 = Kit_WordCountOnes(p->puSupps[2*Var+0]); - nSuppSize1 = Kit_WordCountOnes(p->puSupps[2*Var+1]); - assert( nSuppSize0 < (int)p->nVars ); - assert( nSuppSize1 < (int)p->nVars ); - if ( nSuppSize0 < 1 || nSuppSize1 < 1 ) - continue; -//printf( "%d %d ", nSuppSize0, nSuppSize1 ); - if ( nSuppSize0 <= (int)p->nLutK - 2 && nSuppSize1 <= (int)p->nLutK - 2 ) - { - // include cof var into 0-block - DelayA = Lpk_SuppDelay( p->puSupps[2*Var+0] | (1<pDelays ); - DelayB = Lpk_SuppDelay( p->puSupps[2*Var+1] , p->pDelays ); - Delay0 = ABC_MAX( DelayA, DelayB + 1 ); - // include cof var into 1-block - DelayA = Lpk_SuppDelay( p->puSupps[2*Var+1] | (1<pDelays ); - DelayB = Lpk_SuppDelay( p->puSupps[2*Var+0] , p->pDelays ); - Delay1 = ABC_MAX( DelayA, DelayB + 1 ); - // get the best delay - Delay = ABC_MIN( Delay0, Delay1 ); - Area = 2; - Polarity = (int)(Delay == Delay1); - } - else if ( nSuppSize0 <= (int)p->nLutK - 2 ) - { - DelayA = Lpk_SuppDelay( p->puSupps[2*Var+0] | (1<pDelays ); - DelayB = Lpk_SuppDelay( p->puSupps[2*Var+1] , p->pDelays ); - Delay = ABC_MAX( DelayA, DelayB + 1 ); - Area = 1 + Lpk_LutNumLuts( nSuppSize1, p->nLutK ); - Polarity = 0; - } - else if ( nSuppSize1 <= (int)p->nLutK - 2 ) - { - DelayA = Lpk_SuppDelay( p->puSupps[2*Var+1] | (1<pDelays ); - DelayB = Lpk_SuppDelay( p->puSupps[2*Var+0] , p->pDelays ); - Delay = ABC_MAX( DelayA, DelayB + 1 ); - Area = 1 + Lpk_LutNumLuts( nSuppSize0, p->nLutK ); - Polarity = 1; - } - else if ( nSuppSize0 <= (int)p->nLutK ) - { - DelayA = Lpk_SuppDelay( p->puSupps[2*Var+1] | (1<pDelays ); - DelayB = Lpk_SuppDelay( p->puSupps[2*Var+0] , p->pDelays ); - Delay = ABC_MAX( DelayA, DelayB + 1 ); - Area = 1 + Lpk_LutNumLuts( nSuppSize1+2, p->nLutK ); - Polarity = 1; - } - else if ( nSuppSize1 <= (int)p->nLutK ) - { - DelayA = Lpk_SuppDelay( p->puSupps[2*Var+0] | (1<pDelays ); - DelayB = Lpk_SuppDelay( p->puSupps[2*Var+1] , p->pDelays ); - Delay = ABC_MAX( DelayA, DelayB + 1 ); - Area = 1 + Lpk_LutNumLuts( nSuppSize0+2, p->nLutK ); - Polarity = 0; - } - else - { - // include cof var into 0-block - DelayA = Lpk_SuppDelay( p->puSupps[2*Var+0] | (1<pDelays ); - DelayB = Lpk_SuppDelay( p->puSupps[2*Var+1] , p->pDelays ); - Delay0 = ABC_MAX( DelayA, DelayB + 1 ); - // include cof var into 1-block - DelayA = Lpk_SuppDelay( p->puSupps[2*Var+1] | (1<pDelays ); - DelayB = Lpk_SuppDelay( p->puSupps[2*Var+0] , p->pDelays ); - Delay1 = ABC_MAX( DelayA, DelayB + 1 ); - // get the best delay - Delay = ABC_MIN( Delay0, Delay1 ); - if ( Delay == Delay0 ) - Area = Lpk_LutNumLuts( nSuppSize0+2, p->nLutK ) + Lpk_LutNumLuts( nSuppSize1, p->nLutK ); - else - Area = Lpk_LutNumLuts( nSuppSize1+2, p->nLutK ) + Lpk_LutNumLuts( nSuppSize0, p->nLutK ); - Polarity = (int)(Delay == Delay1); - } - // find the best variable - if ( Delay > (int)p->nDelayLim ) - continue; - if ( Area > (int)p->nAreaLim ) - continue; - nSuppSizeS = ABC_MIN( nSuppSize0 + 2 *!Polarity, nSuppSize1 + 2 * Polarity ); - nSuppSizeL = ABC_MAX( nSuppSize0 + 2 *!Polarity, nSuppSize1 + 2 * Polarity ); - if ( nSuppSizeL > (int)p->nVars ) - continue; - if ( pRes->Variable == -1 || pRes->AreaEst > Area || - (pRes->AreaEst == Area && pRes->nSuppSizeS + pRes->nSuppSizeL > nSuppSizeS + nSuppSizeL) || - (pRes->AreaEst == Area && pRes->nSuppSizeS + pRes->nSuppSizeL == nSuppSizeS + nSuppSizeL && pRes->DelayEst > Delay) ) - { - pRes->Variable = Var; - pRes->Polarity = Polarity; - pRes->AreaEst = Area; - pRes->DelayEst = Delay; - pRes->nSuppSizeS = nSuppSizeS; - pRes->nSuppSizeL = nSuppSizeL; - } - } - return pRes->Variable == -1 ? NULL : pRes; -} - -/**Function************************************************************* - - Synopsis [Transforms the function decomposed by the MUX decomposition.] - - Description [Returns the best variable to use for MUX decomposition.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Lpk_Fun_t * Lpk_MuxSplit( Lpk_Man_t * pMan, Lpk_Fun_t * p, int Var, int Pol ) -{ - Lpk_Fun_t * pNew; - unsigned * pTruth = Lpk_FunTruth( p, 0 ); - unsigned * pTruth0 = Lpk_FunTruth( p, 1 ); - unsigned * pTruth1 = Lpk_FunTruth( p, 2 ); -// unsigned uSupp; - int iVarVac; - assert( Var >= 0 && Var < (int)p->nVars ); - assert( p->nAreaLim >= 2 ); - assert( p->uSupp == Kit_BitMask(p->nVars) ); - Kit_TruthCofactor0New( pTruth0, pTruth, p->nVars, Var ); - Kit_TruthCofactor1New( pTruth1, pTruth, p->nVars, Var ); -/* -uSupp = Kit_TruthSupport( pTruth, p->nVars ); -Extra_PrintBinary( stdout, &uSupp, 16 ); printf( "\n" ); -uSupp = Kit_TruthSupport( pTruth0, p->nVars ); -Extra_PrintBinary( stdout, &uSupp, 16 ); printf( "\n" ); -uSupp = Kit_TruthSupport( pTruth1, p->nVars ); -Extra_PrintBinary( stdout, &uSupp, 16 ); printf( "\n\n" ); -*/ - // derive the new component - pNew = Lpk_FunDup( p, Pol ? pTruth0 : pTruth1 ); - // update the support of the old component - p->uSupp = Kit_TruthSupport( Pol ? pTruth1 : pTruth0, p->nVars ); - p->uSupp |= (1 << Var); - // update the truth table of the old component - iVarVac = Kit_WordFindFirstBit( ~p->uSupp ); - assert( iVarVac < (int)p->nVars ); - p->uSupp |= (1 << iVarVac); - Kit_TruthIthVar( pTruth, p->nVars, iVarVac ); - if ( Pol ) - Kit_TruthMuxVar( pTruth, pTruth, pTruth1, p->nVars, Var ); - else - Kit_TruthMuxVar( pTruth, pTruth0, pTruth, p->nVars, Var ); - assert( p->uSupp == Kit_TruthSupport(pTruth, p->nVars) ); - // set the decomposed variable - p->pFanins[iVarVac] = pNew->Id; - p->pDelays[iVarVac] = p->nDelayLim - 1; - // support minimize both - p->fSupports = 0; - Lpk_FunSuppMinimize( p ); - Lpk_FunSuppMinimize( pNew ); - // update delay and area requirements - pNew->nDelayLim = p->nDelayLim - 1; - if ( pNew->nVars <= pNew->nLutK ) - { - pNew->nAreaLim = 1; - p->nAreaLim = p->nAreaLim - 1; - } - else if ( p->nVars <= p->nLutK ) - { - pNew->nAreaLim = p->nAreaLim - 1; - p->nAreaLim = 1; - } - else if ( p->nVars < pNew->nVars ) - { - pNew->nAreaLim = p->nAreaLim / 2 + p->nAreaLim % 2; - p->nAreaLim = p->nAreaLim / 2 - p->nAreaLim % 2; - } - else // if ( pNew->nVars < p->nVars ) - { - pNew->nAreaLim = p->nAreaLim / 2 - p->nAreaLim % 2; - p->nAreaLim = p->nAreaLim / 2 + p->nAreaLim % 2; - } - pNew->fMark = 1; - return pNew; -} - - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/opt/lpk/lpkAbcUtil.c b/src/opt/lpk/lpkAbcUtil.c deleted file mode 100644 index 3f917ce2..00000000 --- a/src/opt/lpk/lpkAbcUtil.c +++ /dev/null @@ -1,244 +0,0 @@ -/**CFile**************************************************************** - - FileName [lpkAbcUtil.c] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Fast Boolean matching for LUT structures.] - - Synopsis [Procedures working on decomposed functions.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - April 28, 2007.] - - Revision [$Id: lpkAbcUtil.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "lpkInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Allocates the function.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Lpk_Fun_t * Lpk_FunAlloc( int nVars ) -{ - Lpk_Fun_t * p; - p = (Lpk_Fun_t *)malloc( sizeof(Lpk_Fun_t) + sizeof(unsigned) * Kit_TruthWordNum(nVars) * 3 ); - memset( p, 0, sizeof(Lpk_Fun_t) ); - return p; -} - -/**Function************************************************************* - - Synopsis [Deletes the function] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Lpk_FunFree( Lpk_Fun_t * p ) -{ - free( p ); -} - -/**Function************************************************************* - - Synopsis [Creates the starting function.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Lpk_Fun_t * Lpk_FunCreate( Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, unsigned * pTruth, int nLutK, int AreaLim, int DelayLim ) -{ - Lpk_Fun_t * p; - Abc_Obj_t * pNode; - int i; - p = Lpk_FunAlloc( Vec_PtrSize(vLeaves) ); - p->Id = Vec_PtrSize(vLeaves); - p->vNodes = vLeaves; - p->nVars = Vec_PtrSize(vLeaves); - p->nLutK = nLutK; - p->nAreaLim = AreaLim; - p->nDelayLim = DelayLim; - p->uSupp = Kit_TruthSupport( pTruth, p->nVars ); - Kit_TruthCopy( Lpk_FunTruth(p,0), pTruth, p->nVars ); - Vec_PtrForEachEntry( vLeaves, pNode, i ) - { - p->pFanins[i] = i; - p->pDelays[i] = pNode->Level; - } - Vec_PtrPush( p->vNodes, p ); - return p; -} - -/**Function************************************************************* - - Synopsis [Creates the new function with the given truth table.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -Lpk_Fun_t * Lpk_FunDup( Lpk_Fun_t * p, unsigned * pTruth ) -{ - Lpk_Fun_t * pNew; - pNew = Lpk_FunAlloc( p->nVars ); - pNew->Id = Vec_PtrSize(p->vNodes); - pNew->vNodes = p->vNodes; - pNew->nVars = p->nVars; - pNew->nLutK = p->nLutK; - pNew->nAreaLim = p->nAreaLim; - pNew->nDelayLim = p->nDelayLim; - pNew->uSupp = Kit_TruthSupport( pTruth, p->nVars ); - Kit_TruthCopy( Lpk_FunTruth(pNew,0), pTruth, p->nVars ); - memcpy( pNew->pFanins, p->pFanins, 16 ); - memcpy( pNew->pDelays, p->pDelays, 16 ); - Vec_PtrPush( p->vNodes, pNew ); - return pNew; -} - -/**Function************************************************************* - - Synopsis [Minimizes support of the function.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Lpk_FunSuppMinimize( Lpk_Fun_t * p ) -{ - int i, k, nVarsNew; - // compress the truth table - if ( p->uSupp == Kit_BitMask(p->nVars) ) - return 0; - // invalidate support info - p->fSupports = 0; -//Extra_PrintBinary( stdout, &p->uSupp, p->nVars ); printf( "\n" ); - // minimize support - nVarsNew = Kit_WordCountOnes(p->uSupp); - Kit_TruthShrink( Lpk_FunTruth(p, 1), Lpk_FunTruth(p, 0), nVarsNew, p->nVars, p->uSupp, 1 ); - k = 0; - Lpk_SuppForEachVar( p->uSupp, i ) - { - p->pFanins[k] = p->pFanins[i]; - p->pDelays[k] = p->pDelays[i]; -/* - if ( p->fSupports ) - { - p->puSupps[2*k+0] = p->puSupps[2*i+0]; - p->puSupps[2*k+1] = p->puSupps[2*i+1]; - } -*/ - k++; - } - assert( k == nVarsNew ); - p->nVars = k; - p->uSupp = Kit_BitMask(p->nVars); - return 1; -} - -/**Function************************************************************* - - Synopsis [Computes cofactors w.r.t. each variable.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Lpk_FunComputeCofSupps( Lpk_Fun_t * p ) -{ - unsigned * pTruth = Lpk_FunTruth( p, 0 ); - unsigned * pTruth0 = Lpk_FunTruth( p, 1 ); - unsigned * pTruth1 = Lpk_FunTruth( p, 2 ); - int Var; - assert( p->fSupports == 0 ); -// Lpk_SuppForEachVar( p->uSupp, Var ) - for ( Var = 0; Var < (int)p->nVars; Var++ ) - { - Kit_TruthCofactor0New( pTruth0, pTruth, p->nVars, Var ); - Kit_TruthCofactor1New( pTruth1, pTruth, p->nVars, Var ); - p->puSupps[2*Var+0] = Kit_TruthSupport( pTruth0, p->nVars ); - p->puSupps[2*Var+1] = Kit_TruthSupport( pTruth1, p->nVars ); - } - p->fSupports = 1; -} - -/**Function************************************************************* - - Synopsis [Get the delay of the bound set.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Lpk_SuppDelay( unsigned uSupp, char * pDelays ) -{ - int Delay, Var; - Delay = 0; - Lpk_SuppForEachVar( uSupp, Var ) - Delay = ABC_MAX( Delay, pDelays[Var] ); - return Delay + 1; -} - -/**Function************************************************************* - - Synopsis [Converts support into variables.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Lpk_SuppToVars( unsigned uBoundSet, char * pVars ) -{ - int i, nVars = 0; - Lpk_SuppForEachVar( uBoundSet, i ) - pVars[nVars++] = i; - return nVars; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/opt/lpk/lpkCore.c b/src/opt/lpk/lpkCore.c deleted file mode 100644 index e819a7fb..00000000 --- a/src/opt/lpk/lpkCore.c +++ /dev/null @@ -1,659 +0,0 @@ -/**CFile**************************************************************** - - FileName [lpkCore.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: lpkCore.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "lpkInt.h" -#include "cloud.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Prepares the mapping manager.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Lpk_IfManStart( Lpk_Man_t * p ) -{ - If_Par_t * pPars; - assert( p->pIfMan == NULL ); - // set defaults - pPars = ALLOC( If_Par_t, 1 ); - memset( pPars, 0, sizeof(If_Par_t) ); - // user-controlable paramters - pPars->nLutSize = p->pPars->nLutSize; - pPars->nCutsMax = 16; - pPars->nFlowIters = 0; // 1 - pPars->nAreaIters = 0; // 1 - pPars->DelayTarget = -1; - pPars->fPreprocess = 0; - pPars->fArea = 1; - pPars->fFancy = 0; - pPars->fExpRed = 0; // - pPars->fLatchPaths = 0; - pPars->fSeqMap = 0; - pPars->fVerbose = 0; - // internal parameters - pPars->fTruth = 1; - pPars->fUsePerm = 0; - pPars->nLatches = 0; - pPars->pLutLib = NULL; // Abc_FrameReadLibLut(); - pPars->pTimesArr = NULL; - pPars->pTimesArr = NULL; - pPars->fUseBdds = 0; - pPars->fUseSops = 0; - pPars->fUseCnfs = 0; - pPars->fUseMv = 0; - // start the mapping manager and set its parameters - p->pIfMan = If_ManStart( pPars ); - If_ManSetupSetAll( p->pIfMan, 1000 ); - p->pIfMan->pPars->pTimesArr = ALLOC( float, 32 ); -} - -/**Function************************************************************* - - Synopsis [Returns 1 if at least one entry has changed.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Lpk_NodeHasChanged( Lpk_Man_t * p, int iNode ) -{ - Vec_Ptr_t * vNodes; - Abc_Obj_t * pTemp; - int i; - vNodes = Vec_VecEntry( p->vVisited, iNode ); - if ( Vec_PtrSize(vNodes) == 0 ) - return 1; - Vec_PtrForEachEntry( vNodes, pTemp, i ) - { - // check if the node has changed - pTemp = Abc_NtkObj( p->pNtk, (int)pTemp ); - if ( pTemp == NULL ) - return 1; - // check if the number of fanouts has changed -// if ( Abc_ObjFanoutNum(pTemp) != (int)Vec_PtrEntry(vNodes, i+1) ) -// return 1; - i++; - } - return 0; -} - -/**Function************************************************************* - - Synopsis [Prepares the mapping manager.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Lpk_ExploreCut( Lpk_Man_t * p, Lpk_Cut_t * pCut, Kit_DsdNtk_t * pNtk ) -{ - extern Abc_Obj_t * Abc_NodeFromIf_rec( Abc_Ntk_t * pNtkNew, If_Man_t * pIfMan, If_Obj_t * pIfObj, Vec_Int_t * vCover ); - Kit_DsdObj_t * pRoot; - If_Obj_t * pDriver, * ppLeaves[16]; - Abc_Obj_t * pLeaf, * pObjNew; - int nGain, i, clk; - int nNodesBef; -// int nOldShared; - - // check special cases - pRoot = Kit_DsdNtkRoot( pNtk ); - if ( pRoot->Type == KIT_DSD_CONST1 ) - { - if ( Kit_DsdLitIsCompl(pNtk->Root) ) - pObjNew = Abc_NtkCreateNodeConst0( p->pNtk ); - else - pObjNew = Abc_NtkCreateNodeConst1( p->pNtk ); - Abc_NtkUpdate( p->pObj, pObjNew, p->vLevels ); - p->nGainTotal += pCut->nNodes - pCut->nNodesDup; - return 1; - } - if ( pRoot->Type == KIT_DSD_VAR ) - { - pObjNew = Abc_NtkObj( p->pNtk, pCut->pLeaves[ Kit_DsdLit2Var(pRoot->pFans[0]) ] ); - if ( Kit_DsdLitIsCompl(pNtk->Root) ^ Kit_DsdLitIsCompl(pRoot->pFans[0]) ) - pObjNew = Abc_NtkCreateNodeInv( p->pNtk, pObjNew ); - Abc_NtkUpdate( p->pObj, pObjNew, p->vLevels ); - p->nGainTotal += pCut->nNodes - pCut->nNodesDup; - return 1; - } - assert( pRoot->Type == KIT_DSD_AND || pRoot->Type == KIT_DSD_XOR || pRoot->Type == KIT_DSD_PRIME ); - - // start the mapping manager - if ( p->pIfMan == NULL ) - Lpk_IfManStart( p ); - - // prepare the mapping manager - If_ManRestart( p->pIfMan ); - // create the PI variables - for ( i = 0; i < p->pPars->nVarsMax; i++ ) - ppLeaves[i] = If_ManCreateCi( p->pIfMan ); - // set the arrival times - Lpk_CutForEachLeaf( p->pNtk, pCut, pLeaf, i ) - p->pIfMan->pPars->pTimesArr[i] = (float)pLeaf->Level; - // prepare the PI cuts - If_ManSetupCiCutSets( p->pIfMan ); - // create the internal nodes - p->fCalledOnce = 0; - p->nCalledSRed = 0; - pDriver = Lpk_MapTree_rec( p, pNtk, ppLeaves, pNtk->Root, NULL ); - if ( pDriver == NULL ) - return 0; - // create the PO node - If_ManCreateCo( p->pIfMan, If_Regular(pDriver) ); - - // perform mapping - p->pIfMan->pPars->fAreaOnly = 1; -clk = clock(); - If_ManPerformMappingComb( p->pIfMan ); -p->timeMap += clock() - clk; - - // compute the gain in area - nGain = pCut->nNodes - pCut->nNodesDup - (int)p->pIfMan->AreaGlo; - if ( p->pPars->fVeryVerbose ) - printf( " Mffc = %2d. Mapped = %2d. Gain = %3d. Depth increase = %d. SReds = %d.\n", - pCut->nNodes - pCut->nNodesDup, (int)p->pIfMan->AreaGlo, nGain, (int)p->pIfMan->RequiredGlo - (int)p->pObj->Level, p->nCalledSRed ); - - // quit if there is no gain - if ( !(nGain > 0 || (p->pPars->fZeroCost && nGain == 0)) ) - return 0; - - // quit if depth increases too much - if ( (int)p->pIfMan->RequiredGlo > Abc_ObjRequiredLevel(p->pObj) ) - return 0; - - // perform replacement - p->nGainTotal += nGain; - p->nChanges++; - if ( p->nCalledSRed ) - p->nBenefited++; - - nNodesBef = Abc_NtkNodeNum(p->pNtk); - // prepare the mapping manager - If_ManCleanNodeCopy( p->pIfMan ); - If_ManCleanCutData( p->pIfMan ); - // set the PIs of the cut - Lpk_CutForEachLeaf( p->pNtk, pCut, pLeaf, i ) - If_ObjSetCopy( If_ManCi(p->pIfMan, i), pLeaf ); - // get the area of mapping - pObjNew = Abc_NodeFromIf_rec( p->pNtk, p->pIfMan, If_Regular(pDriver), p->vCover ); - pObjNew->pData = Hop_NotCond( pObjNew->pData, If_IsComplement(pDriver) ); - // perform replacement - Abc_NtkUpdate( p->pObj, pObjNew, p->vLevels ); -//printf( "%3d : %d-%d=%d(%d) \n", p->nChanges, nNodesBef, Abc_NtkNodeNum(p->pNtk), nNodesBef-Abc_NtkNodeNum(p->pNtk), nGain ); - return 1; -} - -/**Function************************************************************* - - Synopsis [Performs resynthesis for one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Lpk_ResynthesizeNode( Lpk_Man_t * p ) -{ - static int Count = 0; - Kit_DsdNtk_t * pDsdNtk; - Lpk_Cut_t * pCut; - unsigned * pTruth; - int i, k, nSuppSize, nCutNodes, RetValue, clk; - - // compute the cuts -clk = clock(); - if ( !Lpk_NodeCuts( p ) ) - { -p->timeCuts += clock() - clk; - return 0; - } -p->timeCuts += clock() - clk; - -//return 0; - - if ( p->pPars->fVeryVerbose ) - printf( "Node %5d : Mffc size = %5d. Cuts = %5d.\n", p->pObj->Id, p->nMffc, p->nEvals ); - // try the good cuts - p->nCutsTotal += p->nCuts; - p->nCutsUseful += p->nEvals; - for ( i = 0; i < p->nEvals; i++ ) - { - // get the cut - pCut = p->pCuts + p->pEvals[i]; - if ( p->pPars->fFirst && i == 1 ) - break; - - // skip bad cuts -// printf( "Mffc size = %d. ", Abc_NodeMffcLabel(p->pObj) ); - for ( k = 0; k < (int)pCut->nLeaves; k++ ) - Abc_NtkObj(p->pNtk, pCut->pLeaves[k])->vFanouts.nSize++; - nCutNodes = Abc_NodeMffcLabel(p->pObj); -// printf( "Mffc with cut = %d. ", nCutNodes ); - for ( k = 0; k < (int)pCut->nLeaves; k++ ) - Abc_NtkObj(p->pNtk, pCut->pLeaves[k])->vFanouts.nSize--; -// printf( "Mffc cut = %d. ", (int)pCut->nNodes - (int)pCut->nNodesDup ); -// printf( "\n" ); - if ( nCutNodes != (int)pCut->nNodes - (int)pCut->nNodesDup ) - continue; - - // compute the truth table -clk = clock(); - pTruth = Lpk_CutTruth( p, pCut, 0 ); - nSuppSize = Extra_TruthSupportSize(pTruth, pCut->nLeaves); -p->timeTruth += clock() - clk; - - pDsdNtk = Kit_DsdDecompose( pTruth, pCut->nLeaves ); -// Kit_DsdVerify( pDsdNtk, pTruth, pCut->nLeaves ); - // skip 16-input non-DSD because ISOP will not work - if ( Kit_DsdNtkRoot(pDsdNtk)->nFans == 16 ) - { - Kit_DsdNtkFree( pDsdNtk ); - continue; - } - - // if DSD has nodes that require splitting to fit them into LUTs - // we can skip those cuts that cannot lead to improvement - // (a full DSD network requires V = Nmin * (K-1) + 1 for improvement) - if ( Kit_DsdNonDsdSizeMax(pDsdNtk) > p->pPars->nLutSize && - nSuppSize >= ((int)pCut->nNodes - (int)pCut->nNodesDup - 1) * (p->pPars->nLutSize - 1) + 1 ) - { - Kit_DsdNtkFree( pDsdNtk ); - continue; - } - - if ( p->pPars->fVeryVerbose ) - { -// char * pFileName; - printf( " C%02d: L= %2d/%2d V= %2d/%d N= %d W= %4.2f ", - i, pCut->nLeaves, nSuppSize, pCut->nNodes, pCut->nNodesDup, pCut->nLuts, pCut->Weight ); - Kit_DsdPrint( stdout, pDsdNtk ); - Kit_DsdPrintFromTruth( pTruth, pCut->nLeaves ); -// pFileName = Kit_TruthDumpToFile( pTruth, pCut->nLeaves, Count++ ); -// printf( "Saved truth table in file \"%s\".\n", pFileName ); - } - - // update the network -clk = clock(); - RetValue = Lpk_ExploreCut( p, pCut, pDsdNtk ); -p->timeEval += clock() - clk; - Kit_DsdNtkFree( pDsdNtk ); - if ( RetValue ) - break; - } - return 1; -} - - -/**Function************************************************************* - - Synopsis [Computes supports of the cofactors of the function.] - - Description [This procedure should be called after Lpk_CutTruth(p,pCut,0)] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Lpk_ComputeSupports( Lpk_Man_t * p, Lpk_Cut_t * pCut, unsigned * pTruth ) -{ - unsigned * pTruthInv; - int RetValue1, RetValue2; - pTruthInv = Lpk_CutTruth( p, pCut, 1 ); - RetValue1 = Kit_CreateCloudFromTruth( p->pDsdMan->dd, pTruth, pCut->nLeaves, p->vBddDir ); - RetValue2 = Kit_CreateCloudFromTruth( p->pDsdMan->dd, pTruthInv, pCut->nLeaves, p->vBddInv ); - if ( RetValue1 && RetValue2 ) - Kit_TruthCofSupports( p->vBddDir, p->vBddInv, pCut->nLeaves, p->vMemory, p->puSupps ); - else - p->puSupps[0] = p->puSupps[1] = 0; -} - - -/**Function************************************************************* - - Synopsis [Performs resynthesis for one node.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Lpk_ResynthesizeNodeNew( Lpk_Man_t * p ) -{ - static int Count = 0; - Abc_Obj_t * pObjNew, * pLeaf; - Lpk_Cut_t * pCut; - unsigned * pTruth; - int nNodesBef, nNodesAft, nCutNodes; - int i, k, clk; - int Required = Abc_ObjRequiredLevel(p->pObj); -// CloudNode * pFun2;//, * pFun1; - - // compute the cuts -clk = clock(); - if ( !Lpk_NodeCuts( p ) ) - { -p->timeCuts += clock() - clk; - return 0; - } -p->timeCuts += clock() - clk; - - if ( p->pPars->fVeryVerbose ) - printf( "Node %5d : Mffc size = %5d. Cuts = %5d. Level = %2d. Req = %2d.\n", - p->pObj->Id, p->nMffc, p->nEvals, p->pObj->Level, Required ); - // try the good cuts - p->nCutsTotal += p->nCuts; - p->nCutsUseful += p->nEvals; - for ( i = 0; i < p->nEvals; i++ ) - { - // get the cut - pCut = p->pCuts + p->pEvals[i]; - if ( p->pPars->fFirst && i == 1 ) - break; -// if ( pCut->Weight < 1.05 ) -// continue; - - // skip bad cuts -// printf( "Mffc size = %d. ", Abc_NodeMffcLabel(p->pObj) ); - for ( k = 0; k < (int)pCut->nLeaves; k++ ) - Abc_NtkObj(p->pNtk, pCut->pLeaves[k])->vFanouts.nSize++; - nCutNodes = Abc_NodeMffcLabel(p->pObj); -// printf( "Mffc with cut = %d. ", nCutNodes ); - for ( k = 0; k < (int)pCut->nLeaves; k++ ) - Abc_NtkObj(p->pNtk, pCut->pLeaves[k])->vFanouts.nSize--; -// printf( "Mffc cut = %d. ", (int)pCut->nNodes - (int)pCut->nNodesDup ); -// printf( "\n" ); - if ( nCutNodes != (int)pCut->nNodes - (int)pCut->nNodesDup ) - continue; - - // collect nodes into the array - Vec_PtrClear( p->vLeaves ); - for ( k = 0; k < (int)pCut->nLeaves; k++ ) - Vec_PtrPush( p->vLeaves, Abc_NtkObj(p->pNtk, pCut->pLeaves[k]) ); - - // compute the truth table -clk = clock(); - pTruth = Lpk_CutTruth( p, pCut, 0 ); -p->timeTruth += clock() - clk; -clk = clock(); - Lpk_ComputeSupports( p, pCut, pTruth ); -p->timeSupps += clock() - clk; -//clk = clock(); -// pFun1 = Lpk_CutTruthBdd( p, pCut ); -//p->timeTruth2 += clock() - clk; -/* -clk = clock(); - Cloud_Restart( p->pDsdMan->dd ); - pFun2 = Kit_TruthToCloud( p->pDsdMan->dd, pTruth, pCut->nLeaves ); - RetValue = Kit_CreateCloud( p->pDsdMan->dd, pFun2, p->vBddNodes ); -p->timeTruth3 += clock() - clk; -*/ -// if ( pFun1 != pFun2 ) -// printf( "Truth tables do not agree!\n" ); -// else -// printf( "Fine!\n" ); - - if ( p->pPars->fVeryVerbose ) - { -// char * pFileName; - int nSuppSize = Extra_TruthSupportSize( pTruth, pCut->nLeaves ); - printf( " C%02d: L= %2d/%2d V= %2d/%d N= %d W= %4.2f ", - i, pCut->nLeaves, nSuppSize, pCut->nNodes, pCut->nNodesDup, pCut->nLuts, pCut->Weight ); - Vec_PtrForEachEntry( p->vLeaves, pLeaf, k ) - printf( "%c=%d ", 'a'+k, Abc_ObjLevel(pLeaf) ); - printf( "\n" ); - Kit_DsdPrintFromTruth( pTruth, pCut->nLeaves ); -// pFileName = Kit_TruthDumpToFile( pTruth, pCut->nLeaves, Count++ ); -// printf( "Saved truth table in file \"%s\".\n", pFileName ); - } - - // update the network - nNodesBef = Abc_NtkNodeNum(p->pNtk); -clk = clock(); - pObjNew = Lpk_Decompose( p, p->pNtk, p->vLeaves, pTruth, p->puSupps, p->pPars->nLutSize, - (int)pCut->nNodes - (int)pCut->nNodesDup - 1 + (int)(p->pPars->fZeroCost > 0), Required ); -p->timeEval += clock() - clk; - nNodesAft = Abc_NtkNodeNum(p->pNtk); - - // perform replacement - if ( pObjNew ) - { - int nGain = (int)pCut->nNodes - (int)pCut->nNodesDup - (nNodesAft - nNodesBef); - assert( nGain >= 1 - p->pPars->fZeroCost ); - assert( Abc_ObjLevel(pObjNew) <= Required ); -/* - if ( nGain <= 0 ) - { - int x = 0; - } - if ( Abc_ObjLevel(pObjNew) > Required ) - { - int x = 0; - } -*/ - p->nGainTotal += nGain; - p->nChanges++; - if ( p->pPars->fVeryVerbose ) - printf( "Performed resynthesis: Gain = %2d. Level = %2d. Req = %2d.\n", nGain, Abc_ObjLevel(pObjNew), Required ); - Abc_NtkUpdate( p->pObj, pObjNew, p->vLevels ); -//printf( "%3d : %d-%d=%d(%d) \n", p->nChanges, nNodesBef, Abc_NtkNodeNum(p->pNtk), nNodesBef-Abc_NtkNodeNum(p->pNtk), nGain ); - break; - } - } - return 1; -} - -/**Function************************************************************* - - Synopsis [Performs resynthesis for one network.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Lpk_Resynthesize( Abc_Ntk_t * pNtk, Lpk_Par_t * pPars ) -{ - ProgressBar * pProgress; - Lpk_Man_t * p; - Abc_Obj_t * pObj; - double Delta; - int i, Iter, nNodes, nNodesPrev, clk = clock(); - assert( Abc_NtkIsLogic(pNtk) ); - - // sweep dangling nodes as a preprocessing step - Abc_NtkSweep( pNtk, 0 ); - - // get the number of inputs - pPars->nLutSize = Abc_NtkGetFaninMax( pNtk ); - if ( pPars->nLutSize > 6 ) - pPars->nLutSize = 6; - if ( pPars->nLutSize < 3 ) - pPars->nLutSize = 3; - // adjust the number of crossbars based on LUT size - if ( pPars->nVarsShared > pPars->nLutSize - 2 ) - pPars->nVarsShared = pPars->nLutSize - 2; - // get the max number of LUTs tried - pPars->nVarsMax = pPars->nLutsMax * (pPars->nLutSize - 1) + 1; // V = N * (K-1) + 1 - while ( pPars->nVarsMax > 16 ) - { - pPars->nLutsMax--; - pPars->nVarsMax = pPars->nLutsMax * (pPars->nLutSize - 1) + 1; - - } - if ( pPars->fVerbose ) - { - printf( "Resynthesis for %d %d-LUTs with %d non-MFFC LUTs, %d crossbars, and %d-input cuts.\n", - pPars->nLutsMax, pPars->nLutSize, pPars->nLutsOver, pPars->nVarsShared, pPars->nVarsMax ); - } - - - // convert into the AIG - if ( !Abc_NtkToAig(pNtk) ) - { - fprintf( stdout, "Converting to BDD has failed.\n" ); - return 0; - } - assert( Abc_NtkHasAig(pNtk) ); - - // set the number of levels - Abc_NtkLevel( pNtk ); - Abc_NtkStartReverseLevels( pNtk, pPars->nGrowthLevel ); - - // start the manager - p = Lpk_ManStart( pPars ); - p->pNtk = pNtk; - p->nNodesTotal = Abc_NtkNodeNum(pNtk); - p->vLevels = Vec_VecStart( pNtk->LevelMax ); - if ( p->pPars->fSatur ) - p->vVisited = Vec_VecStart( 0 ); - if ( pPars->fVerbose ) - { - p->nTotalNets = Abc_NtkGetTotalFanins(pNtk); - p->nTotalNodes = Abc_NtkNodeNum(pNtk); - } - - // iterate over the network - nNodesPrev = p->nNodesTotal; - for ( Iter = 1; ; Iter++ ) - { - // expand storage for changed nodes - if ( p->pPars->fSatur ) - Vec_VecExpand( p->vVisited, Abc_NtkObjNumMax(pNtk) + 1 ); - - // consider all nodes - nNodes = Abc_NtkObjNumMax(pNtk); - if ( !pPars->fVeryVerbose ) - pProgress = Extra_ProgressBarStart( stdout, nNodes ); - Abc_NtkForEachNode( pNtk, pObj, i ) - { - // skip all except the final node - if ( pPars->fFirst ) - { - if ( !Abc_ObjIsCo(Abc_ObjFanout0(pObj)) ) - continue; - } - if ( i >= nNodes ) - break; - if ( !pPars->fVeryVerbose ) - Extra_ProgressBarUpdate( pProgress, i, NULL ); - // skip the nodes that did not change - if ( p->pPars->fSatur && !Lpk_NodeHasChanged(p, pObj->Id) ) - continue; - // resynthesize - p->pObj = pObj; - if ( p->pPars->fOldAlgo ) - Lpk_ResynthesizeNode( p ); - else - Lpk_ResynthesizeNodeNew( p ); - } - if ( !pPars->fVeryVerbose ) - Extra_ProgressBarStop( pProgress ); - - // check the increase - Delta = 100.00 * (nNodesPrev - Abc_NtkNodeNum(pNtk)) / p->nNodesTotal; - if ( Delta < 0.05 ) - break; - nNodesPrev = Abc_NtkNodeNum(pNtk); - if ( !p->pPars->fSatur ) - break; - - if ( pPars->fFirst ) - break; - } - Abc_NtkStopReverseLevels( pNtk ); - - if ( pPars->fVerbose ) - { -// Cloud_PrintInfo( p->pDsdMan->dd ); - p->nTotalNets2 = Abc_NtkGetTotalFanins(pNtk); - p->nTotalNodes2 = Abc_NtkNodeNum(pNtk); - printf( "Node gain = %5d. (%.2f %%) ", - p->nTotalNodes-p->nTotalNodes2, 100.0*(p->nTotalNodes-p->nTotalNodes2)/p->nTotalNodes ); - printf( "Edge gain = %5d. (%.2f %%) ", - p->nTotalNets-p->nTotalNets2, 100.0*(p->nTotalNets-p->nTotalNets2)/p->nTotalNets ); - printf( "Muxes = %4d. Dsds = %4d.", p->nMuxes, p->nDsds ); - printf( "\n" ); - printf( "Nodes = %5d (%3d) Cuts = %5d (%4d) Changes = %5d Iter = %2d Benefit = %d.\n", - p->nNodesTotal, p->nNodesOver, p->nCutsTotal, p->nCutsUseful, p->nChanges, Iter, p->nBenefited ); - - printf( "Non-DSD:" ); - for ( i = 3; i <= pPars->nVarsMax; i++ ) - if ( p->nBlocks[i] ) - printf( " %d=%d", i, p->nBlocks[i] ); - printf( "\n" ); - - p->timeTotal = clock() - clk; - p->timeEval = p->timeEval - p->timeMap; - p->timeOther = p->timeTotal - p->timeCuts - p->timeTruth - p->timeEval - p->timeMap; - PRTP( "Cuts ", p->timeCuts, p->timeTotal ); - PRTP( "Truth ", p->timeTruth, p->timeTotal ); - PRTP( "CSupps", p->timeSupps, p->timeTotal ); - PRTP( "Eval ", p->timeEval, p->timeTotal ); - PRTP( " MuxAn", p->timeEvalMuxAn, p->timeEval ); - PRTP( " MuxSp", p->timeEvalMuxSp, p->timeEval ); - PRTP( " DsdAn", p->timeEvalDsdAn, p->timeEval ); - PRTP( " DsdSp", p->timeEvalDsdSp, p->timeEval ); - PRTP( " Other", p->timeEval-p->timeEvalMuxAn-p->timeEvalMuxSp-p->timeEvalDsdAn-p->timeEvalDsdSp, p->timeEval ); - PRTP( "Map ", p->timeMap, p->timeTotal ); - PRTP( "Other ", p->timeOther, p->timeTotal ); - PRTP( "TOTAL ", p->timeTotal, p->timeTotal ); - } - - Lpk_ManStop( p ); - // check the resulting network - if ( !Abc_NtkCheck( pNtk ) ) - { - printf( "Lpk_Resynthesize: The network check has failed.\n" ); - return 0; - } - return 1; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/opt/lpk/lpkCut.c b/src/opt/lpk/lpkCut.c deleted file mode 100644 index facd330b..00000000 --- a/src/opt/lpk/lpkCut.c +++ /dev/null @@ -1,683 +0,0 @@ -/**CFile**************************************************************** - - FileName [lpkCut.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: lpkCut.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "lpkInt.h" -#include "cloud.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Computes the truth table of one cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -CloudNode * Lpk_CutTruthBdd_rec( CloudManager * dd, Hop_Man_t * pMan, Hop_Obj_t * pObj, int nVars ) -{ - CloudNode * pTruth, * pTruth0, * pTruth1; - assert( !Hop_IsComplement(pObj) ); - if ( pObj->pData ) - { - assert( ((unsigned)pObj->pData) & 0xffff0000 ); - return pObj->pData; - } - // get the plan for a new truth table - if ( Hop_ObjIsConst1(pObj) ) - pTruth = dd->one; - else - { - assert( Hop_ObjIsAnd(pObj) ); - // compute the truth tables of the fanins - pTruth0 = Lpk_CutTruthBdd_rec( dd, pMan, Hop_ObjFanin0(pObj), nVars ); - pTruth1 = Lpk_CutTruthBdd_rec( dd, pMan, Hop_ObjFanin1(pObj), nVars ); - pTruth0 = Cloud_NotCond( pTruth0, Hop_ObjFaninC0(pObj) ); - pTruth1 = Cloud_NotCond( pTruth1, Hop_ObjFaninC1(pObj) ); - // creat the truth table of the node - pTruth = Cloud_bddAnd( dd, pTruth0, pTruth1 ); - } - pObj->pData = pTruth; - return pTruth; -} - -/**Function************************************************************* - - Synopsis [Verifies that the factoring is correct.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -CloudNode * Lpk_CutTruthBdd( Lpk_Man_t * p, Lpk_Cut_t * pCut ) -{ - CloudManager * dd = p->pDsdMan->dd; - Hop_Man_t * pManHop = p->pNtk->pManFunc; - Hop_Obj_t * pObjHop; - Abc_Obj_t * pObj, * pFanin; - CloudNode * pTruth; - int i, k, iCount = 0; - -// return NULL; -// Lpk_NodePrintCut( p, pCut ); - // initialize the leaves - Lpk_CutForEachLeaf( p->pNtk, pCut, pObj, i ) - pObj->pCopy = (Abc_Obj_t *)dd->vars[pCut->nLeaves-1-i]; - - // construct truth table in the topological order - Lpk_CutForEachNodeReverse( p->pNtk, pCut, pObj, i ) - { - // get the local AIG - pObjHop = Hop_Regular(pObj->pData); - // clean the data field of the nodes in the AIG subgraph - Hop_ObjCleanData_rec( pObjHop ); - // set the initial truth tables at the fanins - Abc_ObjForEachFanin( pObj, pFanin, k ) - { - assert( ((unsigned)pFanin->pCopy) & 0xffff0000 ); - Hop_ManPi( pManHop, k )->pData = pFanin->pCopy; - } - // compute the truth table of internal nodes - pTruth = Lpk_CutTruthBdd_rec( dd, pManHop, pObjHop, pCut->nLeaves ); - if ( Hop_IsComplement(pObj->pData) ) - pTruth = Cloud_Not(pTruth); - // set the truth table at the node - pObj->pCopy = (Abc_Obj_t *)pTruth; - - } - -// Cloud_bddPrint( dd, pTruth ); -// printf( "Bdd size = %d. Total nodes = %d.\n", Cloud_DagSize( dd, pTruth ), dd->nNodesCur-dd->nVars-1 ); - return pTruth; -} - - -/**Function************************************************************* - - Synopsis [Computes the truth table of one cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -unsigned * Lpk_CutTruth_rec( Hop_Man_t * pMan, Hop_Obj_t * pObj, int nVars, Vec_Ptr_t * vTtNodes, int * piCount ) -{ - unsigned * pTruth, * pTruth0, * pTruth1; - assert( !Hop_IsComplement(pObj) ); - if ( pObj->pData ) - { - assert( ((unsigned)pObj->pData) & 0xffff0000 ); - return pObj->pData; - } - // get the plan for a new truth table - pTruth = Vec_PtrEntry( vTtNodes, (*piCount)++ ); - if ( Hop_ObjIsConst1(pObj) ) - Kit_TruthFill( pTruth, nVars ); - else - { - assert( Hop_ObjIsAnd(pObj) ); - // compute the truth tables of the fanins - pTruth0 = Lpk_CutTruth_rec( pMan, Hop_ObjFanin0(pObj), nVars, vTtNodes, piCount ); - pTruth1 = Lpk_CutTruth_rec( pMan, Hop_ObjFanin1(pObj), nVars, vTtNodes, piCount ); - // creat the truth table of the node - Kit_TruthAndPhase( pTruth, pTruth0, pTruth1, nVars, Hop_ObjFaninC0(pObj), Hop_ObjFaninC1(pObj) ); - } - pObj->pData = pTruth; - return pTruth; -} - -/**Function************************************************************* - - Synopsis [Computes the truth able of one cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -unsigned * Lpk_CutTruth( Lpk_Man_t * p, Lpk_Cut_t * pCut, int fInv ) -{ - Hop_Man_t * pManHop = p->pNtk->pManFunc; - Hop_Obj_t * pObjHop; - Abc_Obj_t * pObj, * pFanin; - unsigned * pTruth; - int i, k, iCount = 0; -// Lpk_NodePrintCut( p, pCut ); - assert( pCut->nNodes > 0 ); - - // initialize the leaves - Lpk_CutForEachLeaf( p->pNtk, pCut, pObj, i ) - pObj->pCopy = Vec_PtrEntry( p->vTtElems, fInv? pCut->nLeaves-1-i : i ); - - // construct truth table in the topological order - Lpk_CutForEachNodeReverse( p->pNtk, pCut, pObj, i ) - { - // get the local AIG - pObjHop = Hop_Regular(pObj->pData); - // clean the data field of the nodes in the AIG subgraph - Hop_ObjCleanData_rec( pObjHop ); - // set the initial truth tables at the fanins - Abc_ObjForEachFanin( pObj, pFanin, k ) - { - assert( ((unsigned)pFanin->pCopy) & 0xffff0000 ); - Hop_ManPi( pManHop, k )->pData = pFanin->pCopy; - } - // compute the truth table of internal nodes - pTruth = Lpk_CutTruth_rec( pManHop, pObjHop, pCut->nLeaves, p->vTtNodes, &iCount ); - if ( Hop_IsComplement(pObj->pData) ) - Kit_TruthNot( pTruth, pTruth, pCut->nLeaves ); - // set the truth table at the node - pObj->pCopy = (Abc_Obj_t *)pTruth; - } - - // make sure direct truth table is stored elsewhere (assuming the first call for direct truth!!!) - if ( fInv == 0 ) - { - pTruth = Vec_PtrEntry( p->vTtNodes, iCount++ ); - Kit_TruthCopy( pTruth, (unsigned *)pObj->pCopy, pCut->nLeaves ); - } - assert( iCount <= Vec_PtrSize(p->vTtNodes) ); - return pTruth; -} - - -/**Function************************************************************* - - Synopsis [Returns 1 if at least one entry has changed.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Lpk_NodeRecordImpact( Lpk_Man_t * p ) -{ - Lpk_Cut_t * pCut; - Vec_Ptr_t * vNodes = Vec_VecEntry( p->vVisited, p->pObj->Id ); - Abc_Obj_t * pNode; - int i, k; - // collect the nodes that impact the given node - Vec_PtrClear( vNodes ); - for ( i = 0; i < p->nCuts; i++ ) - { - pCut = p->pCuts + i; - for ( k = 0; k < (int)pCut->nLeaves; k++ ) - { - pNode = Abc_NtkObj( p->pNtk, pCut->pLeaves[k] ); - if ( pNode->fMarkC ) - continue; - pNode->fMarkC = 1; - Vec_PtrPush( vNodes, (void *)pNode->Id ); - Vec_PtrPush( vNodes, (void *)Abc_ObjFanoutNum(pNode) ); - } - } - // clear the marks - Vec_PtrForEachEntry( vNodes, pNode, i ) - { - pNode = Abc_NtkObj( p->pNtk, (int)pNode ); - pNode->fMarkC = 0; - i++; - } -//printf( "%d ", Vec_PtrSize(vNodes) ); -} - -/**Function************************************************************* - - Synopsis [Returns 1 if the cut has structural DSD.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Lpk_NodeCutsCheckDsd( Lpk_Man_t * p, Lpk_Cut_t * pCut ) -{ - Abc_Obj_t * pObj, * pFanin; - int i, k, nCands, fLeavesOnly, RetValue; - assert( pCut->nLeaves > 0 ); - // clear ref counters - memset( p->pRefs, 0, sizeof(int) * pCut->nLeaves ); - // mark cut leaves - Lpk_CutForEachLeaf( p->pNtk, pCut, pObj, i ) - { - assert( pObj->fMarkA == 0 ); - pObj->fMarkA = 1; - pObj->pCopy = (void *)i; - } - // ref leaves pointed from the internal nodes - nCands = 0; - Lpk_CutForEachNode( p->pNtk, pCut, pObj, i ) - { - fLeavesOnly = 1; - Abc_ObjForEachFanin( pObj, pFanin, k ) - if ( pFanin->fMarkA ) - p->pRefs[(int)pFanin->pCopy]++; - else - fLeavesOnly = 0; - if ( fLeavesOnly ) - p->pCands[nCands++] = pObj->Id; - } - // look at the nodes that only point to the leaves - RetValue = 0; - for ( i = 0; i < nCands; i++ ) - { - pObj = Abc_NtkObj( p->pNtk, p->pCands[i] ); - Abc_ObjForEachFanin( pObj, pFanin, k ) - { - assert( pFanin->fMarkA == 1 ); - if ( p->pRefs[(int)pFanin->pCopy] > 1 ) - break; - } - if ( k == Abc_ObjFaninNum(pObj) ) - { - RetValue = 1; - break; - } - } - // unmark cut leaves - Lpk_CutForEachLeaf( p->pNtk, pCut, pObj, i ) - pObj->fMarkA = 0; - return RetValue; -} - -/**Function************************************************************* - - Synopsis [Returns 1 if pDom is contained in pCut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline int Lpk_NodeCutsOneDominance( Lpk_Cut_t * pDom, Lpk_Cut_t * pCut ) -{ - int i, k; - for ( i = 0; i < (int)pDom->nLeaves; i++ ) - { - for ( k = 0; k < (int)pCut->nLeaves; k++ ) - if ( pDom->pLeaves[i] == pCut->pLeaves[k] ) - break; - if ( k == (int)pCut->nLeaves ) // node i in pDom is not contained in pCut - return 0; - } - // every node in pDom is contained in pCut - return 1; -} - -/**Function************************************************************* - - Synopsis [Check if the cut exists.] - - Description [Returns 1 if the cut exists.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Lpk_NodeCutsOneFilter( Lpk_Cut_t * pCuts, int nCuts, Lpk_Cut_t * pCutNew ) -{ - Lpk_Cut_t * pCut; - int i, k; - assert( pCutNew->uSign[0] || pCutNew->uSign[1] ); - // try to find the cut - for ( i = 0; i < nCuts; i++ ) - { - pCut = pCuts + i; - if ( pCut->nLeaves == 0 ) - continue; - if ( pCut->nLeaves == pCutNew->nLeaves ) - { - if ( pCut->uSign[0] == pCutNew->uSign[0] && pCut->uSign[1] == pCutNew->uSign[1] ) - { - for ( k = 0; k < (int)pCutNew->nLeaves; k++ ) - if ( pCut->pLeaves[k] != pCutNew->pLeaves[k] ) - break; - if ( k == (int)pCutNew->nLeaves ) - return 1; - } - continue; - } - if ( pCut->nLeaves < pCutNew->nLeaves ) - { - // skip the non-contained cuts - if ( (pCut->uSign[0] & pCutNew->uSign[0]) != pCut->uSign[0] ) - continue; - if ( (pCut->uSign[1] & pCutNew->uSign[1]) != pCut->uSign[1] ) - continue; - // check containment seriously - if ( Lpk_NodeCutsOneDominance( pCut, pCutNew ) ) - return 1; - continue; - } - // check potential containment of other cut - - // skip the non-contained cuts - if ( (pCut->uSign[0] & pCutNew->uSign[0]) != pCutNew->uSign[0] ) - continue; - if ( (pCut->uSign[1] & pCutNew->uSign[1]) != pCutNew->uSign[1] ) - continue; - // check containment seriously - if ( Lpk_NodeCutsOneDominance( pCutNew, pCut ) ) - pCut->nLeaves = 0; // removed - } - return 0; -} - -/**Function************************************************************* - - Synopsis [Prints the given cut.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Lpk_NodePrintCut( Lpk_Man_t * p, Lpk_Cut_t * pCut, int fLeavesOnly ) -{ - Abc_Obj_t * pObj; - int i; - if ( !fLeavesOnly ) - printf( "LEAVES:\n" ); - Lpk_CutForEachLeaf( p->pNtk, pCut, pObj, i ) - printf( "%d,", pObj->Id ); - if ( !fLeavesOnly ) - { - printf( "\nNODES:\n" ); - Lpk_CutForEachNode( p->pNtk, pCut, pObj, i ) - { - printf( "%d,", pObj->Id ); - assert( Abc_ObjIsNode(pObj) ); - } - printf( "\n" ); - } -} - -/**Function************************************************************* - - Synopsis [Set the cut signature.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Lpk_NodeCutSignature( Lpk_Cut_t * pCut ) -{ - unsigned i; - pCut->uSign[0] = pCut->uSign[1] = 0; - for ( i = 0; i < pCut->nLeaves; i++ ) - { - pCut->uSign[(pCut->pLeaves[i] & 32) > 0] |= (1 << (pCut->pLeaves[i] & 31)); - if ( i != pCut->nLeaves - 1 ) - assert( pCut->pLeaves[i] < pCut->pLeaves[i+1] ); - } -} - - -/**Function************************************************************* - - Synopsis [Computes the set of all cuts.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Lpk_NodeCutsOne( Lpk_Man_t * p, Lpk_Cut_t * pCut, int Node ) -{ - Lpk_Cut_t * pCutNew; - Abc_Obj_t * pObj, * pFanin; - int i, k, j, nLeavesNew; -/* - printf( "Exploring cut " ); - Lpk_NodePrintCut( p, pCut, 1 ); - printf( "with node %d\n", Node ); -*/ - // check if the cut can stand adding one more internal node - if ( pCut->nNodes == LPK_SIZE_MAX ) - return; - - // if the node is a PI, quit - pObj = Abc_NtkObj( p->pNtk, Node ); - if ( Abc_ObjIsCi(pObj) ) - return; - assert( Abc_ObjIsNode(pObj) ); -// assert( Abc_ObjFaninNum(pObj) <= p->pPars->nLutSize ); - - // if the node is not in the MFFC, check the limit - if ( !Abc_NodeIsTravIdCurrent(pObj) ) - { - if ( (int)pCut->nNodesDup == p->pPars->nLutsOver ) - return; - assert( (int)pCut->nNodesDup < p->pPars->nLutsOver ); - } - - // check the possibility of adding this node using the signature - nLeavesNew = pCut->nLeaves - 1; - Abc_ObjForEachFanin( pObj, pFanin, i ) - { - if ( (pCut->uSign[(pFanin->Id & 32) > 0] & (1 << (pFanin->Id & 31))) ) - continue; - if ( ++nLeavesNew > p->pPars->nVarsMax ) - return; - } - - // initialize the set of leaves to the nodes in the cut - assert( p->nCuts < LPK_CUTS_MAX ); - pCutNew = p->pCuts + p->nCuts; - pCutNew->nLeaves = 0; - for ( i = 0; i < (int)pCut->nLeaves; i++ ) - if ( pCut->pLeaves[i] != Node ) - pCutNew->pLeaves[pCutNew->nLeaves++] = pCut->pLeaves[i]; - - // add new nodes - Abc_ObjForEachFanin( pObj, pFanin, i ) - { - // find the place where this node belongs - for ( k = 0; k < (int)pCutNew->nLeaves; k++ ) - if ( pCutNew->pLeaves[k] >= pFanin->Id ) - break; - if ( k < (int)pCutNew->nLeaves && pCutNew->pLeaves[k] == pFanin->Id ) - continue; - // check if there is room - if ( (int)pCutNew->nLeaves == p->pPars->nVarsMax ) - return; - // move all the nodes - for ( j = pCutNew->nLeaves; j > k; j-- ) - pCutNew->pLeaves[j] = pCutNew->pLeaves[j-1]; - pCutNew->pLeaves[k] = pFanin->Id; - pCutNew->nLeaves++; - assert( pCutNew->nLeaves <= LPK_SIZE_MAX ); - - } - // skip the contained cuts - Lpk_NodeCutSignature( pCutNew ); - if ( Lpk_NodeCutsOneFilter( p->pCuts, p->nCuts, pCutNew ) ) - return; - - // update the set of internal nodes - assert( pCut->nNodes < LPK_SIZE_MAX ); - memcpy( pCutNew->pNodes, pCut->pNodes, pCut->nNodes * sizeof(int) ); - pCutNew->nNodes = pCut->nNodes; - pCutNew->nNodesDup = pCut->nNodesDup; - - // check if the node is already there - // if so, move the node to be the last - for ( i = 0; i < (int)pCutNew->nNodes; i++ ) - if ( pCutNew->pNodes[i] == Node ) - { - for ( k = i; k < (int)pCutNew->nNodes - 1; k++ ) - pCutNew->pNodes[k] = pCutNew->pNodes[k+1]; - pCutNew->pNodes[k] = Node; - break; - } - if ( i == (int)pCutNew->nNodes ) // new node - { - pCutNew->pNodes[ pCutNew->nNodes++ ] = Node; - pCutNew->nNodesDup += !Abc_NodeIsTravIdCurrent(pObj); - } - // the number of nodes does not exceed MFFC plus duplications - assert( pCutNew->nNodes <= p->nMffc + pCutNew->nNodesDup ); - // add the cut to storage - assert( p->nCuts < LPK_CUTS_MAX ); - p->nCuts++; -} - -/**Function************************************************************* - - Synopsis [Computes the set of all cuts.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Lpk_NodeCuts( Lpk_Man_t * p ) -{ - Lpk_Cut_t * pCut, * pCut2; - int i, k, Temp, nMffc, fChanges; - - // mark the MFFC of the node with the current trav ID - nMffc = p->nMffc = Abc_NodeMffcLabel( p->pObj ); - assert( nMffc > 0 ); - if ( nMffc == 1 ) - return 0; - - // initialize the first cut - pCut = p->pCuts; p->nCuts = 1; - pCut->nNodes = 0; - pCut->nNodesDup = 0; - pCut->nLeaves = 1; - pCut->pLeaves[0] = p->pObj->Id; - // assign the signature - Lpk_NodeCutSignature( pCut ); - - // perform the cut computation - for ( i = 0; i < p->nCuts; i++ ) - { - pCut = p->pCuts + i; - if ( pCut->nLeaves == 0 ) - continue; - - // try to expand the fanins of this cut - for ( k = 0; k < (int)pCut->nLeaves; k++ ) - { - // create a new cut - Lpk_NodeCutsOne( p, pCut, pCut->pLeaves[k] ); - // quit if the number of cuts has exceeded the limit - if ( p->nCuts == LPK_CUTS_MAX ) - break; - } - if ( p->nCuts == LPK_CUTS_MAX ) - break; - } - if ( p->nCuts == LPK_CUTS_MAX ) - p->nNodesOver++; - - // record the impact of this node - if ( p->pPars->fSatur ) - Lpk_NodeRecordImpact( p ); - - // compress the cuts by removing empty ones, those with negative Weight, and decomposable ones - p->nEvals = 0; - for ( i = 0; i < p->nCuts; i++ ) - { - pCut = p->pCuts + i; - if ( pCut->nLeaves < 2 ) - continue; - // compute the minimum number of LUTs needed to implement this cut - // V = N * (K-1) + 1 ~~~~~ N = Ceiling[(V-1)/(K-1)] = (V-1)/(K-1) + [(V-1)%(K-1) > 0] - pCut->nLuts = Lpk_LutNumLuts( pCut->nLeaves, p->pPars->nLutSize ); -// pCut->Weight = (float)1.0 * (pCut->nNodes - pCut->nNodesDup - 1) / pCut->nLuts; //p->pPars->nLutsMax; - pCut->Weight = (float)1.0 * (pCut->nNodes - pCut->nNodesDup) / pCut->nLuts; //p->pPars->nLutsMax; - if ( pCut->Weight <= 1.001 ) -// if ( pCut->Weight <= 0.999 ) - continue; - pCut->fHasDsd = Lpk_NodeCutsCheckDsd( p, pCut ); - if ( pCut->fHasDsd ) - continue; - p->pEvals[p->nEvals++] = i; - } - if ( p->nEvals == 0 ) - return 0; - - // sort the cuts by Weight - do { - fChanges = 0; - for ( i = 0; i < p->nEvals - 1; i++ ) - { - pCut = p->pCuts + p->pEvals[i]; - pCut2 = p->pCuts + p->pEvals[i+1]; - if ( pCut->Weight >= pCut2->Weight - 0.001 ) - continue; - Temp = p->pEvals[i]; - p->pEvals[i] = p->pEvals[i+1]; - p->pEvals[i+1] = Temp; - fChanges = 1; - } - } while ( fChanges ); -/* - for ( i = 0; i < p->nEvals; i++ ) - { - pCut = p->pCuts + p->pEvals[i]; - printf( "Cut %3d : W = %5.2f.\n", i, pCut->Weight ); - } - printf( "\n" ); -*/ - return 1; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/opt/lpk/lpkInt.h b/src/opt/lpk/lpkInt.h deleted file mode 100644 index 960599e4..00000000 --- a/src/opt/lpk/lpkInt.h +++ /dev/null @@ -1,246 +0,0 @@ -/**CFile**************************************************************** - - FileName [lpkInt.h] - - SystemName [ABC: Logic synthesis and verification system.] - - PackageName [Fast Boolean matching for LUT structures.] - - Synopsis [Internal declarations.] - - Author [Alan Mishchenko] - - Affiliation [UC Berkeley] - - Date [Ver. 1.0. Started - April 28, 2007.] - - Revision [$Id: lpkInt.h,v 1.00 2007/04/28 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#ifndef __LPK_INT_H__ -#define __LPK_INT_H__ - -#ifdef __cplusplus -extern "C" { -#endif - -//////////////////////////////////////////////////////////////////////// -/// INCLUDES /// -//////////////////////////////////////////////////////////////////////// - -#include "abc.h" -#include "kit.h" -#include "if.h" -#include "lpk.h" - -//////////////////////////////////////////////////////////////////////// -/// PARAMETERS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// BASIC TYPES /// -//////////////////////////////////////////////////////////////////////// - -#define LPK_SIZE_MAX 24 // the largest size of the function -#define LPK_CUTS_MAX 512 // the largest number of cuts considered - -typedef struct Lpk_Man_t_ Lpk_Man_t; -typedef struct Lpk_Cut_t_ Lpk_Cut_t; - -struct Lpk_Cut_t_ -{ - unsigned nLeaves : 6; // (L) the number of leaves - unsigned nNodes : 6; // (M) the number of nodes - unsigned nNodesDup : 6; // (Q) nodes outside of MFFC - unsigned nLuts : 6; // (N) the number of LUTs to try - unsigned unused : 6; // unused - unsigned fHasDsd : 1; // set to 1 if the cut has structural DSD (and so cannot be used) - unsigned fMark : 1; // multipurpose mark - unsigned uSign[2]; // the signature - float Weight; // the weight of the cut: (M - Q)/N(V) (the larger the better) - int Gain; // the gain achieved using this cut - int pLeaves[LPK_SIZE_MAX]; // the leaves of the cut - int pNodes[LPK_SIZE_MAX]; // the nodes of the cut -}; - -struct Lpk_Man_t_ -{ - // parameters - Lpk_Par_t * pPars; // the set of parameters - // current representation - Abc_Ntk_t * pNtk; // the network - Abc_Obj_t * pObj; // the node to resynthesize - // cut representation - int nMffc; // the size of MFFC of the node - int nCuts; // the total number of cuts - int nCutsMax; // the largest possible number of cuts - int nEvals; // the number of good cuts - Lpk_Cut_t pCuts[LPK_CUTS_MAX]; // the storage for cuts - int pEvals[LPK_CUTS_MAX]; // the good cuts - // visited nodes - Vec_Vec_t * vVisited; - // mapping manager - If_Man_t * pIfMan; - Vec_Int_t * vCover; - Vec_Vec_t * vLevels; - // temporary variables - int fCofactoring; // working in the cofactoring mode - int fCalledOnce; // limits the depth of MUX cofactoring - int nCalledSRed; // the number of called to SRed - int pRefs[LPK_SIZE_MAX]; // fanin reference counters - int pCands[LPK_SIZE_MAX]; // internal nodes pointing only to the leaves - Vec_Ptr_t * vLeaves; - // truth table representation - Vec_Ptr_t * vTtElems; // elementary truth tables - Vec_Ptr_t * vTtNodes; // storage for temporary truth tables of the nodes - Vec_Int_t * vMemory; - Vec_Int_t * vBddDir; - Vec_Int_t * vBddInv; - unsigned puSupps[32]; // the supports of the cofactors - unsigned * ppTruths[5][16]; - // variable sets - Vec_Int_t * vSets[8]; - Kit_DsdMan_t* pDsdMan; - // statistics - int nNodesTotal; // total number of nodes - int nNodesOver; // nodes with cuts over the limit - int nCutsTotal; // total number of cuts - int nCutsUseful; // useful cuts - int nGainTotal; // the gain in LUTs - int nChanges; // the number of changed nodes - int nBenefited; // the number of gainful that benefited from decomposition - int nMuxes; - int nDsds; - int nTotalNets; - int nTotalNets2; - int nTotalNodes; - int nTotalNodes2; - // counter of non-DSD blocks - int nBlocks[17]; - // runtime - int timeCuts; - int timeTruth; - int timeSupps; - int timeTruth2; - int timeTruth3; - int timeEval; - int timeMap; - int timeOther; - int timeTotal; - // runtime of eval - int timeEvalMuxAn; - int timeEvalMuxSp; - int timeEvalDsdAn; - int timeEvalDsdSp; - -}; - - -// internal representation of the function to be decomposed -typedef struct Lpk_Fun_t_ Lpk_Fun_t; -struct Lpk_Fun_t_ -{ - Vec_Ptr_t * vNodes; // the array of leaves and decomposition nodes - unsigned Id : 7; // the ID of this node - unsigned nVars : 5; // the number of variables - unsigned nLutK : 4; // the number of LUT inputs - unsigned nAreaLim : 5; // the area limit (the largest allowed) - unsigned nDelayLim : 9; // the delay limit (the largest allowed) - unsigned fSupports : 1; // supports of cofactors were precomputed - unsigned fMark : 1; // marks the MUX-based dec - unsigned uSupp; // the support of this component - unsigned puSupps[32]; // the supports of the cofactors - char pDelays[16]; // the delays of the inputs - char pFanins[16]; // the fanins of this function - unsigned pTruth[0]; // the truth table (contains room for three truth tables) -}; - -// preliminary decomposition result -typedef struct Lpk_Res_t_ Lpk_Res_t; -struct Lpk_Res_t_ -{ - int nBSVars; // the number of bound set variables - unsigned BSVars; // the bound set - int nCofVars; // the number of cofactoring variables - char pCofVars[4]; // the cofactoring variables - int nSuppSizeS; // support size of the smaller (decomposed) function - int nSuppSizeL; // support size of the larger (composition) function - int DelayEst; // estimated delay of the decomposition - int AreaEst; // estimated area of the decomposition - int Variable; // variable in MUX decomposition - int Polarity; // polarity in MUX decomposition -}; - -static inline int Lpk_LutNumVars( int nLutsLim, int nLutK ) { return nLutsLim * (nLutK - 1) + 1; } -static inline int Lpk_LutNumLuts( int nVarsMax, int nLutK ) { return (nVarsMax - 1) / (nLutK - 1) + (int)((nVarsMax - 1) % (nLutK - 1) > 0); } -static inline unsigned * Lpk_FunTruth( Lpk_Fun_t * p, int Num ) { assert( Num < 3 ); return p->pTruth + Kit_TruthWordNum(p->nVars) * Num; } - -//////////////////////////////////////////////////////////////////////// -/// MACRO DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// ITERATORS /// -//////////////////////////////////////////////////////////////////////// - -#define Lpk_CutForEachLeaf( pNtk, pCut, pObj, i ) \ - for ( i = 0; (i < (int)(pCut)->nLeaves) && (((pObj) = Abc_NtkObj(pNtk, (pCut)->pLeaves[i])), 1); i++ ) -#define Lpk_CutForEachNode( pNtk, pCut, pObj, i ) \ - for ( i = 0; (i < (int)(pCut)->nNodes) && (((pObj) = Abc_NtkObj(pNtk, (pCut)->pNodes[i])), 1); i++ ) -#define Lpk_CutForEachNodeReverse( pNtk, pCut, pObj, i ) \ - for ( i = (int)(pCut)->nNodes - 1; (i >= 0) && (((pObj) = Abc_NtkObj(pNtk, (pCut)->pNodes[i])), 1); i-- ) -#define Lpk_SuppForEachVar( Supp, Var )\ - for ( Var = 0; Var < 16; Var++ )\ - if ( !(Supp & (1<nLutsMax <= 16 ); - assert( pPars->nVarsMax > 0 && pPars->nVarsMax <= 16 ); - p = ALLOC( Lpk_Man_t, 1 ); - memset( p, 0, sizeof(Lpk_Man_t) ); - p->pPars = pPars; - p->nCutsMax = LPK_CUTS_MAX; - p->vTtElems = Vec_PtrAllocTruthTables( pPars->nVarsMax ); - p->vTtNodes = Vec_PtrAllocSimInfo( 1024, Abc_TruthWordNum(pPars->nVarsMax) ); - p->vCover = Vec_IntAlloc( 1 << 12 ); - p->vLeaves = Vec_PtrAlloc( 32 ); - for ( i = 0; i < 8; i++ ) - p->vSets[i] = Vec_IntAlloc(100); - p->pDsdMan = Kit_DsdManAlloc( pPars->nVarsMax, 64 ); - p->vMemory = Vec_IntAlloc( 1024 * 32 ); - p->vBddDir = Vec_IntAlloc( 256 ); - p->vBddInv = Vec_IntAlloc( 256 ); - // allocate temporary storage for truth tables - nWords = Kit_TruthWordNum(pPars->nVarsMax); - p->ppTruths[0][0] = ALLOC( unsigned, 32 * nWords ); - p->ppTruths[1][0] = p->ppTruths[0][0] + 1 * nWords; - for ( i = 1; i < 2; i++ ) - p->ppTruths[1][i] = p->ppTruths[1][0] + i * nWords; - p->ppTruths[2][0] = p->ppTruths[1][0] + 2 * nWords; - for ( i = 1; i < 4; i++ ) - p->ppTruths[2][i] = p->ppTruths[2][0] + i * nWords; - p->ppTruths[3][0] = p->ppTruths[2][0] + 4 * nWords; - for ( i = 1; i < 8; i++ ) - p->ppTruths[3][i] = p->ppTruths[3][0] + i * nWords; - p->ppTruths[4][0] = p->ppTruths[3][0] + 8 * nWords; - for ( i = 1; i < 16; i++ ) - p->ppTruths[4][i] = p->ppTruths[4][0] + i * nWords; - return p; -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Lpk_ManStop( Lpk_Man_t * p ) -{ - int i; - free( p->ppTruths[0][0] ); - Vec_IntFree( p->vBddDir ); - Vec_IntFree( p->vBddInv ); - Vec_IntFree( p->vMemory ); - Kit_DsdManFree( p->pDsdMan ); - for ( i = 0; i < 8; i++ ) - Vec_IntFree(p->vSets[i]); - if ( p->pIfMan ) - { - void * pPars = p->pIfMan->pPars; - If_ManStop( p->pIfMan ); - free( pPars ); - } - if ( p->vLevels ) - Vec_VecFree( p->vLevels ); - if ( p->vVisited ) - Vec_VecFree( p->vVisited ); - Vec_PtrFree( p->vLeaves ); - Vec_IntFree( p->vCover ); - Vec_PtrFree( p->vTtElems ); - Vec_PtrFree( p->vTtNodes ); - free( p ); -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/opt/lpk/lpkMap.c b/src/opt/lpk/lpkMap.c deleted file mode 100644 index 698aeea1..00000000 --- a/src/opt/lpk/lpkMap.c +++ /dev/null @@ -1,205 +0,0 @@ -/**CFile**************************************************************** - - FileName [lpkMap.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: lpkMap.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "lpkInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Transforms the decomposition graph into the AIG.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -If_Obj_t * Lpk_MapPrimeInternal( If_Man_t * pIfMan, Kit_Graph_t * pGraph ) -{ - Kit_Node_t * pNode; - If_Obj_t * pAnd0, * pAnd1; - int i; - // check for constant function - if ( Kit_GraphIsConst(pGraph) ) - return If_ManConst1(pIfMan); - // check for a literal - if ( Kit_GraphIsVar(pGraph) ) - return Kit_GraphVar(pGraph)->pFunc; - // build the AIG nodes corresponding to the AND gates of the graph - Kit_GraphForEachNode( pGraph, pNode, i ) - { - pAnd0 = Kit_GraphNode(pGraph, pNode->eEdge0.Node)->pFunc; - pAnd1 = Kit_GraphNode(pGraph, pNode->eEdge1.Node)->pFunc; - pNode->pFunc = If_ManCreateAnd( pIfMan, - If_NotCond( If_Regular(pAnd0), If_IsComplement(pAnd0) ^ pNode->eEdge0.fCompl ), - If_NotCond( If_Regular(pAnd1), If_IsComplement(pAnd1) ^ pNode->eEdge1.fCompl ) ); - } - return pNode->pFunc; -} - -/**Function************************************************************* - - Synopsis [Strashes one logic node using its SOP.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -If_Obj_t * Lpk_MapPrime( Lpk_Man_t * p, unsigned * pTruth, int nVars, If_Obj_t ** ppLeaves ) -{ - Kit_Graph_t * pGraph; - Kit_Node_t * pNode; - If_Obj_t * pRes; - int i; - // derive the factored form - pGraph = Kit_TruthToGraph( pTruth, nVars, p->vCover ); - if ( pGraph == NULL ) - return NULL; - // collect the fanins - Kit_GraphForEachLeaf( pGraph, pNode, i ) - pNode->pFunc = ppLeaves[i]; - // perform strashing - pRes = Lpk_MapPrimeInternal( p->pIfMan, pGraph ); - pRes = If_NotCond( pRes, Kit_GraphIsComplement(pGraph) ); - Kit_GraphFree( pGraph ); - return pRes; -} - -/**Function************************************************************* - - Synopsis [Prepares the mapping manager.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -If_Obj_t * Lpk_MapTree_rec( Lpk_Man_t * p, Kit_DsdNtk_t * pNtk, If_Obj_t ** ppLeaves, int iLit, If_Obj_t * pResult ) -{ - Kit_DsdObj_t * pObj; - If_Obj_t * pObjNew = NULL, * pObjNew2 = NULL, * pFansNew[16]; - unsigned i, iLitFanin; - - assert( iLit >= 0 ); - - // consider the case of a gate - pObj = Kit_DsdNtkObj( pNtk, Kit_DsdLit2Var(iLit) ); - if ( pObj == NULL ) - { - pObjNew = ppLeaves[Kit_DsdLit2Var(iLit)]; - return If_NotCond( pObjNew, Kit_DsdLitIsCompl(iLit) ); - } - if ( pObj->Type == KIT_DSD_CONST1 ) - { - return If_NotCond( If_ManConst1(p->pIfMan), Kit_DsdLitIsCompl(iLit) ); - } - if ( pObj->Type == KIT_DSD_VAR ) - { - pObjNew = ppLeaves[Kit_DsdLit2Var(pObj->pFans[0])]; - return If_NotCond( pObjNew, Kit_DsdLitIsCompl(iLit) ^ Kit_DsdLitIsCompl(pObj->pFans[0]) ); - } - if ( pObj->Type == KIT_DSD_AND ) - { - assert( pObj->nFans == 2 ); - pFansNew[0] = Lpk_MapTree_rec( p, pNtk, ppLeaves, pObj->pFans[0], NULL ); - pFansNew[1] = pResult? pResult : Lpk_MapTree_rec( p, pNtk, ppLeaves, pObj->pFans[1], NULL ); - if ( pFansNew[0] == NULL || pFansNew[1] == NULL ) - return NULL; - pObjNew = If_ManCreateAnd( p->pIfMan, pFansNew[0], pFansNew[1] ); - return If_NotCond( pObjNew, Kit_DsdLitIsCompl(iLit) ); - } - if ( pObj->Type == KIT_DSD_XOR ) - { - int fCompl = Kit_DsdLitIsCompl(iLit); - assert( pObj->nFans == 2 ); - pFansNew[0] = Lpk_MapTree_rec( p, pNtk, ppLeaves, pObj->pFans[0], NULL ); - pFansNew[1] = pResult? pResult : Lpk_MapTree_rec( p, pNtk, ppLeaves, pObj->pFans[1], NULL ); - if ( pFansNew[0] == NULL || pFansNew[1] == NULL ) - return NULL; - fCompl ^= If_IsComplement(pFansNew[0]) ^ If_IsComplement(pFansNew[1]); - pObjNew = If_ManCreateXor( p->pIfMan, If_Regular(pFansNew[0]), If_Regular(pFansNew[1]) ); - return If_NotCond( pObjNew, fCompl ); - } - assert( pObj->Type == KIT_DSD_PRIME ); - p->nBlocks[pObj->nFans]++; - - // solve for the inputs - Kit_DsdObjForEachFanin( pNtk, pObj, iLitFanin, i ) - { - if ( i == 0 ) - pFansNew[i] = pResult? pResult : Lpk_MapTree_rec( p, pNtk, ppLeaves, iLitFanin, NULL ); - else - pFansNew[i] = Lpk_MapTree_rec( p, pNtk, ppLeaves, iLitFanin, NULL ); - if ( pFansNew[i] == NULL ) - return NULL; - } -/* - if ( !p->fCofactoring && p->pPars->nVarsShared > 0 && (int)pObj->nFans > p->pPars->nLutSize ) - { - pObjNew = Lpk_MapTreeMulti( p, Kit_DsdObjTruth(pObj), pObj->nFans, pFansNew ); - return If_NotCond( pObjNew, Kit_DsdLitIsCompl(iLit) ); - } -*/ -/* - if ( (int)pObj->nFans > p->pPars->nLutSize ) - { - pObjNew2 = Lpk_MapTreeMux_rec( p, Kit_DsdObjTruth(pObj), pObj->nFans, pFansNew ); -// if ( pObjNew2 ) -// return If_NotCond( pObjNew2, Kit_DsdLitIsCompl(iLit) ); - } -*/ - - // find best cofactoring variable - if ( p->pPars->nVarsShared > 0 && (int)pObj->nFans > p->pPars->nLutSize ) - { - pObjNew2 = Lpk_MapSuppRedDec_rec( p, Kit_DsdObjTruth(pObj), pObj->nFans, pFansNew ); - if ( pObjNew2 ) - return If_NotCond( pObjNew2, Kit_DsdLitIsCompl(iLit) ); - } - - pObjNew = Lpk_MapPrime( p, Kit_DsdObjTruth(pObj), pObj->nFans, pFansNew ); - - // add choice - if ( pObjNew && pObjNew2 ) - { - If_ObjSetChoice( If_Regular(pObjNew), If_Regular(pObjNew2) ); - If_ManCreateChoice( p->pIfMan, If_Regular(pObjNew) ); - } - return If_NotCond( pObjNew, Kit_DsdLitIsCompl(iLit) ); -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/opt/lpk/lpkMulti.c b/src/opt/lpk/lpkMulti.c deleted file mode 100644 index 82cf3578..00000000 --- a/src/opt/lpk/lpkMulti.c +++ /dev/null @@ -1,495 +0,0 @@ -/**CFile**************************************************************** - - FileName [lpkMulti.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: lpkMulti.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "lpkInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Records variable order.] - - Description [Increaments Order[x][y] by 1 if x should be above y in the DSD.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Lpk_CreateVarOrder( Kit_DsdNtk_t * pNtk, char pTable[][16] ) -{ - Kit_DsdObj_t * pObj; - unsigned uSuppFanins, k; - int Above[16], Below[16]; - int nAbove, nBelow, iFaninLit, i, x, y; - // iterate through the nodes - Kit_DsdNtkForEachObj( pNtk, pObj, i ) - { - // collect fanin support of this node - nAbove = 0; - uSuppFanins = 0; - Kit_DsdObjForEachFanin( pNtk, pObj, iFaninLit, k ) - { - if ( Kit_DsdLitIsLeaf( pNtk, iFaninLit ) ) - Above[nAbove++] = Kit_DsdLit2Var(iFaninLit); - else - uSuppFanins |= Kit_DsdLitSupport( pNtk, iFaninLit ); - } - // find the below variables - nBelow = 0; - for ( y = 0; y < 16; y++ ) - if ( uSuppFanins & (1 << y) ) - Below[nBelow++] = y; - // create all pairs - for ( x = 0; x < nAbove; x++ ) - for ( y = 0; y < nBelow; y++ ) - pTable[Above[x]][Below[y]]++; - } -} - -/**Function************************************************************* - - Synopsis [Creates commmon variable order.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Lpk_CreateCommonOrder( char pTable[][16], int piCofVar[], int nCBars, int pPrios[], int nVars, int fVerbose ) -{ - int Score[16] = {0}, pPres[16]; - int i, y, x, iVarBest, ScoreMax, PrioCount; - - // mark the present variables - for ( i = 0; i < nVars; i++ ) - pPres[i] = 1; - // remove cofactored variables - for ( i = 0; i < nCBars; i++ ) - pPres[piCofVar[i]] = 0; - - // compute scores for each leaf - for ( i = 0; i < nVars; i++ ) - { - if ( pPres[i] == 0 ) - continue; - for ( y = 0; y < nVars; y++ ) - Score[i] += pTable[i][y]; - for ( x = 0; x < nVars; x++ ) - Score[i] -= pTable[x][i]; - } - - // print the scores - if ( fVerbose ) - { - printf( "Scores: " ); - for ( i = 0; i < nVars; i++ ) - printf( "%c=%d ", 'a'+i, Score[i] ); - printf( " " ); - printf( "Prios: " ); - } - - // derive variable priority - // variables with equal score receive the same priority - for ( i = 0; i < nVars; i++ ) - pPrios[i] = 16; - - // iterate until variables remain - for ( PrioCount = 1; ; PrioCount++ ) - { - // find the present variable with the highest score - iVarBest = -1; - ScoreMax = -100000; - for ( i = 0; i < nVars; i++ ) - { - if ( pPres[i] == 0 ) - continue; - if ( ScoreMax < Score[i] ) - { - ScoreMax = Score[i]; - iVarBest = i; - } - } - if ( iVarBest == -1 ) - break; - // give the next priority to all vars having this score - if ( fVerbose ) - printf( "%d=", PrioCount ); - for ( i = 0; i < nVars; i++ ) - { - if ( pPres[i] == 0 ) - continue; - if ( Score[i] == ScoreMax ) - { - pPrios[i] = PrioCount; - pPres[i] = 0; - if ( fVerbose ) - printf( "%c", 'a'+i ); - } - } - if ( fVerbose ) - printf( " " ); - } - if ( fVerbose ) - printf( "\n" ); -} - -/**Function************************************************************* - - Synopsis [Finds components with the highest priority.] - - Description [Returns the number of components selected.] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -int Lpk_FindHighest( Kit_DsdNtk_t ** ppNtks, int * piLits, int nSize, int * pPrio, int * pDecision ) -{ - Kit_DsdObj_t * pObj; - unsigned uSupps[8], uSuppFanin, uSuppTotal, uSuppLarge; - int i, pTriv[8], PrioMin, iVarMax, nComps, fOneNonTriv; - - // find individual support and total support - uSuppTotal = 0; - for ( i = 0; i < nSize; i++ ) - { - pTriv[i] = 1; - if ( piLits[i] < 0 ) - uSupps[i] = 0; - else if ( Kit_DsdLitIsLeaf(ppNtks[i], piLits[i]) ) - uSupps[i] = Kit_DsdLitSupport( ppNtks[i], piLits[i] ); - else - { - pObj = Kit_DsdNtkObj( ppNtks[i], Kit_DsdLit2Var(piLits[i]) ); - if ( pObj->Type == KIT_DSD_PRIME ) - { - pTriv[i] = 0; - uSuppFanin = Kit_DsdLitSupport( ppNtks[i], pObj->pFans[0] ); - } - else - { - assert( pObj->nFans == 2 ); - if ( !Kit_DsdLitIsLeaf(ppNtks[i], pObj->pFans[0]) ) - pTriv[i] = 0; - uSuppFanin = Kit_DsdLitSupport( ppNtks[i], pObj->pFans[1] ); - } - uSupps[i] = Kit_DsdLitSupport( ppNtks[i], piLits[i] ) & ~uSuppFanin; - } - assert( uSupps[i] <= 0xFFFF ); - uSuppTotal |= uSupps[i]; - } - if ( uSuppTotal == 0 ) - return 0; - - // find one support variable with the highest priority - PrioMin = ABC_INFINITY; - iVarMax = -1; - for ( i = 0; i < 16; i++ ) - if ( uSuppTotal & (1 << i) ) - if ( PrioMin > pPrio[i] ) - { - PrioMin = pPrio[i]; - iVarMax = i; - } - assert( iVarMax != -1 ); - - // select components, which have this variable - nComps = 0; - fOneNonTriv = 0; - uSuppLarge = 0; - for ( i = 0; i < nSize; i++ ) - if ( uSupps[i] & (1<pIfMan) ); - - // iterate over the nodes - if ( p->pPars->fVeryVerbose ) - printf( "Decision: " ); - for ( i = 0; i < nSize; i++ ) - { - if ( pDecision[i] ) - { - if ( p->pPars->fVeryVerbose ) - printf( "%d ", i ); - assert( piLits[i] >= 0 ); - pObj = Kit_DsdNtkObj( ppNtks[i], Kit_DsdLit2Var(piLits[i]) ); - if ( pObj == NULL ) - piLitsNew[i] = -2; - else if ( pObj->Type == KIT_DSD_PRIME ) - piLitsNew[i] = pObj->pFans[0]; - else - piLitsNew[i] = pObj->pFans[1]; - } - else - piLitsNew[i] = piLits[i]; - } - if ( p->pPars->fVeryVerbose ) - printf( "\n" ); - - // call again - pResPrev = Lpk_MapTreeMulti_rec( p, ppNtks, piLitsNew, piCofVar, nCBars, ppLeaves, nLeaves, pPrio ); - - // create new set of nodes - for ( i = 0; i < nSize; i++ ) - { - if ( pDecision[i] ) - pObjsNew[nCBars][i] = Lpk_MapTree_rec( p, ppNtks[i], ppLeaves, piLits[i], pResPrev ); - else if ( piLits[i] == -1 ) - pObjsNew[nCBars][i] = If_ManConst1(p->pIfMan); - else if ( piLits[i] == -2 ) - pObjsNew[nCBars][i] = If_Not( If_ManConst1(p->pIfMan) ); - else - pObjsNew[nCBars][i] = pResPrev; - } - - // create MUX using these outputs - for ( k = nCBars; k > 0; k-- ) - { - nSize /= 2; - for ( i = 0; i < nSize; i++ ) - pObjsNew[k-1][i] = If_ManCreateMux( p->pIfMan, pObjsNew[k][2*i+0], pObjsNew[k][2*i+1], ppLeaves[piCofVar[k-1]] ); - } - assert( nSize == 1 ); - return pObjsNew[0][0]; -} - -/**Function************************************************************* - - Synopsis [Prepares the mapping manager.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -If_Obj_t * Lpk_MapTreeMulti( Lpk_Man_t * p, unsigned * pTruth, int nVars, If_Obj_t ** ppLeaves ) -{ - static Counter = 0; - If_Obj_t * pResult; - Kit_DsdNtk_t * ppNtks[8] = {0}, * pTemp; - Kit_DsdObj_t * pRoot; - int piCofVar[4], pPrios[16], pFreqs[16] = {0}, piLits[16]; - int i, k, nCBars, nSize, nMemSize; - unsigned * ppCofs[4][8], uSupport; - char pTable[16][16] = {0}; - int fVerbose = p->pPars->fVeryVerbose; - - Counter++; -// printf( "Run %d.\n", Counter ); - - // allocate storage for cofactors - nMemSize = Kit_TruthWordNum(nVars); - ppCofs[0][0] = ALLOC( unsigned, 32 * nMemSize ); - nSize = 0; - for ( i = 0; i < 4; i++ ) - for ( k = 0; k < 8; k++ ) - ppCofs[i][k] = ppCofs[0][0] + nMemSize * nSize++; - assert( nSize == 32 ); - - // find the best cofactoring variables - nCBars = Kit_DsdCofactoring( pTruth, nVars, piCofVar, p->pPars->nVarsShared, 0 ); -// nCBars = 2; -// piCofVar[0] = 0; -// piCofVar[1] = 1; - - - // copy the function - Kit_TruthCopy( ppCofs[0][0], pTruth, nVars ); - - // decompose w.r.t. these variables - for ( k = 0; k < nCBars; k++ ) - { - nSize = (1 << k); - for ( i = 0; i < nSize; i++ ) - { - Kit_TruthCofactor0New( ppCofs[k+1][2*i+0], ppCofs[k][i], nVars, piCofVar[k] ); - Kit_TruthCofactor1New( ppCofs[k+1][2*i+1], ppCofs[k][i], nVars, piCofVar[k] ); - } - } - nSize = (1 << nCBars); - // compute DSD networks - for ( i = 0; i < nSize; i++ ) - { - ppNtks[i] = Kit_DsdDecompose( ppCofs[nCBars][i], nVars ); - ppNtks[i] = Kit_DsdExpand( pTemp = ppNtks[i] ); - Kit_DsdNtkFree( pTemp ); - if ( fVerbose ) - { - printf( "Cof%d%d: ", nCBars, i ); - Kit_DsdPrint( stdout, ppNtks[i] ); - } - } - - // compute variable frequences - for ( i = 0; i < nSize; i++ ) - { - uSupport = Kit_TruthSupport( ppCofs[nCBars][i], nVars ); - for ( k = 0; k < nVars; k++ ) - if ( uSupport & (1<pSupps[0] <= 0xFFFF ); - // undec nodes should be rotated in such a way that the first input has as many shared inputs as possible - Kit_DsdRotate( ppNtks[i], pFreqs ); - // print the resulting networks - if ( fVerbose ) - { - printf( "Cof%d%d: ", nCBars, i ); - Kit_DsdPrint( stdout, ppNtks[i] ); - } - } - - for ( i = 0; i < nSize; i++ ) - { - // collect the roots - pRoot = Kit_DsdNtkRoot(ppNtks[i]); - if ( pRoot->Type == KIT_DSD_CONST1 ) - piLits[i] = Kit_DsdLitIsCompl(ppNtks[i]->Root)? -2: -1; - else if ( pRoot->Type == KIT_DSD_VAR ) - piLits[i] = Kit_DsdLitNotCond( pRoot->pFans[0], Kit_DsdLitIsCompl(ppNtks[i]->Root) ); - else - piLits[i] = ppNtks[i]->Root; - } - - - // recursively construct AIG for mapping - p->fCofactoring = 1; - pResult = Lpk_MapTreeMulti_rec( p, ppNtks, piLits, piCofVar, nCBars, ppLeaves, nVars, pPrios ); - p->fCofactoring = 0; - - if ( fVerbose ) - printf( "\n" ); - - // verify the transformations - nSize = (1 << nCBars); - for ( i = 0; i < nSize; i++ ) - Kit_DsdTruth( ppNtks[i], ppCofs[nCBars][i] ); - // mux the truth tables - for ( k = nCBars-1; k >= 0; k-- ) - { - nSize = (1 << k); - for ( i = 0; i < nSize; i++ ) - Kit_TruthMuxVar( ppCofs[k][i], ppCofs[k+1][2*i+0], ppCofs[k+1][2*i+1], nVars, piCofVar[k] ); - } - if ( !Extra_TruthIsEqual( pTruth, ppCofs[0][0], nVars ) ) - printf( "Verification failed.\n" ); - - - // free the networks - for ( i = 0; i < 8; i++ ) - if ( ppNtks[i] ) - Kit_DsdNtkFree( ppNtks[i] ); - free( ppCofs[0][0] ); - - return pResult; -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - 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 /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/opt/lpk/lpkSets.c b/src/opt/lpk/lpkSets.c deleted file mode 100644 index 90e46863..00000000 --- a/src/opt/lpk/lpkSets.c +++ /dev/null @@ -1,440 +0,0 @@ -/**CFile**************************************************************** - - FileName [lpkSets.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: lpkSets.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "lpkInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -typedef struct Lpk_Set_t_ Lpk_Set_t; -struct Lpk_Set_t_ -{ - char iVar; // the cofactoring variable - char Over; // the overlap in supports - char SRed; // the support reduction - char Size; // the size of the boundset - unsigned uSubset0; // the first subset (with removed) - unsigned uSubset1; // the second subset (with removed) -}; - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [Recursively computes decomposable subsets.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -unsigned Lpk_ComputeSets_rec( Kit_DsdNtk_t * p, int iLit, Vec_Int_t * vSets ) -{ - unsigned i, iLitFanin, uSupport, uSuppCur; - Kit_DsdObj_t * pObj; - // consider the case of simple gate - pObj = Kit_DsdNtkObj( p, Kit_DsdLit2Var(iLit) ); - if ( pObj == NULL ) - return (1 << Kit_DsdLit2Var(iLit)); - if ( pObj->Type == KIT_DSD_AND || pObj->Type == KIT_DSD_XOR ) - { - unsigned uSupps[16], Limit, s; - uSupport = 0; - Kit_DsdObjForEachFanin( p, pObj, iLitFanin, i ) - { - uSupps[i] = Lpk_ComputeSets_rec( p, iLitFanin, vSets ); - uSupport |= uSupps[i]; - } - // create all subsets, except empty and full - Limit = (1 << pObj->nFans) - 1; - for ( s = 1; s < Limit; s++ ) - { - uSuppCur = 0; - for ( i = 0; i < pObj->nFans; i++ ) - if ( s & (1 << i) ) - uSuppCur |= uSupps[i]; - Vec_IntPush( vSets, uSuppCur ); - } - return uSupport; - } - assert( pObj->Type == KIT_DSD_PRIME ); - // get the cumulative support of all fanins - uSupport = 0; - Kit_DsdObjForEachFanin( p, pObj, iLitFanin, i ) - { - uSuppCur = Lpk_ComputeSets_rec( p, iLitFanin, vSets ); - uSupport |= uSuppCur; - Vec_IntPush( vSets, uSuppCur ); - } - return uSupport; -} - -/**Function************************************************************* - - Synopsis [Computes the set of subsets of decomposable variables.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -unsigned Lpk_ComputeSets( Kit_DsdNtk_t * p, Vec_Int_t * vSets ) -{ - unsigned uSupport, Entry; - int Number, i; - assert( p->nVars <= 16 ); - Vec_IntClear( vSets ); - Vec_IntPush( vSets, 0 ); - if ( Kit_DsdNtkRoot(p)->Type == KIT_DSD_CONST1 ) - return 0; - if ( Kit_DsdNtkRoot(p)->Type == KIT_DSD_VAR ) - { - uSupport = ( 1 << Kit_DsdLit2Var(Kit_DsdNtkRoot(p)->pFans[0]) ); - Vec_IntPush( vSets, uSupport ); - return uSupport; - } - uSupport = Lpk_ComputeSets_rec( p, p->Root, vSets ); - assert( (uSupport & 0xFFFF0000) == 0 ); - Vec_IntPush( vSets, uSupport ); - // set the remaining variables - Vec_IntForEachEntry( vSets, Number, i ) - { - Entry = Number; - Vec_IntWriteEntry( vSets, i, Entry | ((uSupport & ~Entry) << 16) ); - } - return uSupport; -} - -/**Function************************************************************* - - Synopsis [Prints the sets of subsets.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static void Lpk_PrintSetOne( int uSupport ) -{ - unsigned k; - for ( k = 0; k < 16; k++ ) - if ( uSupport & (1<> 16) ); - // get the support reduction - nSuppRed = nSuppSize - 1 - nSuppOver; - // only consider support-reducing subsets - if ( nSuppRed <= 0 ) - continue; - // check if this support is already used - if ( TravId[uSupp] < nTravId ) - { - Used[nUsed++] = uSupp; - - TravId[uSupp] = nTravId; - SRed[uSupp] = nSuppRed; - Over[uSupp] = nSuppOver; - Parents[uSupp] = (k << 16) | i; - } - else if ( TravId[uSupp] == nTravId && SRed[uSupp] < nSuppRed ) - { - TravId[uSupp] = nTravId; - SRed[uSupp] = nSuppRed; - Over[uSupp] = nSuppOver; - Parents[uSupp] = (k << 16) | i; - } - } - - // find the minimum overlap - nMinOver = 1000; - for ( s = 0; s < nUsed; s++ ) - if ( nMinOver > Over[Used[s]] ) - nMinOver = Over[Used[s]]; - - - // collect the accumulated ones - for ( s = 0; s < nUsed; s++ ) - if ( Over[Used[s]] == nMinOver ) - { - // save the entry - if ( *pSize == nSizeLimit ) - return; - pEntry = pStore + (*pSize)++; - - i = Parents[Used[s]] & 0xFFFF; - k = Parents[Used[s]] >> 16; - - pEntry->uSubset0 = Vec_IntEntry(vSets0, i); - pEntry->uSubset1 = Vec_IntEntry(vSets1, k); - Entry = pEntry->uSubset0 | pEntry->uSubset1; - - // record the cofactoring variable - pEntry->iVar = iCofVar; - // set the bound set size - pEntry->Size = Kit_WordCountOnes( Entry & 0xFFFF ); - // get the number of overlapping vars - pEntry->Over = Kit_WordCountOnes( Entry & (Entry >> 16) ); - // get the support reduction - pEntry->SRed = pEntry->Size - 1 - pEntry->Over; - assert( pEntry->SRed > 0 ); - } -} - -/**Function************************************************************* - - Synopsis [Prints one set.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Lpk_MapSuppPrintSet( Lpk_Set_t * pSet, int i ) -{ - unsigned Entry; - Entry = pSet->uSubset0 | pSet->uSubset1; - printf( "%2d : ", i ); - printf( "Var = %c ", 'a' + pSet->iVar ); - printf( "Size = %2d ", pSet->Size ); - printf( "Over = %2d ", pSet->Over ); - printf( "SRed = %2d ", pSet->SRed ); - Lpk_PrintSetOne( Entry ); - printf( " " ); - Lpk_PrintSetOne( Entry >> 16 ); - printf( "\n" ); -} - -/**Function************************************************************* - - Synopsis [Evaluates the cofactors.] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -unsigned Lpk_MapSuppRedDecSelect( Lpk_Man_t * p, unsigned * pTruth, int nVars, int * piVar, int * piVarReused ) -{ - static int nStoreSize = 256; - static Lpk_Set_t pStore[256], * pSet, * pSetBest; - Kit_DsdNtk_t * ppNtks[2], * pTemp; - Vec_Int_t * vSets0 = p->vSets[0]; - Vec_Int_t * vSets1 = p->vSets[1]; - unsigned * pCof0 = Vec_PtrEntry( p->vTtNodes, 0 ); - unsigned * pCof1 = Vec_PtrEntry( p->vTtNodes, 1 ); - int nSets, i, SizeMax;//, SRedMax; - unsigned Entry; - int fVerbose = p->pPars->fVeryVerbose; -// int fVerbose = 0; - - // collect decomposable subsets for each pair of cofactors - if ( fVerbose ) - { - printf( "\nExploring support-reducing bound-sets of function:\n" ); - Kit_DsdPrintFromTruth( pTruth, nVars ); - } - nSets = 0; - for ( i = 0; i < nVars; i++ ) - { - if ( fVerbose ) - printf( "Evaluating variable %c:\n", 'a'+i ); - // evaluate the cofactor pair - Kit_TruthCofactor0New( pCof0, pTruth, nVars, i ); - Kit_TruthCofactor1New( pCof1, pTruth, nVars, i ); - // decompose and expand - 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 ); - if ( fVerbose ) - Kit_DsdPrint( stdout, ppNtks[0] ); - if ( fVerbose ) - Kit_DsdPrint( stdout, ppNtks[1] ); - // compute subsets - Lpk_ComputeSets( ppNtks[0], vSets0 ); - Lpk_ComputeSets( ppNtks[1], vSets1 ); - // print subsets - if ( fVerbose ) - Lpk_PrintSets( vSets0 ); - if ( fVerbose ) - Lpk_PrintSets( vSets1 ); - // free the networks - Kit_DsdNtkFree( ppNtks[0] ); - Kit_DsdNtkFree( ppNtks[1] ); - // evaluate the pair - Lpk_ComposeSets( vSets0, vSets1, nVars, i, pStore, &nSets, nStoreSize ); - } - - // print the results - if ( fVerbose ) - printf( "\n" ); - if ( fVerbose ) - for ( i = 0; i < nSets; i++ ) - Lpk_MapSuppPrintSet( pStore + i, i ); - - // choose the best subset - SizeMax = 0; - pSetBest = NULL; - for ( i = 0; i < nSets; i++ ) - { - pSet = pStore + i; - if ( pSet->Size > p->pPars->nLutSize - 1 ) - continue; - if ( SizeMax < pSet->Size ) - { - pSetBest = pSet; - SizeMax = pSet->Size; - } - } -/* - // if the best is not choosen, select the one with largest reduction - SRedMax = 0; - if ( pSetBest == NULL ) - { - for ( i = 0; i < nSets; i++ ) - { - pSet = pStore + i; - if ( SRedMax < pSet->SRed ) - { - pSetBest = pSet; - SRedMax = pSet->SRed; - } - } - } -*/ - if ( pSetBest == NULL ) - { - if ( fVerbose ) - printf( "Could not select a subset.\n" ); - return 0; - } - else - { - if ( fVerbose ) - printf( "Selected the following subset:\n" ); - if ( fVerbose ) - Lpk_MapSuppPrintSet( pSetBest, pSetBest - pStore ); - } - - // prepare the return result - // get the remaining variables - Entry = ((pSetBest->uSubset0 >> 16) | (pSetBest->uSubset1 >> 16)); - // get the variables to be removed - Entry = Kit_BitMask(nVars) & ~(1<iVar) & ~Entry; - // make sure there are some - otherwise it is not supp-red - assert( Entry ); - // remember the first such variable - *piVarReused = Kit_WordFindFirstBit( Entry ); - *piVar = pSetBest->iVar; - return (pSetBest->uSubset1 << 16) | (pSetBest->uSubset0 & 0xFFFF); -} - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/opt/lpk/lpk_.c b/src/opt/lpk/lpk_.c deleted file mode 100644 index d8555e08..00000000 --- a/src/opt/lpk/lpk_.c +++ /dev/null @@ -1,48 +0,0 @@ -/**CFile**************************************************************** - - FileName [lpk_.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: lpk_.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $] - -***********************************************************************/ - -#include "lpkInt.h" - -//////////////////////////////////////////////////////////////////////// -/// DECLARATIONS /// -//////////////////////////////////////////////////////////////////////// - -//////////////////////////////////////////////////////////////////////// -/// FUNCTION DEFINITIONS /// -//////////////////////////////////////////////////////////////////////// - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ - - -//////////////////////////////////////////////////////////////////////// -/// END OF FILE /// -//////////////////////////////////////////////////////////////////////// - - diff --git a/src/opt/lpk/module.make b/src/opt/lpk/module.make deleted file mode 100644 index 26a54894..00000000 --- a/src/opt/lpk/module.make +++ /dev/null @@ -1,11 +0,0 @@ -SRC += src/opt/lpk/lpkCore.c \ - src/opt/lpk/lpkAbcDec.c \ - src/opt/lpk/lpkAbcMux.c \ - src/opt/lpk/lpkAbcDsd.c \ - src/opt/lpk/lpkAbcUtil.c \ - src/opt/lpk/lpkCut.c \ - src/opt/lpk/lpkMan.c \ - src/opt/lpk/lpkMap.c \ - src/opt/lpk/lpkMulti.c \ - src/opt/lpk/lpkMux.c \ - src/opt/lpk/lpkSets.c -- cgit v1.2.3