abcBalance.c File Reference

#include "base/abc/abc.h"

Include dependency graph for abcBalance.c:

Go to the source code of this file.

Functions
Abc_Ntk_t *	Abc_NtkBalance (Abc_Ntk_t *pNtk, int fDuplicate, int fSelective, int fUpdateLevel)
	FUNCTION DEFINITIONS ///.
int	Abc_NodeBalanceFindLeft (Vec_Ptr_t *vSuper)
void	Abc_NodeBalancePermute (Abc_Ntk_t *pNtkNew, Vec_Ptr_t *vSuper, int LeftBound)
int	Abc_NodeBalanceConeExor_rec (Abc_Obj_t *pNode, Vec_Ptr_t *vSuper, int fFirst)
Vec_Ptr_t *	Abc_NodeFindCone_rec (Abc_Obj_t *pNode)
void	Abc_NtkBalanceAttach (Abc_Ntk_t *pNtk)
void	Abc_NtkBalanceDetach (Abc_Ntk_t *pNtk)
int	Abc_NtkBalanceLevel_rec (Abc_Obj_t *pNode)
void	Abc_NtkBalanceLevel (Abc_Ntk_t *pNtk)

Function Documentation

Abc_NodeBalanceConeExor_rec()

int Abc_NodeBalanceConeExor_rec	(	Abc_Obj_t *	pNode,
		Vec_Ptr_t *	vSuper,
		int	fFirst )

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 392 of file abcBalance.c.

{
    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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_NodeBalanceFindLeft()

int Abc_NodeBalanceFindLeft

(

Vec_Ptr_t *

vSuper

)

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 []

Definition at line 154 of file abcBalance.c.

{
    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;
}

Abc_NodeBalancePermute()

void Abc_NodeBalancePermute	(	Abc_Ntk_t *	pNtkNew,
		Vec_Ptr_t *	vSuper,
		int	LeftBound )

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 []

Definition at line 192 of file abcBalance.c.

{
    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 );
    }
*/
}

Here is the call graph for this function:

Abc_NodeFindCone_rec()

Vec_Ptr_t * Abc_NodeFindCone_rec

(

Abc_Obj_t *

pNode

)

Function*************************************************************

Synopsis [Collects the nodes in the implication supergate.]

Description []

SideEffects []

SeeAlso []

Definition at line 453 of file abcBalance.c.

{
    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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_NtkBalance()

Abc_Ntk_t * Abc_NtkBalance	(	Abc_Ntk_t *	pNtk,
		int	fDuplicate,
		int	fSelective,
		int	fUpdateLevel )

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Balances the AIG network.]

Description []

SideEffects []

SeeAlso []

Definition at line 53 of file abcBalance.c.

{
//    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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_NtkBalanceAttach()

void Abc_NtkBalanceAttach

(

Abc_Ntk_t *

pNtk

)

Function*************************************************************

Synopsis [Attaches the implication supergates to internal nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 506 of file abcBalance.c.

{
    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 );
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_NtkBalanceDetach()

void Abc_NtkBalanceDetach

(

Abc_Ntk_t *

pNtk

)

Function*************************************************************

Synopsis [Attaches the implication supergates to internal nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 531 of file abcBalance.c.

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

Here is the caller graph for this function:

Abc_NtkBalanceLevel()

void Abc_NtkBalanceLevel

(

Abc_Ntk_t *

pNtk

)

Function*************************************************************

Synopsis [Compute levels of implication supergates.]

Description []

SideEffects []

SeeAlso []

Definition at line 590 of file abcBalance.c.

{
    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) );
}

Here is the call graph for this function:

Abc_NtkBalanceLevel_rec()

int Abc_NtkBalanceLevel_rec

(

Abc_Obj_t *

pNode

)

Function*************************************************************

Synopsis [Compute levels of implication supergates.]

Description []

SideEffects []

SeeAlso []

Definition at line 554 of file abcBalance.c.

{
    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;
}

Here is the call graph for this function:

Here is the caller graph for this function: