/**CFile****************************************************************
FileName [acbPush.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Hierarchical word-level netlist.]
Synopsis [Implementation of logic pushing.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - July 21, 2015.]
Revision [$Id: acbPush.c,v 1.00 2014/11/29 00:00:00 alanmi Exp $]
***********************************************************************/
#include "acb.h"
#include "misc/util/utilTruth.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Pushing logic to the fanout.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Acb_ObjPushToFanout( Acb_Ntk_t * p, int iObj, int iFaninIndex, int iFanout )
{
word c0, uTruthObjNew = 0, uTruthObj = Acb_ObjTruth( p, iObj ), Gate;
word c1, uTruthFanNew = 0, uTruthFan = Acb_ObjTruth( p, iFanout );
int DecType = Abc_Tt6CheckOutDec( uTruthObj, iFaninIndex, &uTruthObjNew );
int iFanin = Acb_ObjFanin( p, iObj, iFaninIndex );
int iFanoutObjIndex = Acb_ObjWhatFanin( p, iFanout, iObj );
int iFanoutFaninIndex = Acb_ObjWhatFanin( p, iFanout, iFanin );
if ( iFanoutFaninIndex == -1 )
iFanoutFaninIndex = Acb_ObjFaninNum(p, iFanout);
assert( !Acb_ObjIsCio(p, iObj) );
assert( !Acb_ObjIsCio(p, iFanout) );
assert( iFanoutFaninIndex >= 0 );
assert( iFaninIndex < Acb_ObjFaninNum(p, iObj) );
assert( Acb_ObjFanoutNum(p, iObj) == 1 );
// compute new function of the fanout
c0 = Abc_Tt6Cofactor0( uTruthFan, iFanoutObjIndex );
c1 = Abc_Tt6Cofactor1( uTruthFan, iFanoutObjIndex );
if ( DecType == 0 ) // F = i * G
Gate = s_Truths6[iFanoutFaninIndex] & s_Truths6[iFanoutObjIndex];
else if ( DecType == 1 ) // F = ~i * G
Gate = ~s_Truths6[iFanoutFaninIndex] & s_Truths6[iFanoutObjIndex];
else if ( DecType == 2 ) // F = ~i + G
Gate = ~s_Truths6[iFanoutFaninIndex] | s_Truths6[iFanoutObjIndex];
else if ( DecType == 3 ) // F = i + G
Gate = s_Truths6[iFanoutFaninIndex] | s_Truths6[iFanoutObjIndex];
else if ( DecType == 4 ) // F = i # G
Gate = s_Truths6[iFanoutFaninIndex] ^ s_Truths6[iFanoutObjIndex];
else assert( 0 );
uTruthFanNew = (~Gate & c0) | (Gate & c1);
// update functions
Vec_WrdWriteEntry( &p->vObjTruth, iObj, Abc_Tt6RemoveVar(uTruthObjNew, iFaninIndex) );
Vec_WrdWriteEntry( &p->vObjTruth, iFanout, uTruthFanNew );
// update fanins
Acb_ObjRemoveFaninFanoutOne( p, iObj, iFanin );
if ( iFanoutFaninIndex == Acb_ObjFaninNum(p, iFanout) ) // adding new
Acb_ObjAddFaninFanoutOne( p, iFanout, iFanin );
}
/**Function*************************************************************
Synopsis [Pushing logic to the fanin.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Acb_ObjPushToFanin( Acb_Ntk_t * p, int iObj, int iFaninIndex2, int iFanin )
{
word uTruthObjNew = 0, uTruthObj = Acb_ObjTruth( p, iObj );
word uTruthFanNew = 0, uTruthFan = Acb_ObjTruth( p, iFanin );
int iFaninIndex = Acb_ObjWhatFanin( p, iObj, iFanin );
int DecType = Abc_TtCheckDsdAnd( uTruthObj, iFaninIndex, iFaninIndex2, &uTruthObjNew );
int iFanin2 = Acb_ObjFanin( p, iObj, iFaninIndex2 );
int iFaninFaninIndex = Acb_ObjWhatFanin( p, iFanin, iFanin2 );
if ( iFaninFaninIndex == -1 )
iFaninFaninIndex = Acb_ObjFaninNum(p, iFanin);
assert( !Acb_ObjIsCio(p, iObj) );
assert( !Acb_ObjIsCio(p, iFanin) );
assert( iFaninIndex < Acb_ObjFaninNum(p, iObj) );
assert( iFaninIndex2 < Acb_ObjFaninNum(p, iObj) );
assert( iFaninIndex != iFaninIndex2 );
assert( Acb_ObjFanoutNum(p, iFanin) == 1 );
// compute new function of the fanout
if ( DecType == 0 ) // i * j
uTruthFanNew = uTruthFan & s_Truths6[iFaninFaninIndex];
else if ( DecType == 1 ) // i * !j
uTruthFanNew = ~uTruthFan & s_Truths6[iFaninFaninIndex];
else if ( DecType == 2 ) // !i * j
uTruthFanNew = uTruthFan & ~s_Truths6[iFaninFaninIndex];
else if ( DecType == 3 ) // !i * !j
uTruthFanNew = ~uTruthFan & ~s_Truths6[iFaninFaninIndex];
else if ( DecType == 4 ) // i # j
uTruthFanNew = uTruthFan ^ s_Truths6[iFaninFaninIndex];
else assert( 0 );
// update functions
Vec_WrdWriteEntry( &p->vObjTruth, iObj, Abc_Tt6RemoveVar(uTruthObjNew, iFaninIndex2) );
Vec_WrdWriteEntry( &p->vObjTruth, iFanin, uTruthFanNew );
// update fanins
Acb_ObjRemoveFaninFanoutOne( p, iObj, iFanin2 );
if ( iFaninFaninIndex == Acb_ObjFaninNum(p, iFanin) ) // adding new
Acb_ObjAddFaninFanoutOne( p, iFanin, iFanin2 );
}
/**Function*************************************************************
Synopsis [Removing constants, buffers, duplicated fanins.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
static inline int Acb_ObjFindNodeFanout( Acb_Ntk_t * p, int iObj )
{
int i, iFanout;
Acb_ObjForEachFanout( p, iObj, iFanout, i )
if ( !Acb_ObjIsCio(p, iFanout) )
return iFanout;
return -1;
}
int Acb_ObjSuppMin_int( Acb_Ntk_t * p, int iObj )
{
int k, iFanin, * pFanins;
word uTruth = Acb_ObjTruth( p, iObj );
Acb_ObjForEachFaninFast( p, iObj, pFanins, iFanin, k )
{
if ( Abc_Tt6HasVar(uTruth, k) )
continue;
Acb_ObjDeleteFaninIndex( p, iObj, k );
Vec_IntRemove( Vec_WecEntry(&p->vFanouts, iFanin), iObj );
Vec_WrdWriteEntry( &p->vObjTruth, iObj, Abc_Tt6RemoveVar(uTruth, k) );
return 1;
}
return 0;
}
void Acb_ObjSuppMin( Acb_Ntk_t * p, int iObj )
{
while ( Acb_ObjSuppMin_int(p, iObj) );
}
void Acb_ObjRemoveDup( Acb_Ntk_t * p, int iObj, int i, int j )
{
word c00, c11, uTruthNew, uTruth = Acb_ObjTruth( p, iObj );
assert( !Acb_ObjIsCio(p, iObj) );
assert( Acb_ObjFanin(p, iObj, i) == Acb_ObjFanin(p, iObj, j) );
c00 = Abc_Tt6Cofactor0( Abc_Tt6Cofactor0(uTruth, i), j );
c11 = Abc_Tt6Cofactor1( Abc_Tt6Cofactor1(uTruth, i), j );
uTruthNew = (~s_Truths6[i] & c00) | (s_Truths6[i] & c11);
Vec_WrdWriteEntry( &p->vObjTruth, iObj, Abc_Tt6RemoveVar(uTruthNew, j) );
Acb_ObjDeleteFaninIndex( p, iObj, j );
Vec_IntRemove( Vec_WecEntry(&p->vFanouts, iObj), Acb_ObjFanin(p, iObj, j) );
Acb_ObjSuppMin( p, iObj );
}
int Acb_ObjRemoveDupFanins_int( Acb_Ntk_t * p, int iObj )
{
int i, k, * pFanins = Acb_ObjFanins( p, iObj );
for ( i = 0; i < pFanins[0]; i++ )
for ( k = i+1; k < pFanins[0]; k++ )
{
if ( pFanins[1+i] != pFanins[1+k] )
continue;
Acb_ObjRemoveDup( p, iObj, i, k );
return 1;
}
return 0;
}
void Acb_ObjRemoveDupFanins( Acb_Ntk_t * p, int iObj )
{
assert( !Acb_ObjIsCio(p, iObj) );
while ( Acb_ObjRemoveDupFanins_int(p, iObj) );
}
void Acb_ObjRemoveConst( Acb_Ntk_t * p, int iObj )
{
int iFanout;
word uTruth = Acb_ObjTruth( p, iObj );
assert( !Acb_ObjIsCio(p, iObj) );
assert( Acb_ObjFaninNum(p, iObj) == 0 );
assert( uTruth == 0 || ~uTruth == 0 );
while ( (iFanout = Acb_ObjFindNodeFanout(p, iObj)) >= 0 )
{
int iObjIndex = Acb_ObjWhatFanin( p, iFanout, iObj );
word uTruthF = Acb_ObjTruth( p, iFanout );
Acb_ObjRemoveFaninFanoutOne( p, iFanout, iObj );
uTruthF = (uTruth & 1) ? Abc_Tt6Cofactor1(uTruthF, iObjIndex) : Abc_Tt6Cofactor0(uTruthF, iObjIndex);
Vec_WrdWriteEntry( &p->vObjTruth, iFanout, Abc_Tt6RemoveVar(uTruthF, iObjIndex) );
Acb_ObjSuppMin( p, iFanout );
}
if ( Acb_ObjFanoutNum(p, iObj) == 0 )
Acb_ObjCleanType( p, iObj );
}
void Acb_ObjRemoveBufInv( Acb_Ntk_t * p, int iObj )
{
int iFanout;
word uTruth = Acb_ObjTruth( p, iObj );
assert( !Acb_ObjIsCio(p, iObj) );
assert( Acb_ObjFaninNum(p, iObj) == 1 );
assert( uTruth == s_Truths6[0] || ~uTruth == s_Truths6[0] );
while ( (iFanout = Acb_ObjFindNodeFanout(p, iObj)) >= 0 )
{
int iFanin = Acb_ObjFanin( p, iObj, 0 );
int iObjIndex = Acb_ObjWhatFanin( p, iFanout, iObj );
Acb_ObjPatchFanin( p, iFanout, iObj, iFanin );
if ( uTruth & 1 ) // inv
{
word uTruthF = Acb_ObjTruth( p, iFanout );
Vec_WrdWriteEntry( &p->vObjTruth, iFanout, Abc_Tt6Flip(uTruthF, iObjIndex) );
}
Acb_ObjRemoveDupFanins( p, iFanout );
}
while ( (uTruth & 1) == 0 && Acb_ObjFanoutNum(p, iObj) > 0 )
{
int iFanin = Acb_ObjFanin( p, iObj, 0 );
int iFanout = Acb_ObjFanout( p, iObj, 0 );
assert( Acb_ObjIsCo(p, iFanout) );
Acb_ObjPatchFanin( p, iFanout, iObj, iFanin );
}
if ( Acb_ObjFanoutNum(p, iObj) == 0 )
{
Acb_ObjRemoveFaninFanout( p, iObj );
Acb_ObjRemoveFanins( p, iObj );
Acb_ObjCleanType( p, iObj );
}
}
/**Function*************************************************************
Synopsis [Check if the node can have its logic pushed.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
static inline int Acb_ObjFindFaninPushableIndex( Acb_Ntk_t * p, int iObj, int iFanIndex )
{
int k, iFanin, * pFanins;
Acb_ObjForEachFaninFast( p, iObj, pFanins, iFanin, k )
if ( k != iFanIndex && Abc_TtCheckDsdAnd(Acb_ObjTruth(p, iObj), k, iFanIndex, NULL) >= 0 )
return k;
return -1;
}
static inline int Acb_ObjFindFanoutPushableIndex( Acb_Ntk_t * p, int iObj )
{
int k, iFanin, * pFanins;
Acb_ObjForEachFaninFast( p, iObj, pFanins, iFanin, k )
if ( Abc_Tt6CheckOutDec(Acb_ObjTruth(p, iObj), k, NULL) >= 0 )
return k;
return -1;
}
int Acb_ObjPushToFanins( Acb_Ntk_t * p, int iObj, int nLutSize )
{
int k, k2, iFanin, * pFanins;
if ( Acb_ObjFaninNum(p, iObj) < 2 )
return 0;
Acb_ObjForEachFaninFast( p, iObj, pFanins, iFanin, k )
{
if ( Acb_ObjIsCi(p, iFanin) )
continue;
if ( Acb_ObjFanoutNum(p, iFanin) > 1 )
continue;
if ( Acb_ObjFaninNum(p, iFanin) == nLutSize )
continue;
if ( (k2 = Acb_ObjFindFaninPushableIndex(p, iObj, k)) == -1 )
continue;
//printf( "Object %4d : Pushing fanin %d (%d) into fanin %d.\n", iObj, Acb_ObjFanin(p, iObj, k2), k2, iFanin );
Acb_ObjPushToFanin( p, iObj, k2, iFanin );
return 1;
}
if ( Acb_ObjFaninNum(p, iObj) == 2 && Acb_ObjFanoutNum(p, iObj) == 1 )
{
int iFanout = Acb_ObjFanout( p, iObj, 0 );
if ( !Acb_ObjIsCo(p, iFanout) && Acb_ObjFaninNum(p, iFanout) < nLutSize )
{
k2 = Acb_ObjFindFanoutPushableIndex( p, iObj );
//printf( "Object %4d : Pushing fanin %d (%d) into fanout %d.\n", iObj, Acb_ObjFanin(p, iObj, k2), k2, iFanout );
Acb_ObjPushToFanout( p, iObj, k2, iFanout );
return 1;
}
}
return 0;
}
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Acb_NtkPushLogic( Acb_Ntk_t * p, int nLutSize, int fVerbose )
{
int n = 0, iObj, nNodes = Acb_NtkNodeNum(p), nPushes = 0;
Acb_NtkCreateFanout( p ); // fanout data structure
Acb_NtkForEachNodeSupp( p, iObj, 0 )
Acb_ObjRemoveConst( p, iObj );
Acb_NtkForEachNodeSupp( p, iObj, 1 )
Acb_ObjRemoveBufInv( p, iObj );
for ( n = 2; n <= nLutSize; n++ )
Acb_NtkForEachNodeSupp( p, iObj, n )
{
while ( Acb_ObjPushToFanins(p, iObj, nLutSize) )
nPushes++;
if ( Acb_ObjFaninNum(p, iObj) == 1 )
Acb_ObjRemoveBufInv( p, iObj );
}
printf( "Saved %d nodes after %d pushes.\n", nNodes - Acb_NtkNodeNum(p), nPushes );
}
/**Function*************************************************************
Synopsis [Pushing logic to the fanin.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Acb_NtkPushLogic2( Acb_Ntk_t * p, int nLutSize, int fVerbose )
{
int iObj;
Acb_NtkCreateFanout( p ); // fanout data structure
Acb_NtkForEachObj( p, iObj )
if ( !Acb_ObjIsCio(p, iObj) )
break;
Acb_ObjPushToFanout( p, iObj, Acb_ObjFaninNum(p, iObj)-1, Acb_ObjFanout(p, iObj, 0) );
// Acb_ObjPushToFanin( p, Acb_ObjFanout(p, iObj, 0), Acb_ObjFaninNum(p, iObj)-1, iObj );
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END