abcHaig.c File Reference

#include "base/abc/abc.h"

Go to the source code of this file.

Functions
ABC_NAMESPACE_IMPL_START Vec_Ptr_t *	Abc_NtkHaigCollectMembers (Hop_Man_t *p)
	DECLARATIONS ///. More...
Vec_Ptr_t *	Abc_NtkHaigCreateClasses (Vec_Ptr_t *vMembers)
int	Abc_NtkHaigCountFans (Hop_Man_t *p)
static Hop_Obj_t *	Hop_ObjReprHop (Hop_Obj_t *pObj)
static Hop_Obj_t *	Hop_ObjChild0Hop (Hop_Obj_t *pObj)
static Hop_Obj_t *	Hop_ObjChild1Hop (Hop_Obj_t *pObj)
Hop_Man_t *	Abc_NtkHaigReconstruct (Hop_Man_t *p)
int	Abc_NtkHaigCheckTfi_rec (Abc_Obj_t *pNode, Abc_Obj_t *pOld)
int	Abc_NtkHaigCheckTfi (Abc_Ntk_t *pNtk, Abc_Obj_t *pOld, Abc_Obj_t *pNew)
static Abc_Obj_t *	Hop_ObjChild0Next (Hop_Obj_t *pObj)
static Abc_Obj_t *	Hop_ObjChild1Next (Hop_Obj_t *pObj)
Abc_Ntk_t *	Abc_NtkHaigRecreateAig (Abc_Ntk_t *pNtk, Hop_Man_t *p)
void	Abc_NtkHaigResetReprsOld (Hop_Man_t *pMan)
int	Abc_NtkHaigResetReprs (Hop_Man_t *p)
Abc_Ntk_t *	Abc_NtkHopRemoveLoops (Abc_Ntk_t *pNtk, Hop_Man_t *pMan)

Function Documentation

int Abc_NtkHaigCheckTfi	(	Abc_Ntk_t *	pNtk,
		Abc_Obj_t *	pOld,
		Abc_Obj_t *	pNew
	)

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

Synopsis [Returns 1 if pOld is in the TFI of pNew.]

Description []

SideEffects []

SeeAlso []

Definition at line 311 of file abcHaig.c.

{
    assert( !Abc_ObjIsComplement(pOld) );
    assert( !Abc_ObjIsComplement(pNew) );
    Abc_NtkIncrementTravId(pNtk);
    return Abc_NtkHaigCheckTfi_rec( pNew, pOld );
}

int Abc_NtkHaigCheckTfi_rec	(	Abc_Obj_t *	pNode,
		Abc_Obj_t *	pOld
	)

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

Synopsis [Returns 1 if pOld is in the TFI of pNew.]

Description []

SideEffects []

SeeAlso []

Definition at line 276 of file abcHaig.c.

{
    if ( pNode == NULL )
        return 0;
    if ( pNode == pOld )
        return 1;
    // check the trivial cases
    if ( Abc_ObjIsCi(pNode) )
        return 0;
    assert( Abc_ObjIsNode(pNode) );
    // if this node is already visited, skip
    if ( Abc_NodeIsTravIdCurrent( pNode ) )
        return 0;
    // mark the node as visited
    Abc_NodeSetTravIdCurrent( pNode );
    // check the children
    if ( Abc_NtkHaigCheckTfi_rec( Abc_ObjFanin0(pNode), pOld ) )
        return 1;
    if ( Abc_NtkHaigCheckTfi_rec( Abc_ObjFanin1(pNode), pOld ) )
        return 1;
    // check equivalent nodes
    return Abc_NtkHaigCheckTfi_rec( (Abc_Obj_t *)pNode->pData, pOld );
}

ABC_NAMESPACE_IMPL_START Vec_Ptr_t* Abc_NtkHaigCollectMembers

(

Hop_Man_t *

p

)

DECLARATIONS ///.

CFile****************************************************************

FileName [abcHaig.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Network and node package.]

Synopsis [Implements history AIG for combinational rewriting.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id:

abcHaig.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

]FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis [Collects the nodes in the classes.]

Description []

SideEffects []

SeeAlso []

Definition at line 46 of file abcHaig.c.

{
    Vec_Ptr_t * vObjs;
    Hop_Obj_t * pObj;
    int i;
    vObjs = Vec_PtrAlloc( 4098 );
    Vec_PtrForEachEntry( Hop_Obj_t *, p->vObjs, pObj, i )
    {
        if ( pObj->pData == NULL )
            continue;
        pObj->pData = Hop_ObjRepr( pObj );
        Vec_PtrPush( vObjs, pObj );
    }
    return vObjs;
}

int Abc_NtkHaigCountFans

(

Hop_Man_t *

p

)

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

Synopsis [Counts how many data members have non-trivial fanout.]

Description []

SideEffects []

SeeAlso []

Definition at line 159 of file abcHaig.c.

{
    Hop_Obj_t * pObj;
    int i, Counter = 0;
    Vec_PtrForEachEntry( Hop_Obj_t *, p->vObjs, pObj, i )
    {
        if ( pObj->pData == NULL )
            continue;
        if ( Hop_ObjRefs(pObj) > 0 )
            Counter++;
    }
    printf( "The number of class members with fanouts = %5d.\n", Counter );
    return Counter;
}

Vec_Ptr_t* Abc_NtkHaigCreateClasses

(

Vec_Ptr_t *

vMembers

)

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

Synopsis [Creates classes.]

Description []

SideEffects []

SeeAlso []

Definition at line 73 of file abcHaig.c.

{
    Vec_Ptr_t * vClasses;
    Hop_Obj_t * pObj, * pRepr;
    int i;

    // count classes
    vClasses = Vec_PtrAlloc( 4098 );
    Vec_PtrForEachEntry( Hop_Obj_t *, vMembers, pObj, i )
    {
        pRepr = (Hop_Obj_t *)pObj->pData;
        assert( pRepr->pData == NULL );
        if ( pRepr->fMarkA == 0 ) // new
        {
            pRepr->fMarkA = 1;
            Vec_PtrPush( vClasses, pRepr );
        }
    }

    // set representatives as representatives
    Vec_PtrForEachEntry( Hop_Obj_t *, vClasses, pObj, i )
    {
        pObj->fMarkA = 0;
        pObj->pData = pObj;
    }

    // go through the members and update
    Vec_PtrForEachEntry( Hop_Obj_t *, vMembers, pObj, i )
    {
        pRepr = (Hop_Obj_t *)pObj->pData;
        if ( ((Hop_Obj_t *)pRepr->pData)->Id > pObj->Id )
            pRepr->pData = pObj;
    }

    // change representatives of the class
    Vec_PtrForEachEntry( Hop_Obj_t *, vMembers, pObj, i )
    {
        pRepr = (Hop_Obj_t *)pObj->pData;
        pObj->pData = pRepr->pData;
        assert( ((Hop_Obj_t *)pObj->pData)->Id <= pObj->Id );
    }

    // update classes
    Vec_PtrForEachEntry( Hop_Obj_t *, vClasses, pObj, i )
    {
        pRepr = (Hop_Obj_t *)pObj->pData;
        assert( pRepr->pData == pRepr );
//        pRepr->pData = NULL;
        Vec_PtrWriteEntry( vClasses, i, pRepr );
        Vec_PtrPush( vMembers, pObj );
    }

    Vec_PtrForEachEntry( Hop_Obj_t *, vMembers, pObj, i )
        if ( pObj->pData == pObj )
            pObj->pData = NULL;

/*
    Vec_PtrForEachEntry( Hop_Obj_t *, vMembers, pObj, i )
    {
        printf( "ObjId = %4d : ", pObj->Id );
        if ( pObj->pData == NULL )
        {
            printf( "NULL" );
        }
        else
        {
            printf( "%4d", ((Hop_Obj_t *)pObj->pData)->Id );
            assert( ((Hop_Obj_t *)pObj->pData)->Id <= pObj->Id );
        }
        printf( "\n" );
    }
*/
    return vClasses;
}

Hop_Man_t* Abc_NtkHaigReconstruct

(

Hop_Man_t *

p

)

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

Synopsis [Stops history AIG.]

Description []

SideEffects []

SeeAlso []

Definition at line 222 of file abcHaig.c.

{ 
    Hop_Man_t * pNew;
    Hop_Obj_t * pObj;
    int i, Counter = 0;
    Vec_PtrForEachEntry( Hop_Obj_t *, p->vObjs, pObj, i )
        pObj->pNext = NULL;
    // start the HOP package
    pNew = Hop_ManStart();
    pNew->vObjs = Vec_PtrAlloc( p->nCreated );
    Vec_PtrPush( pNew->vObjs, Hop_ManConst1(pNew) );
    // map the constant node
    Hop_ManConst1(p)->pNext = Hop_ManConst1(pNew);
    // map the CIs
    Hop_ManForEachPi( p, pObj, i )
        pObj->pNext = Hop_ObjCreatePi(pNew);
    // map the internal nodes
    Vec_PtrForEachEntry( Hop_Obj_t *, p->vObjs, pObj, i )
    {
        if ( !Hop_ObjIsNode(pObj) )
            continue;
        pObj->pNext = Hop_And( pNew, Hop_ObjChild0Hop(pObj), Hop_ObjChild1Hop(pObj) );
//        assert( !Hop_IsComplement(pObj->pNext) );
        if ( Hop_ManConst1(pNew) == Hop_Regular(pObj->pNext) )
            Counter++;
        if ( pObj->pData ) // member of the class
            Hop_Regular(pObj->pNext)->pData = Hop_Regular(((Hop_Obj_t *)pObj->pData)->pNext);
    }
//    printf( " Counter = %d.\n", Counter );
    // transfer the POs
    Hop_ManForEachPo( p, pObj, i )
        Hop_ObjCreatePo( pNew, Hop_ObjChild0Hop(pObj) );
    // check the new manager
    if ( !Hop_ManCheck(pNew) )
    {
        printf( "Abc_NtkHaigReconstruct: Check for History AIG has failed.\n" );
        Hop_ManStop(pNew);
        return NULL;
    }
    return pNew;
}

Abc_Ntk_t* Abc_NtkHaigRecreateAig	(	Abc_Ntk_t *	pNtk,
		Hop_Man_t *	p
	)

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

Synopsis [Stops history AIG.]

Description []

SideEffects []

SeeAlso []

Definition at line 344 of file abcHaig.c.

{
    Abc_Ntk_t * pNtkAig;
    Abc_Obj_t * pObjOld, * pObjAbcThis, * pObjAbcRepr;
    Hop_Obj_t * pObj;
    int i;
    assert( p->nCreated == Vec_PtrSize(p->vObjs) );

    // start the new network
    pNtkAig = Abc_NtkStartFrom( pNtk, ABC_NTK_STRASH, ABC_FUNC_AIG );

    // transfer new nodes to the PIs of HOP
    Hop_ManConst1(p)->pNext = (Hop_Obj_t *)Abc_AigConst1( pNtkAig );
    Hop_ManForEachPi( p, pObj, i )
        pObj->pNext = (Hop_Obj_t *)Abc_NtkCi( pNtkAig, i );

    // construct new nodes
    Vec_PtrForEachEntry( Hop_Obj_t *, p->vObjs, pObj, i )
    {
        if ( !Hop_ObjIsNode(pObj) )
            continue;
        pObj->pNext = (Hop_Obj_t *)Abc_AigAnd( (Abc_Aig_t *)pNtkAig->pManFunc, Hop_ObjChild0Next(pObj), Hop_ObjChild1Next(pObj) );
        assert( !Hop_IsComplement(pObj->pNext) );
    }

    // set the COs
    Abc_NtkForEachCo( pNtk, pObjOld, i )
        Abc_ObjAddFanin( pObjOld->pCopy, Hop_ObjChild0Next(Hop_ManPo(p,i)) );

    // construct choice nodes
    Vec_PtrForEachEntry( Hop_Obj_t *, p->vObjs, pObj, i )
    {
        // skip the node without choices
        if ( pObj->pData == NULL )
            continue;
        // skip the representative of the class
        if ( pObj->pData == pObj )
            continue;
        // do not create choices for constant 1 and PIs
        if ( !Hop_ObjIsNode((Hop_Obj_t *)pObj->pData) )
            continue;
        // get the corresponding new nodes
        pObjAbcThis = (Abc_Obj_t *)pObj->pNext;
        pObjAbcRepr = (Abc_Obj_t *)((Hop_Obj_t *)pObj->pData)->pNext;
        // the new node cannot be already in the class
        assert( pObjAbcThis->pData == NULL );
        // the new node cannot have fanouts
        assert( Abc_ObjFanoutNum(pObjAbcThis) == 0 );
        // these should be different nodes
        assert( pObjAbcRepr != pObjAbcThis );
        // do not create choices if there is a path from pObjAbcThis to pObjAbcRepr
        if ( !Abc_NtkHaigCheckTfi( pNtkAig, pObjAbcRepr, pObjAbcThis ) )
        {
            // find the last node in the class
            while ( pObjAbcRepr->pData )
                pObjAbcRepr = (Abc_Obj_t *)pObjAbcRepr->pData;
            // add the new node at the end of the list
            pObjAbcRepr->pData = pObjAbcThis;
        }
    }

    // finish the new network
//    Abc_NtkFinalize( pNtk, pNtkAig );
//    Abc_AigCleanup( pNtkAig->pManFunc );
    // check correctness of the network
    if ( !Abc_NtkCheck( pNtkAig ) )
    {
        printf( "Abc_NtkHaigUse: The network check has failed.\n" );
        Abc_NtkDelete( pNtkAig );
        return NULL;
    }
    return pNtkAig;
}

int Abc_NtkHaigResetReprs

(

Hop_Man_t *

p

)

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

Synopsis [Resets representatives.]

Description []

SideEffects []

SeeAlso []

Definition at line 457 of file abcHaig.c.

{
    Hop_Obj_t * pObj, * pRepr;
    int i, nClasses, nMembers, nFanouts, nNormals;
    // clear self-classes
    Vec_PtrForEachEntry( Hop_Obj_t *, p->vObjs, pObj, i )
    {
        // fix the strange situation of double-loop
        pRepr = (Hop_Obj_t *)pObj->pData;
        if ( pRepr && pRepr->pData == pObj )
            pRepr->pData = pRepr;
        // remove self-loops
        if ( pObj->pData == pObj )
            pObj->pData = NULL;
    }
    // set representatives
    Vec_PtrForEachEntry( Hop_Obj_t *, p->vObjs, pObj, i )
    {
        if ( pObj->pData == NULL )
            continue;
        // get representative of the node
        pRepr = Hop_ObjRepr( pObj );
        pRepr->pData = pRepr;
        // set the representative
        pObj->pData = pRepr;
    }
    // make each class point to the smallest topological order
    Vec_PtrForEachEntry( Hop_Obj_t *, p->vObjs, pObj, i )
    {
        if ( pObj->pData == NULL )
            continue;
        pRepr = Hop_ObjRepr( pObj );
        if ( pRepr->Id > pObj->Id )
        {
            pRepr->pData = pObj;
            pObj->pData = pObj;
        }
        else
            pObj->pData = pRepr;
    }
    // count classes, members, and fanouts - and verify
    nMembers = nClasses = nFanouts = nNormals = 0;
    Vec_PtrForEachEntry( Hop_Obj_t *, p->vObjs, pObj, i )
    {
        if ( pObj->pData == NULL )
            continue;
        // count members
        nMembers++;
        // count the classes and fanouts
        if ( pObj->pData == pObj )
            nClasses++;
        else if ( Hop_ObjRefs(pObj) > 0 )
            nFanouts++;
        else
            nNormals++;
        // compare representatives
        pRepr = Hop_ObjRepr( pObj );
        assert( pObj->pData == pRepr );
        assert( pRepr->Id <= pObj->Id );
    }
//    printf( "Nodes = %7d.  Member = %7d.  Classes = %6d.  Fanouts = %6d.  Normals = %6d.\n", 
//        Hop_ManNodeNum(p), nMembers, nClasses, nFanouts, nNormals );
    return nFanouts;
}

void Abc_NtkHaigResetReprsOld

(

Hop_Man_t *

pMan

)

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

Synopsis [Resets representatives.]

Description []

SideEffects []

SeeAlso []

Definition at line 429 of file abcHaig.c.

{
    Vec_Ptr_t * vMembers, * vClasses;

    // collect members of the classes and make them point to reprs
    vMembers = Abc_NtkHaigCollectMembers( pMan );
    printf( "Collected %6d class members.\n", Vec_PtrSize(vMembers) );

    // create classes
    vClasses = Abc_NtkHaigCreateClasses( vMembers );
    printf( "Collected %6d classes. (Ave = %5.2f)\n", Vec_PtrSize(vClasses), 
        (float)(Vec_PtrSize(vMembers))/Vec_PtrSize(vClasses) );

    Vec_PtrFree( vMembers );
    Vec_PtrFree( vClasses );
}

Abc_Ntk_t* Abc_NtkHopRemoveLoops	(	Abc_Ntk_t *	pNtk,
		Hop_Man_t *	pMan
	)

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

Synopsis [Transform HOP manager into the one without loops.]

Description []

SideEffects []

SeeAlso []

Definition at line 533 of file abcHaig.c.

{
    Abc_Ntk_t * pNtkAig;
    Hop_Man_t * pManTemp;

    // iteratively reconstruct the HOP manager to create choice nodes
    while ( Abc_NtkHaigResetReprs( pMan ) )
    {
        pMan = Abc_NtkHaigReconstruct( pManTemp = pMan );
        Hop_ManStop( pManTemp );
    }

    // traverse in the topological order and create new AIG
    pNtkAig = Abc_NtkHaigRecreateAig( pNtk, pMan );
    Hop_ManStop( pMan );
    return pNtkAig;
}

static Hop_Obj_t* Hop_ObjChild0Hop ( Hop_Obj_t *  pObj )

inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 208 of file abcHaig.c.

{ return Hop_NotCond( Hop_ObjReprHop(Hop_ObjFanin0(pObj)), Hop_ObjFaninC0(pObj) ); }

static Abc_Obj_t* Hop_ObjChild0Next ( Hop_Obj_t *  pObj )

inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 330 of file abcHaig.c.

{ return Abc_ObjNotCond( (Abc_Obj_t *)Hop_ObjFanin0(pObj)->pNext, Hop_ObjFaninC0(pObj) );  }

static Hop_Obj_t* Hop_ObjChild1Hop ( Hop_Obj_t *  pObj )

inlinestatic

Definition at line 209 of file abcHaig.c.

{ return Hop_NotCond( Hop_ObjReprHop(Hop_ObjFanin1(pObj)), Hop_ObjFaninC1(pObj) ); }

static Abc_Obj_t* Hop_ObjChild1Next ( Hop_Obj_t *  pObj )

inlinestatic

Definition at line 331 of file abcHaig.c.

{ return Abc_ObjNotCond( (Abc_Obj_t *)Hop_ObjFanin1(pObj)->pNext, Hop_ObjFaninC1(pObj) );  }

static Hop_Obj_t* Hop_ObjReprHop ( Hop_Obj_t *  pObj )

inlinestatic

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 186 of file abcHaig.c.

{
    Hop_Obj_t * pRepr;
    assert( pObj->pNext != NULL );
    if ( pObj->pData == NULL )
        return pObj->pNext;
    pRepr = (Hop_Obj_t *)pObj->pData;
    assert( pRepr->pData == pRepr );
    return Hop_NotCond( pRepr->pNext, pObj->fPhase ^ pRepr->fPhase );
}