acbPush.c

/**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