/**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"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// 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((Abc_Obj_t *)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((Hop_Man_t *)pNtk->pManFunc), !(pTruth[0] & 1) );
return pObjNew;
}
if ( p->nVars == 1 )
{
pObjNew->pData = Hop_NotCond( Hop_ManPi((Hop_Man_t *)pNtk->pManFunc, 0), (pTruth[0] & 1) );
return pObjNew;
}
// create the logic function
pObjNew->pData = Kit_TruthToHop( (Hop_Man_t *)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 = (Abc_Obj_t *)Vec_PtrEntry( vLeaves, pFun->pFanins[i] );
if ( !Abc_ObjIsComplement(pFanin) )
Lpk_Implement_rec( pMan, pNtk, vLeaves, (Lpk_Fun_t *)pFanin );
pFanin = (Abc_Obj_t *)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( Abc_Obj_t *, 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, (Lpk_Fun_t *)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 )
{
Lpk_Res_t * pResMux, * pResDsd;
Lpk_Fun_t * p2;
clock_t 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( Lpk_Fun_t *, 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 ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END