abcBalance.c

/**CFile****************************************************************

  FileName    [abcBalance.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Network and node package.]

  Synopsis    [Performs global balancing of the AIG by the number of levels.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - June 20, 2005.]

  Revision    [$Id: abcBalance.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]

***********************************************************************/

#include "base/abc/abc.h"

ABC_NAMESPACE_IMPL_START


////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////
 
static void        Abc_NtkBalancePerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, int fDuplicate, int fSelective, int fUpdateLevel );
static Abc_Obj_t * Abc_NodeBalance_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNode, Vec_Vec_t * vStorage, int Level, int fDuplicate, int fSelective, int fUpdateLevel );
static Vec_Ptr_t * Abc_NodeBalanceCone( Abc_Obj_t * pNode, Vec_Vec_t * vSuper, int Level, int fDuplicate, int fSelective );
static int         Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, int fFirst, int fDuplicate, int fSelective );
static void        Abc_NtkMarkCriticalNodes( Abc_Ntk_t * pNtk );
static Vec_Ptr_t * Abc_NodeBalanceConeExor( Abc_Obj_t * pNode );


////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

  Synopsis    [Balances the AIG network.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Abc_Ntk_t * Abc_NtkBalance( Abc_Ntk_t * pNtk, int fDuplicate, int fSelective, int fUpdateLevel )
{
//    extern void Abc_NtkHaigTranfer( Abc_Ntk_t * pNtkOld, Abc_Ntk_t * pNtkNew );
    Abc_Ntk_t * pNtkAig;
    assert( Abc_NtkIsStrash(pNtk) );
    // compute the required times
    if ( fSelective )
    {
        Abc_NtkStartReverseLevels( pNtk, 0 );
        Abc_NtkMarkCriticalNodes( pNtk );
    }
    // perform balancing
    pNtkAig = Abc_NtkStartFrom( pNtk, ABC_NTK_STRASH, ABC_FUNC_AIG );
    // transfer HAIG
//    Abc_NtkHaigTranfer( pNtk, pNtkAig );
    // perform balancing
    Abc_NtkBalancePerform( pNtk, pNtkAig, fDuplicate, fSelective, fUpdateLevel );
    Abc_NtkFinalize( pNtk, pNtkAig );
    Abc_AigCleanup( (Abc_Aig_t *)pNtkAig->pManFunc );
    // undo the required times
    if ( fSelective )
    {
        Abc_NtkStopReverseLevels( pNtk );
        Abc_NtkCleanMarkA( pNtk );
    }
    if ( pNtk->pExdc )
        pNtkAig->pExdc = Abc_NtkDup( pNtk->pExdc );
    // make sure everything is okay
    if ( !Abc_NtkCheck( pNtkAig ) )
    {
        printf( "Abc_NtkBalance: The network check has failed.\n" );
        Abc_NtkDelete( pNtkAig );
        return NULL;
    }
//Abc_NtkPrintCiLevels( pNtkAig );
    return pNtkAig;
}

/**Function*************************************************************

  Synopsis    [Balances the AIG network.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkBalancePerform( Abc_Ntk_t * pNtk, Abc_Ntk_t * pNtkAig, int fDuplicate, int fSelective, int fUpdateLevel )
{
    ProgressBar * pProgress;
    Vec_Vec_t * vStorage;
    Abc_Obj_t * pNode;
    int i;
    // transfer level
    Abc_NtkForEachCi( pNtk, pNode, i )
        pNode->pCopy->Level = pNode->Level;
    // set the level of PIs of AIG according to the arrival times of the old network
    Abc_NtkSetNodeLevelsArrival( pNtk );
    // allocate temporary storage for supergates
    vStorage = Vec_VecStart( 10 );
    // perform balancing of POs
    pProgress = Extra_ProgressBarStart( stdout, Abc_NtkCoNum(pNtk) );
    if ( pNtk->nBarBufs == 0 )
    {
        Abc_NtkForEachCo( pNtk, pNode, i )
        {
            Extra_ProgressBarUpdate( pProgress, i, NULL );
            Abc_NodeBalance_rec( pNtkAig, Abc_ObjFanin0(pNode), vStorage, 0, fDuplicate, fSelective, fUpdateLevel );
        }
    }
    else
    {
        Abc_NtkForEachLiPo( pNtk, pNode, i )
        {
            Extra_ProgressBarUpdate( pProgress, i, NULL );
            Abc_NodeBalance_rec( pNtkAig, Abc_ObjFanin0(pNode), vStorage, 0, fDuplicate, fSelective, fUpdateLevel );
            if ( i < pNtk->nBarBufs )
                Abc_ObjFanout0(Abc_ObjFanout0(pNode))->Level = Abc_ObjFanin0(pNode)->Level;
        }
    }
    Extra_ProgressBarStop( pProgress );
    Vec_VecFree( vStorage );
}

/**Function*************************************************************

  Synopsis    [Finds the left bound on the next candidate to be paired.]

  Description [The nodes in the array are in the decreasing order of levels. 
  The last node in the array has the smallest level. By default it would be paired 
  with the next node on the left. However, it may be possible to pair it with some
  other node on the left, in such a way that the new node is shared. This procedure
  finds the index of the left-most node, which can be paired with the last node.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NodeBalanceFindLeft( Vec_Ptr_t * vSuper )
{
    Abc_Obj_t * pNodeRight, * pNodeLeft;
    int Current;
    // if two or less nodes, pair with the first
    if ( Vec_PtrSize(vSuper) < 3 )
        return 0;
    // set the pointer to the one before the last
    Current = Vec_PtrSize(vSuper) - 2;
    pNodeRight = (Abc_Obj_t *)Vec_PtrEntry( vSuper, Current );
    // go through the nodes to the left of this one
    for ( Current--; Current >= 0; Current-- )
    {
        // get the next node on the left
        pNodeLeft = (Abc_Obj_t *)Vec_PtrEntry( vSuper, Current );
        // if the level of this node is different, quit the loop
        if ( Abc_ObjRegular(pNodeLeft)->Level != Abc_ObjRegular(pNodeRight)->Level )
            break;
    }
    Current++;    
    // get the node, for which the equality holds
    pNodeLeft = (Abc_Obj_t *)Vec_PtrEntry( vSuper, Current );
    assert( Abc_ObjRegular(pNodeLeft)->Level == Abc_ObjRegular(pNodeRight)->Level );
    return Current;
}

/**Function*************************************************************

  Synopsis    [Moves closer to the end the node that is best for sharing.]

  Description [If there is no node with sharing, randomly chooses one of 
  the legal nodes.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NodeBalancePermute( Abc_Ntk_t * pNtkNew, Vec_Ptr_t * vSuper, int LeftBound )
{
    Abc_Obj_t * pNode1, * pNode2, * pNode3;
    int RightBound, i;
    // get the right bound
    RightBound = Vec_PtrSize(vSuper) - 2;
    assert( LeftBound <= RightBound );
    if ( LeftBound == RightBound )
        return;
    // get the two last nodes
    pNode1 = (Abc_Obj_t *)Vec_PtrEntry( vSuper, RightBound + 1 );
    pNode2 = (Abc_Obj_t *)Vec_PtrEntry( vSuper, RightBound     );
    // find the first node that can be shared
    for ( i = RightBound; i >= LeftBound; i-- )
    {
        pNode3 = (Abc_Obj_t *)Vec_PtrEntry( vSuper, i );
        if ( Abc_AigAndLookup( (Abc_Aig_t *)pNtkNew->pManFunc, pNode1, pNode3 ) )
        {
            if ( pNode3 == pNode2 )
                return;
            Vec_PtrWriteEntry( vSuper, i,          pNode2 );
            Vec_PtrWriteEntry( vSuper, RightBound, pNode3 );
            return;
        }
    }
/*
    // we did not find the node to share, randomize choice
    {
        int Choice = rand() % (RightBound - LeftBound + 1);
        pNode3 = Vec_PtrEntry( vSuper, LeftBound + Choice );
        if ( pNode3 == pNode2 )
            return;
        Vec_PtrWriteEntry( vSuper, LeftBound + Choice, pNode2 );
        Vec_PtrWriteEntry( vSuper, RightBound,         pNode3 );
    }
*/
}

/**Function*************************************************************

  Synopsis    [Rebalances the multi-input node rooted at pNodeOld.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Abc_Obj_t * Abc_NodeBalance_rec( Abc_Ntk_t * pNtkNew, Abc_Obj_t * pNodeOld, Vec_Vec_t * vStorage, int Level, int fDuplicate, int fSelective, int fUpdateLevel )
{
    Abc_Aig_t * pMan = (Abc_Aig_t *)pNtkNew->pManFunc;
    Abc_Obj_t * pNodeNew, * pNode1, * pNode2;
    Vec_Ptr_t * vSuper;
    int i, LeftBound;
    assert( !Abc_ObjIsComplement(pNodeOld) );
    // return if the result if known
    if ( pNodeOld->pCopy )
        return pNodeOld->pCopy;
    assert( Abc_ObjIsNode(pNodeOld) );
    // get the implication supergate
//    Abc_NodeBalanceConeExor( pNodeOld );
    vSuper = Abc_NodeBalanceCone( pNodeOld, vStorage, Level, fDuplicate, fSelective );
    if ( vSuper->nSize == 0 )
    { // it means that the supergate contains two nodes in the opposite polarity
        pNodeOld->pCopy = Abc_ObjNot(Abc_AigConst1(pNtkNew));
        return pNodeOld->pCopy;
    }
    // for each old node, derive the new well-balanced node
    for ( i = 0; i < vSuper->nSize; i++ )
    {
        pNodeNew = Abc_NodeBalance_rec( pNtkNew, Abc_ObjRegular((Abc_Obj_t *)vSuper->pArray[i]), vStorage, Level + 1, fDuplicate, fSelective, fUpdateLevel );
        vSuper->pArray[i] = Abc_ObjNotCond( pNodeNew, Abc_ObjIsComplement((Abc_Obj_t *)vSuper->pArray[i]) );
    }
    if ( vSuper->nSize < 2 )
        printf( "BUG!\n" );
    // sort the new nodes by level in the decreasing order
    Vec_PtrSort( vSuper, (int (*)(const void *, const void *))Abc_NodeCompareLevelsDecrease );
    // balance the nodes
    assert( vSuper->nSize > 1 );
    while ( vSuper->nSize > 1 )
    {
        // find the left bound on the node to be paired
        LeftBound = (!fUpdateLevel)? 0 : Abc_NodeBalanceFindLeft( vSuper );
        // find the node that can be shared (if no such node, randomize choice)
        Abc_NodeBalancePermute( pNtkNew, vSuper, LeftBound );
        // pull out the last two nodes
        pNode1 = (Abc_Obj_t *)Vec_PtrPop(vSuper);
        pNode2 = (Abc_Obj_t *)Vec_PtrPop(vSuper);
        Abc_VecObjPushUniqueOrderByLevel( vSuper, Abc_AigAnd(pMan, pNode1, pNode2) );
    }
    // make sure the balanced node is not assigned
    assert( pNodeOld->pCopy == NULL );
    // mark the old node with the new node
    pNodeOld->pCopy = (Abc_Obj_t *)vSuper->pArray[0];
    vSuper->nSize = 0;
//    if ( Abc_ObjRegular(pNodeOld->pCopy) == Abc_AigConst1(pNtkNew) )
//        printf( "Constant node\n" );
//    assert( pNodeOld->Level >= Abc_ObjRegular(pNodeOld->pCopy)->Level );
    return pNodeOld->pCopy;
}

/**Function*************************************************************

  Synopsis    [Collects the nodes in the cone delimited by fMarkA==1.]

  Description [Returns -1 if the AND-cone has the same node in both polarities.
  Returns 1 if the AND-cone has the same node in the same polarity. Returns 0
  if the AND-cone has no repeated nodes.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Abc_NodeBalanceCone( Abc_Obj_t * pNode, Vec_Vec_t * vStorage, int Level, int fDuplicate, int fSelective )
{
    Vec_Ptr_t * vNodes;
    int RetValue, i;
    assert( !Abc_ObjIsComplement(pNode) );
    // extend the storage
    if ( Vec_VecSize( vStorage ) <= Level )
        Vec_VecPush( vStorage, Level, 0 );
    // get the temporary array of nodes
    vNodes = Vec_VecEntry( vStorage, Level );
    Vec_PtrClear( vNodes );
    // collect the nodes in the implication supergate
    RetValue = Abc_NodeBalanceCone_rec( pNode, vNodes, 1, fDuplicate, fSelective );
    assert( vNodes->nSize > 1 );
    // unmark the visited nodes
    for ( i = 0; i < vNodes->nSize; i++ )
        Abc_ObjRegular((Abc_Obj_t *)vNodes->pArray[i])->fMarkB = 0;
    // if we found the node and its complement in the same implication supergate, 
    // return empty set of nodes (meaning that we should use constant-0 node)
    if ( RetValue == -1 )
        vNodes->nSize = 0;
    return vNodes;
}


/**Function*************************************************************

  Synopsis    [Collects the nodes in the cone delimited by fMarkA==1.]

  Description [Returns -1 if the AND-cone has the same node in both polarities.
  Returns 1 if the AND-cone has the same node in the same polarity. Returns 0
  if the AND-cone has no repeated nodes.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NodeBalanceCone_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, int fFirst, int fDuplicate, int fSelective )
{
    int RetValue1, RetValue2, i;
    // check if the node is visited
    if ( Abc_ObjRegular(pNode)->fMarkB )
    {
        // check if the node occurs in the same polarity
        for ( i = 0; i < vSuper->nSize; i++ )
            if ( vSuper->pArray[i] == pNode )
                return 1;
        // check if the node is present in the opposite polarity
        for ( i = 0; i < vSuper->nSize; i++ )
            if ( vSuper->pArray[i] == Abc_ObjNot(pNode) )
                return -1;
        assert( 0 );
        return 0;
    }
    // if the new node is complemented or a PI, another gate begins
    if ( !fFirst && (Abc_ObjIsComplement(pNode) || !Abc_ObjIsNode(pNode) || (!fDuplicate && !fSelective && (Abc_ObjFanoutNum(pNode) > 1)) || Vec_PtrSize(vSuper) > 10000) )
    {
        Vec_PtrPush( vSuper, pNode );
        Abc_ObjRegular(pNode)->fMarkB = 1;
        return 0;
    }
    assert( !Abc_ObjIsComplement(pNode) );
    assert( Abc_ObjIsNode(pNode) );
    // go through the branches
    RetValue1 = Abc_NodeBalanceCone_rec( Abc_ObjChild0(pNode), vSuper, 0, fDuplicate, fSelective );
    RetValue2 = Abc_NodeBalanceCone_rec( Abc_ObjChild1(pNode), vSuper, 0, fDuplicate, fSelective );
    if ( RetValue1 == -1 || RetValue2 == -1 )
        return -1;
    // return 1 if at least one branch has a duplicate
    return RetValue1 || RetValue2;
}


/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NodeBalanceConeExor_rec( Abc_Obj_t * pNode, Vec_Ptr_t * vSuper, int fFirst )
{
    int RetValue1, RetValue2, i;
    // check if the node occurs in the same polarity
    for ( i = 0; i < vSuper->nSize; i++ )
        if ( vSuper->pArray[i] == pNode )
            return 1;
    // if the new node is complemented or a PI, another gate begins
    if ( !fFirst && (!pNode->fExor || !Abc_ObjIsNode(pNode)) )
    {
        Vec_PtrPush( vSuper, pNode );
        return 0;
    }
    assert( !Abc_ObjIsComplement(pNode) );
    assert( Abc_ObjIsNode(pNode) );
    assert( pNode->fExor );
    // go through the branches
    RetValue1 = Abc_NodeBalanceConeExor_rec( Abc_ObjFanin0(Abc_ObjFanin0(pNode)), vSuper, 0 );
    RetValue2 = Abc_NodeBalanceConeExor_rec( Abc_ObjFanin1(Abc_ObjFanin0(pNode)), vSuper, 0 );
    if ( RetValue1 == -1 || RetValue2 == -1 )
        return -1;
    // return 1 if at least one branch has a duplicate
    return RetValue1 || RetValue2;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Abc_NodeBalanceConeExor( Abc_Obj_t * pNode )
{
    Vec_Ptr_t * vSuper;
    if ( !pNode->fExor )
        return NULL;
    vSuper = Vec_PtrAlloc( 10 );
    Abc_NodeBalanceConeExor_rec( pNode, vSuper, 1 );
    printf( "%d ", Vec_PtrSize(vSuper) );
    Vec_PtrFree( vSuper );
    return NULL;
}



/**Function*************************************************************

  Synopsis    [Collects the nodes in the implication supergate.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Abc_NodeFindCone_rec( Abc_Obj_t * pNode )
{
    Vec_Ptr_t * vNodes;
    Abc_Obj_t * pNodeC, * pNodeT, * pNodeE;
    int RetValue, i;
    assert( !Abc_ObjIsComplement(pNode) );
    if ( Abc_ObjIsCi(pNode) )
        return NULL;
    // start the new array
    vNodes = Vec_PtrAlloc( 4 );
    // if the node is the MUX collect its fanins
    if ( Abc_NodeIsMuxType(pNode) )
    {
        pNodeC = Abc_NodeRecognizeMux( pNode, &pNodeT, &pNodeE );
        Vec_PtrPush( vNodes, Abc_ObjRegular(pNodeC) );
        Vec_PtrPushUnique( vNodes, Abc_ObjRegular(pNodeT) );
        Vec_PtrPushUnique( vNodes, Abc_ObjRegular(pNodeE) );
    }
    else
    {
        // collect the nodes in the implication supergate
        RetValue = Abc_NodeBalanceCone_rec( pNode, vNodes, 1, 1, 0 );
        assert( vNodes->nSize > 1 );
        // unmark the visited nodes
        Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
            Abc_ObjRegular(pNode)->fMarkB = 0;
        // if we found the node and its complement in the same implication supergate, 
        // return empty set of nodes (meaning that we should use constant-0 node)
        if ( RetValue == -1 )
            vNodes->nSize = 0;
    }
    // call for the fanin
    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pNode, i )
    {
        pNode = Abc_ObjRegular(pNode);
        if ( pNode->pCopy )
            continue;
        pNode->pCopy = (Abc_Obj_t *)Abc_NodeFindCone_rec( pNode );
    }
    return vNodes;
}

/**Function*************************************************************

  Synopsis    [Attaches the implication supergates to internal nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkBalanceAttach( Abc_Ntk_t * pNtk )
{
    Abc_Obj_t * pNode;
    int i;
    Abc_NtkCleanCopy( pNtk );
    Abc_NtkForEachCo( pNtk, pNode, i )
    {
        pNode = Abc_ObjFanin0(pNode);
        if ( pNode->pCopy )
            continue;
        pNode->pCopy = (Abc_Obj_t *)Abc_NodeFindCone_rec( pNode );
    }
}

/**Function*************************************************************

  Synopsis    [Attaches the implication supergates to internal nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkBalanceDetach( Abc_Ntk_t * pNtk )
{
    Abc_Obj_t * pNode;
    int i;
    Abc_NtkForEachNode( pNtk, pNode, i )
        if ( pNode->pCopy )
        {
            Vec_PtrFree( (Vec_Ptr_t *)pNode->pCopy );
            pNode->pCopy = NULL;
        }
}

/**Function*************************************************************

  Synopsis    [Compute levels of implication supergates.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkBalanceLevel_rec( Abc_Obj_t * pNode )
{
    Vec_Ptr_t * vSuper;
    Abc_Obj_t * pFanin;
    int i, LevelMax;
    assert( !Abc_ObjIsComplement(pNode) );
    if ( pNode->Level > 0 )
        return pNode->Level;
    if ( Abc_ObjIsCi(pNode) )
        return 0;
    vSuper = (Vec_Ptr_t *)pNode->pCopy;
    assert( vSuper != NULL );
    LevelMax = 0;
    Vec_PtrForEachEntry( Abc_Obj_t *, vSuper, pFanin, i )
    {
        pFanin = Abc_ObjRegular(pFanin);
        Abc_NtkBalanceLevel_rec(pFanin);
        if ( LevelMax < (int)pFanin->Level )
            LevelMax = pFanin->Level;
    }
    pNode->Level = LevelMax + 1;
    return pNode->Level;
}


/**Function*************************************************************

  Synopsis    [Compute levels of implication supergates.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkBalanceLevel( Abc_Ntk_t * pNtk )
{
    Abc_Obj_t * pNode;
    int i;
    Abc_NtkForEachObj( pNtk, pNode, i )
        pNode->Level = 0;
    Abc_NtkForEachCo( pNtk, pNode, i )
        Abc_NtkBalanceLevel_rec( Abc_ObjFanin0(pNode) );
}


/**Function*************************************************************

  Synopsis    [Marks the nodes on the critical and near critical paths.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkMarkCriticalNodes( Abc_Ntk_t * pNtk )
{
    Abc_Obj_t * pNode;
    int i, Counter = 0;
    Abc_NtkForEachNode( pNtk, pNode, i )
        if ( Abc_ObjRequiredLevel(pNode) - pNode->Level <= 1 )
            pNode->fMarkA = 1, Counter++;
    printf( "The number of nodes on the critical paths = %6d  (%5.2f %%)\n", Counter, 100.0 * Counter / Abc_NtkNodeNum(pNtk) );
}


////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


ABC_NAMESPACE_IMPL_END