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

  FileName    [seqShare.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Construction and manipulation of sequential AIGs.]

  Synopsis    [Latch sharing at the fanout stems.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

#include "seqInt.h"

ABC_NAMESPACE_IMPL_START


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

static void Seq_NodeShareFanouts( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes );
static void Seq_NodeShareOne( Abc_Obj_t * pNode, Abc_InitType_t Init, Vec_Ptr_t * vNodes );

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

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

  Synopsis    [Transforms the sequential AIG to take fanout sharing into account.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Seq_NtkShareFanouts( Abc_Ntk_t * pNtk )
{
    Vec_Ptr_t * vNodes;
    Abc_Obj_t * pObj;
    int i;
    vNodes = Vec_PtrAlloc( 10 );
    // share the PI latches
    Abc_NtkForEachPi( pNtk, pObj, i )
        Seq_NodeShareFanouts( pObj, vNodes );
    // share the node latches
    Abc_NtkForEachNode( pNtk, pObj, i )
        Seq_NodeShareFanouts( pObj, vNodes );
    Vec_PtrFree( vNodes );
}

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

  Synopsis    [Transforms the node to take fanout sharing into account.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Seq_NodeShareFanouts( Abc_Obj_t * pNode, Vec_Ptr_t * vNodes )
{
    Abc_Obj_t * pFanout;
    Abc_InitType_t Type;
    int nLatches[4], i;
    // skip the node with only one fanout
    if ( Abc_ObjFanoutNum(pNode) < 2 )
        return;
    // clean the the fanout counters
    for ( i = 0; i < 4; i++ )
        nLatches[i] = 0;
    // find the number of fanouts having latches of each type
    Abc_ObjForEachFanout( pNode, pFanout, i )  
    {
        if ( Seq_ObjFanoutL(pNode, pFanout) == 0 )
            continue;
        Type = Seq_NodeGetInitLast( pFanout, Abc_ObjFanoutEdgeNum(pNode, pFanout) );
        nLatches[Type]++;
    }
    // decide what to do
    if ( nLatches[ABC_INIT_ZERO] > 1 && nLatches[ABC_INIT_ONE] > 1 ) // 0-group and 1-group
    {
        Seq_NodeShareOne( pNode, ABC_INIT_ZERO, vNodes );     // shares 0 and DC
        Seq_NodeShareOne( pNode, ABC_INIT_ONE,  vNodes );     // shares 1 and DC
    }
    else if ( nLatches[ABC_INIT_ZERO] > 1 ) // 0-group
        Seq_NodeShareOne( pNode, ABC_INIT_ZERO, vNodes );     // shares 0 and DC
    else if ( nLatches[ABC_INIT_ONE] > 1 ) // 1-group
        Seq_NodeShareOne( pNode, ABC_INIT_ONE,  vNodes );     // shares 1 and DC
    else if ( nLatches[ABC_INIT_DC] > 1 ) // DC-group
    {
        if ( nLatches[ABC_INIT_ZERO] > 0 )
            Seq_NodeShareOne( pNode, ABC_INIT_ZERO, vNodes ); // shares 0 and DC
        else 
            Seq_NodeShareOne( pNode, ABC_INIT_ONE,  vNodes ); // shares 1 and DC
    }
}

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

  Synopsis    [Transforms the node to take fanout sharing into account.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Seq_NodeShareOne( Abc_Obj_t * pNode, Abc_InitType_t Init, Vec_Ptr_t * vNodes )
{
    Vec_Int_t * vNums  = Seq_ObjLNums( pNode );
    Vec_Ptr_t * vInits = Seq_NodeLats( pNode );
    Abc_Obj_t * pFanout, * pBuffer;
    Abc_InitType_t Type, InitNew;
    int i;
    // collect the fanouts that satisfy the property (have initial value Init or DC)
    InitNew = ABC_INIT_DC;
    Vec_PtrClear( vNodes );
    Abc_ObjForEachFanout( pNode, pFanout, i )
    {
        if ( Seq_ObjFanoutL(pNode, pFanout) == 0 )
            continue;
        Type = Seq_NodeGetInitLast( pFanout, Abc_ObjFanoutEdgeNum(pNode, pFanout) );
        if ( Type == Init )
            InitNew = Init;
        if ( Type == Init || Type == ABC_INIT_DC )
        {
            Vec_PtrPush( vNodes, pFanout );
            Seq_NodeDeleteLast( pFanout, Abc_ObjFanoutEdgeNum(pNode, pFanout) );
        }
    }
    // create the new buffer
    pBuffer = Abc_NtkCreateNode( pNode->pNtk );
    Abc_ObjAddFanin( pBuffer, pNode );

    // grow storage for initial states
    Vec_PtrGrow( vInits, 2 * pBuffer->Id + 2 );
    for ( i = Vec_PtrSize(vInits); i < 2 * (int)pBuffer->Id + 2; i++ )
        Vec_PtrPush( vInits, NULL );
    // grow storage for numbers of latches
    Vec_IntGrow( vNums, 2 * pBuffer->Id + 2 );
    for ( i = Vec_IntSize(vNums); i < 2 * (int)pBuffer->Id + 2; i++ )
        Vec_IntPush( vNums, 0 );
    // insert the new latch
    Seq_NodeInsertFirst( pBuffer, 0, InitNew );

    // redirect the fanouts
    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pFanout, i )
        Abc_ObjPatchFanin( pFanout, pNode, pBuffer );
}





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

  Synopsis    [Maps virtual latches into real latches.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline unsigned Seq_NtkShareLatchesKey( Abc_Obj_t * pObj, Abc_InitType_t Init )
{
    return (pObj->Id << 2) | Init;
}

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

  Synopsis    [Maps virtual latches into real latches.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Abc_Obj_t * Seq_NtkShareLatches_rec( Abc_Ntk_t * pNtk, Abc_Obj_t * pObj, Seq_Lat_t * pRing, int nLatch, stmm_table * tLatchMap )
{
    Abc_Obj_t * pLatch, * pFanin;
    Abc_InitType_t Init;
    unsigned Key;
    if ( nLatch == 0 )
        return pObj;
    assert( pRing->pLatch == NULL );
    // get the latch on the previous level
    pFanin = Seq_NtkShareLatches_rec( pNtk, pObj, Seq_LatNext(pRing), nLatch - 1, tLatchMap );

    // get the initial state
    Init = Seq_LatInit( pRing );
    // check if the latch with this initial state exists
    Key = Seq_NtkShareLatchesKey( pFanin, Init );
    if ( stmm_lookup( tLatchMap, (char *)Key, (char **)&pLatch ) )
        return pRing->pLatch = pLatch;

    // does not exist
    if ( Init != ABC_INIT_DC )
    {
        // check if the don't-care exists
        Key = Seq_NtkShareLatchesKey( pFanin, ABC_INIT_DC );
        if ( stmm_lookup( tLatchMap, (char *)Key, (char **)&pLatch ) ) // yes
        {
            // update the table
            stmm_delete( tLatchMap, (char **)&Key, (char **)&pLatch );
            Key = Seq_NtkShareLatchesKey( pFanin, Init );
            stmm_insert( tLatchMap, (char *)Key, (char *)pLatch );
            // change don't-care to the given value
            pLatch->pData = (void *)Init;
            return pRing->pLatch = pLatch;
        }

        // add the latch with this value
        pLatch = Abc_NtkCreateLatch( pNtk );
        pLatch->pData = (void *)Init;
        Abc_ObjAddFanin( pLatch, pFanin );
        // add it to the table
        Key = Seq_NtkShareLatchesKey( pFanin, Init );
        stmm_insert( tLatchMap, (char *)Key, (char *)pLatch );
        return pRing->pLatch = pLatch;
    }
    // the init value is the don't-care

    // check if care values exist
    Key = Seq_NtkShareLatchesKey( pFanin, ABC_INIT_ZERO );
    if ( stmm_lookup( tLatchMap, (char *)Key, (char **)&pLatch ) )
    {
        Seq_LatSetInit( pRing, ABC_INIT_ZERO );
        return pRing->pLatch = pLatch;
    }
    Key = Seq_NtkShareLatchesKey( pFanin, ABC_INIT_ONE );
    if ( stmm_lookup( tLatchMap, (char *)Key, (char **)&pLatch ) )
    {
        Seq_LatSetInit( pRing, ABC_INIT_ONE );
        return pRing->pLatch = pLatch;
    }

    // create the don't-care latch
    pLatch = Abc_NtkCreateLatch( pNtk );
    pLatch->pData = (void *)ABC_INIT_DC;
    Abc_ObjAddFanin( pLatch, pFanin );
    // add it to the table
    Key = Seq_NtkShareLatchesKey( pFanin, ABC_INIT_DC );
    stmm_insert( tLatchMap, (char *)Key, (char *)pLatch );
    return pRing->pLatch = pLatch;
}

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

  Synopsis    [Maps virtual latches into real latches.]

  Description [Creates new latches and assigns them to virtual latches
  on the edges of a sequential AIG. The nodes of the new network should
  be created before this procedure is called.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Seq_NtkShareLatches( Abc_Ntk_t * pNtkNew, Abc_Ntk_t * pNtk )
{ 
    Abc_Obj_t * pObj, * pFanin;
    stmm_table * tLatchMap;
    int i;
    assert( Abc_NtkIsSeq( pNtk ) );
    tLatchMap = stmm_init_table( (int (*)(void))stmm_ptrcmp, (int (*)(void))stmm_ptrhash );
    Abc_AigForEachAnd( pNtk, pObj, i )
    {
        pFanin = Abc_ObjFanin0(pObj);
        Seq_NtkShareLatches_rec( pNtkNew, pFanin->pCopy, Seq_NodeGetRing(pObj,0), Seq_NodeCountLats(pObj,0), tLatchMap );
        pFanin = Abc_ObjFanin1(pObj);
        Seq_NtkShareLatches_rec( pNtkNew, pFanin->pCopy, Seq_NodeGetRing(pObj,1), Seq_NodeCountLats(pObj,1), tLatchMap );
    }
    Abc_NtkForEachPo( pNtk, pObj, i )
        Seq_NtkShareLatches_rec( pNtkNew, Abc_ObjFanin0(pObj)->pCopy, Seq_NodeGetRing(pObj,0), Seq_NodeCountLats(pObj,0), tLatchMap );
    stmm_free_table( tLatchMap );
}

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

  Synopsis    [Maps virtual latches into real latches.]

  Description [Creates new latches and assigns them to virtual latches
  on the edges of a sequential AIG. The nodes of the new network should
  be created before this procedure is called.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Seq_NtkShareLatchesMapping( Abc_Ntk_t * pNtkNew, Abc_Ntk_t * pNtk, Vec_Ptr_t * vMapAnds, int fFpga )
{ 
    Seq_Match_t * pMatch;
    Abc_Obj_t * pObj, * pFanout;
    stmm_table * tLatchMap;
    Vec_Ptr_t * vNodes;
    int i, k;
    assert( Abc_NtkIsSeq( pNtk ) );

    // start the table
    tLatchMap = stmm_init_table( (int (*)(void))stmm_ptrcmp, (int (*)(void))stmm_ptrhash );

    // create the array of all nodes with sharable fanouts
    vNodes = Vec_PtrAlloc( 100 );
    Vec_PtrPush( vNodes, Abc_AigConst1(pNtk) );
    Abc_NtkForEachPi( pNtk, pObj, i )
        Vec_PtrPush( vNodes, pObj );
    if ( fFpga )
    {
        Vec_PtrForEachEntry( Abc_Obj_t *, vMapAnds, pObj, i )
            Vec_PtrPush( vNodes, pObj );
    }
    else 
    {
        Vec_PtrForEachEntry( Abc_Obj_t *, vMapAnds, pMatch, i )
            Vec_PtrPush( vNodes, pMatch->pAnd );
    }

    // process nodes used in the mapping
    Vec_PtrForEachEntry( Abc_Obj_t *, vNodes, pObj, i )
    {
        // make sure the label is clean
        Abc_ObjForEachFanout( pObj, pFanout, k )
            assert( pFanout->fMarkC == 0 );
        Abc_ObjForEachFanout( pObj, pFanout, k )
        {
            if ( pFanout->fMarkC )
                continue;
            pFanout->fMarkC = 1;
            if ( Abc_ObjFaninId0(pFanout) == pObj->Id )
                Seq_NtkShareLatches_rec( pNtkNew, pObj->pCopy, Seq_NodeGetRing(pFanout,0), Seq_NodeCountLats(pFanout,0), tLatchMap );
            if ( Abc_ObjFaninId1(pFanout) == pObj->Id )
                Seq_NtkShareLatches_rec( pNtkNew, pObj->pCopy, Seq_NodeGetRing(pFanout,1), Seq_NodeCountLats(pFanout,1), tLatchMap );
        }
        // clean the label
        Abc_ObjForEachFanout( pObj, pFanout, k )
            pFanout->fMarkC = 0;
    }
    stmm_free_table( tLatchMap );
    // return to the old array
    Vec_PtrFree( vNodes );
}

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

  Synopsis    [Clean the latches after sharing them.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Seq_NtkShareLatchesClean( Abc_Ntk_t * pNtk )
{
    Abc_Obj_t * pObj;
    int i;
    assert( Abc_NtkIsSeq( pNtk ) );
    Abc_AigForEachAnd( pNtk, pObj, i )
    {
        Seq_NodeCleanLats( pObj, 0 );
        Seq_NodeCleanLats( pObj, 1 );
    }
    Abc_NtkForEachPo( pNtk, pObj, i )
        Seq_NodeCleanLats( pObj, 0 );
}

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

