abcHaig.c

Go to the documentation of this file.

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

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

#include "base/abc/abc.h"

ABC_NAMESPACE_IMPL_START


////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

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


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

  Synopsis    [Collects the nodes in the classes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Abc_NtkHaigCollectMembers( Hop_Man_t * p )
{
    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;
}

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

  Synopsis    [Creates classes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Abc_NtkHaigCreateClasses( Vec_Ptr_t * vMembers )
{
    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;
}

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

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkHaigCountFans( Hop_Man_t * p )
{
    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;
}


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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline Hop_Obj_t * Hop_ObjReprHop( Hop_Obj_t * pObj )
{
    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 );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline Hop_Obj_t * Hop_ObjChild0Hop( Hop_Obj_t * pObj ) { return Hop_NotCond( Hop_ObjReprHop(Hop_ObjFanin0(pObj)), Hop_ObjFaninC0(pObj) ); }
static inline Hop_Obj_t * Hop_ObjChild1Hop( Hop_Obj_t * pObj ) { return Hop_NotCond( Hop_ObjReprHop(Hop_ObjFanin1(pObj)), Hop_ObjFaninC1(pObj) ); }

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

  Synopsis    [Stops history AIG.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Hop_Man_t * Abc_NtkHaigReconstruct( Hop_Man_t * p )
{ 
    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;
}


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

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkHaigCheckTfi_rec( Abc_Obj_t * pNode, Abc_Obj_t * pOld )
{
    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 );
}

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

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkHaigCheckTfi( Abc_Ntk_t * pNtk, Abc_Obj_t * pOld, Abc_Obj_t * pNew )
{
    assert( !Abc_ObjIsComplement(pOld) );
    assert( !Abc_ObjIsComplement(pNew) );
    Abc_NtkIncrementTravId(pNtk);
    return Abc_NtkHaigCheckTfi_rec( pNew, pOld );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline Abc_Obj_t * Hop_ObjChild0Next( Hop_Obj_t * pObj ) { return Abc_ObjNotCond( (Abc_Obj_t *)Hop_ObjFanin0(pObj)->pNext, Hop_ObjFaninC0(pObj) );  }
static inline Abc_Obj_t * Hop_ObjChild1Next( Hop_Obj_t * pObj ) { return Abc_ObjNotCond( (Abc_Obj_t *)Hop_ObjFanin1(pObj)->pNext, Hop_ObjFaninC1(pObj) );  }

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

  Synopsis    [Stops history AIG.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Abc_Ntk_t * Abc_NtkHaigRecreateAig( Abc_Ntk_t * pNtk, Hop_Man_t * p )
{
    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;
}

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

  Synopsis    [Resets representatives.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_NtkHaigResetReprsOld( Hop_Man_t * pMan )
{
    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 );
}

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

  Synopsis    [Resets representatives.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abc_NtkHaigResetReprs( Hop_Man_t * p )
{
    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;
}

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

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Abc_Ntk_t * Abc_NtkHopRemoveLoops( Abc_Ntk_t * pNtk, Hop_Man_t * pMan )
{
    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;
}

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


ABC_NAMESPACE_IMPL_END