/**CFile****************************************************************
FileName [giaBidec.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Scalable AIG package.]
Synopsis [Application of bi-decomposition to AIG minimization.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [$Id: giaBidec.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
***********************************************************************/
#include "gia.h"
#include "bool/bdc/bdc.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Computes truth table of the cut.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
unsigned * Gia_ManConvertAigToTruth_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vTruth, int nWords, Vec_Int_t * vVisited )
{
unsigned * pTruth, * pTruth0, * pTruth1;
int i;
assert( !Gia_IsComplement(pObj) );
if ( Vec_IntGetEntry(p->vTruths, Gia_ObjId(p, pObj)) != -1 )
return (unsigned *)Vec_IntEntryP( vTruth, nWords * Vec_IntGetEntry(p->vTruths, Gia_ObjId(p, pObj)) );
// compute the truth tables of the fanins
pTruth0 = Gia_ManConvertAigToTruth_rec( p, Gia_ObjFanin0(pObj), vTruth, nWords, vVisited );
pTruth1 = Gia_ManConvertAigToTruth_rec( p, Gia_ObjFanin1(pObj), vTruth, nWords, vVisited );
// get room for the truth table
pTruth = Vec_IntFetch( vTruth, nWords );
// create the truth table of the node
if ( !Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) )
for ( i = 0; i < nWords; i++ )
pTruth[i] = pTruth0[i] & pTruth1[i];
else if ( !Gia_ObjFaninC0(pObj) && Gia_ObjFaninC1(pObj) )
for ( i = 0; i < nWords; i++ )
pTruth[i] = pTruth0[i] & ~pTruth1[i];
else if ( Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) )
for ( i = 0; i < nWords; i++ )
pTruth[i] = ~pTruth0[i] & pTruth1[i];
else // if ( Gia_ObjFaninC0(pObj) && Gia_ObjFaninC1(pObj) )
for ( i = 0; i < nWords; i++ )
pTruth[i] = ~pTruth0[i] & ~pTruth1[i];
// save the visited node
Vec_IntSetEntry( p->vTruths, Gia_ObjId(p, pObj), Vec_IntSize(vVisited) );
Vec_IntPush( vVisited, Gia_ObjId(p, pObj) );
return pTruth;
}
/**Function*************************************************************
Synopsis [Computes truth table of the node.]
Description [Assumes that the structural support is no more than 8 inputs.
Uses array vTruth to store temporary truth tables. The returned pointer should
be used immediately.]
SideEffects []
SeeAlso []
***********************************************************************/
unsigned * Gia_ManConvertAigToTruth( Gia_Man_t * p, Gia_Obj_t * pRoot, Vec_Int_t * vLeaves, Vec_Int_t * vTruth, Vec_Int_t * vVisited )
{
static unsigned uTruths[8][8] = { // elementary truth tables
{ 0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA },
{ 0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC },
{ 0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0 },
{ 0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00 },
{ 0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000 },
{ 0x00000000,0xFFFFFFFF,0x00000000,0xFFFFFFFF,0x00000000,0xFFFFFFFF,0x00000000,0xFFFFFFFF },
{ 0x00000000,0x00000000,0xFFFFFFFF,0xFFFFFFFF,0x00000000,0x00000000,0xFFFFFFFF,0xFFFFFFFF },
{ 0x00000000,0x00000000,0x00000000,0x00000000,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF }
};
Gia_Obj_t * pObj;
Vec_Ptr_t * vTtElems = NULL;
unsigned * pTruth;//, * pTruth2;
int i, nWords, nVars;
// get the number of variables and words
nVars = Vec_IntSize( vLeaves );
nWords = Abc_TruthWordNum( nVars );
// check the case of a constant
if ( Gia_ObjIsConst0( Gia_Regular(pRoot) ) )
{
Vec_IntClear( vTruth );
// get room for the truth table
pTruth = Vec_IntFetch( vTruth, nWords );
if ( !Gia_IsComplement(pRoot) )
Gia_ManTruthClear( pTruth, nVars );
else
Gia_ManTruthFill( pTruth, nVars );
return pTruth;
}
// if the number of variables is more than 8, allocate truth tables
if ( nVars > 8 )
vTtElems = Vec_PtrAllocTruthTables( nVars );
// assign elementary truth tables
Vec_IntClear( vTruth );
Vec_IntClear( vVisited );
Gia_ManForEachObjVec( vLeaves, p, pObj, i )
{
// get room for the truth table
pTruth = Vec_IntFetch( vTruth, nWords );
// assign elementary variable
if ( vTtElems )
Gia_ManTruthCopy( pTruth, (unsigned *)Vec_PtrEntry(vTtElems, i), nVars );
else
Gia_ManTruthCopy( pTruth, uTruths[i], nVars );
// save the visited node
Vec_IntSetEntry( p->vTruths, Gia_ObjId(p, pObj), Vec_IntSize(vVisited) );
Vec_IntPush( vVisited, Gia_ObjId(p, pObj) );
}
if ( vTtElems )
Vec_PtrFree( vTtElems );
// clear the marks and compute the truth table
// pTruth2 = Gia_ManConvertAigToTruth_rec( p, Gia_Regular(pRoot), vTruth, nWords, vVisited );
pTruth = Gia_ManConvertAigToTruth_rec( p, Gia_Regular(pRoot), vTruth, nWords, vVisited );
// copy the result
// Gia_ManTruthCopy( pTruth, pTruth2, nVars );
if ( Gia_IsComplement(pRoot) )
Gia_ManTruthNot( pTruth, pTruth, nVars );
// clean truth tables
Gia_ManForEachObjVec( vVisited, p, pObj, i )
Vec_IntSetEntry( p->vTruths, Gia_ObjId(p, pObj), -1 );
return pTruth;
}
/**Function*************************************************************
Synopsis [Resynthesizes nodes using bi-decomposition.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Gia_ObjPerformBidec( Bdc_Man_t * pManDec,
Gia_Man_t * pNew, Gia_Man_t * p, Gia_Obj_t * pRoot,
Vec_Int_t * vLeaves, Vec_Int_t * vTruth, Vec_Int_t * vVisited )
{
unsigned * pTruth;
Bdc_Fun_t * pFunc;
Gia_Obj_t * pFanin;
int i, iFan, nVars, nNodes;
// collect leaves of this gate
Vec_IntClear( vLeaves );
Gia_LutForEachFanin( p, Gia_ObjId(p, pRoot), iFan, i )
Vec_IntPush( vLeaves, iFan );
nVars = Vec_IntSize( vLeaves );
assert( nVars < 16 );
// derive truth table
pTruth = Gia_ManConvertAigToTruth( p, pRoot, vLeaves, vTruth, vVisited );
//Extra_PrintBinary( stdout, pTruth, (1<<nVars) ); printf( "\n" );
if ( Gia_ManTruthIsConst0(pTruth, nVars) )
{
//printf( "Node %d is const0\n", Gia_ObjId(p, pRoot) );
return 0;
}
if ( Gia_ManTruthIsConst1(pTruth, nVars) )
{
//printf( "Node %d is const1\n", Gia_ObjId(p, pRoot) );
return 1;
}
// decompose truth table
Bdc_ManDecompose( pManDec, pTruth, NULL, nVars, NULL, 1000 );
/*
if ( Bdc_ManNodeNum(pManDec) == 0 )
printf( "Node %d has 0 bidec nodes\n", Gia_ObjId(p, pRoot) );
if ( Kit_TruthSupportSize(pTruth, nVars) != nVars )
{
printf( "Node %d has %d fanins and %d supp size\n", Gia_ObjId(p, pRoot), nVars, Kit_TruthSupportSize(pTruth, nVars) );
Gia_LutForEachFanin( p, Gia_ObjId(p, pRoot), iFan, i )
{
printf( "%d ", Kit_TruthVarInSupport(pTruth, nVars, i) );
Gia_ObjPrint( p, Gia_ManObj(p, iFan) );
}
// Gia_ManPrintStats( p, 0 );
}
*/
// convert back into HOP
Bdc_FuncSetCopy( Bdc_ManFunc( pManDec, 0 ), Gia_ManConst1(pNew) );
Gia_ManForEachObjVec( vLeaves, p, pFanin, i )
Bdc_FuncSetCopyInt( Bdc_ManFunc( pManDec, i+1 ), Gia_ObjValue(pFanin) );
nNodes = Bdc_ManNodeNum( pManDec );
for ( i = nVars + 1; i < nNodes; i++ )
{
pFunc = Bdc_ManFunc( pManDec, i );
Bdc_FuncSetCopyInt( pFunc, Gia_ManHashAnd( pNew, Bdc_FunFanin0Copy(pFunc), Bdc_FunFanin1Copy(pFunc) ) );
}
return Bdc_FunObjCopy( Bdc_ManRoot(pManDec) );
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Gia_Man_t * Gia_ManPerformBidec( Gia_Man_t * p, int fVerbose )
{
Bdc_Man_t * pManDec;
Bdc_Par_t Pars = {0}, * pPars = &Pars;
Vec_Int_t * vLeaves, * vTruth, * vVisited;
Gia_Man_t * pNew, * pTemp;
Gia_Obj_t * pObj;
int i;//, clk = Abc_Clock();
pPars->nVarsMax = Gia_ManLutSizeMax( p );
pPars->fVerbose = fVerbose;
if ( pPars->nVarsMax < 2 )
{
printf( "Resynthesis is not performed when nodes have less than 2 inputs.\n" );
return NULL;
}
if ( pPars->nVarsMax > 15 )
{
printf( "Resynthesis is not performed when nodes have more than 15 inputs.\n" );
return NULL;
}
vLeaves = Vec_IntAlloc( 0 );
vTruth = Vec_IntAlloc( (1<<16) );
vVisited = Vec_IntAlloc( 0 );
// clean the old manager
Gia_ManCleanTruth( p );
Gia_ManFillValue( p );
Gia_ManConst0(p)->Value = 0;
// start the new manager
pNew = Gia_ManStart( Gia_ManObjNum(p) );
pNew->pName = Abc_UtilStrsav( p->pName );
pNew->pSpec = Abc_UtilStrsav( p->pSpec );
Gia_ManHashAlloc( pNew );
// Gia_ManCleanLevels( pNew, Gia_ManObjNum(p) );
pManDec = Bdc_ManAlloc( pPars );
Gia_ManForEachObj1( p, pObj, i )
{
if ( Gia_ObjIsCi(pObj) ) // transfer the CI level (is it needed?)
pObj->Value = Gia_ManAppendCi( pNew );
else if ( Gia_ObjIsCo(pObj) )
pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
else if ( Gia_ObjIsLut(p, i) )
pObj->Value = Gia_ObjPerformBidec( pManDec, pNew, p, pObj, vLeaves, vTruth, vVisited );
}
Bdc_ManFree( pManDec );
// cleanup the AIG
Gia_ManHashStop( pNew );
// check the presence of dangling nodes
if ( Gia_ManHasDangling(pNew) )
{
pNew = Gia_ManCleanup( pTemp = pNew );
if ( Gia_ManAndNum(pNew) != Gia_ManAndNum(pTemp) )
printf( "Gia_ManPerformBidec() node count before and after: %6d and %6d.\n", Gia_ManAndNum(pNew), Gia_ManAndNum(pTemp) );
Gia_ManStop( pTemp );
}
Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
Vec_IntFree( vLeaves );
Vec_IntFree( vTruth );
Vec_IntFree( vVisited );
if ( fVerbose )
{
// printf( "Total gain in AIG nodes = %d. ", Gia_ManObjNum(p)-Gia_ManObjNum(pNew) );
// ABC_PRT( "Total runtime", Abc_Clock() - clk );
}
return pNew;
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END