wnderive.c

主要进行大规模的电路综合

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

  FileName    [wnDerive.c]

  PackageName [MVSIS 2.0: Multi-valued logic synthesis system.]

  Synopsis    [Computes the window centered about one node.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - February 1, 2003.]

  Revision    [$Id: wnDerive.c,v 1.3 2003/05/27 23:14:54 alanmi Exp $]

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

#include "wnInt.h"

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

static Wn_Window_t * Wn_WindowInit( Wn_Window_t * pWndCore, int nLevelsTfi, int nLevelsTfo );
static int           Wn_WindowSelectLeaves( Ntk_Network_t * pNet, Ntk_Node_t * ppNodes[] );
static int           Wn_WindowSelectRoots( Ntk_Network_t * pNet, Ntk_Node_t * ppNodes[] );
static int           Wn_WindowComputeTfiMarked( Ntk_Network_t * pNet, Ntk_Node_t * pNodes[], int nNodes, int Depth, bool fExistPath );
static int           Wn_WindowComputeTfiMarked_rec( Ntk_Node_t * pNode, int Depth, bool fExistPath );
static int           Wn_WindowComputeLeaves( Ntk_Network_t * pNet );
static void          Wn_WindowVerifyWindow( Wn_Window_t * pWnd );

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFITIONS                           ///
////////////////////////////////////////////////////////////////////////

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

  Synopsis    [Computes the window centered about one node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Wn_Window_t * Wn_WindowDerive( Wn_Window_t * pWndCore, int nLevelsTfi, int nLevelsTfo )
{
    Wn_Window_t * p;
    Ntk_Node_t ** pNodesStart;
    int nNodesStart, nNodesTfo, nNodesAll;
    int nLeaves, nLevels, i;
    bool fExistPath = 0; // when it is 1, theoretically the algorithm may not work...
    bool fVerbose = 0;

    // the window can be derived only if the core window is given
    assert( pWndCore );
    assert( pWndCore->pNet );

    // start a new window with the given window as its core
    p = Wn_WindowInit( pWndCore, nLevelsTfi, nLevelsTfo );

    // (1) find the window roots
    // collect the nodes of the core window
    Wn_WindowCollectInternal( pWndCore );
    // link the nodes in the limited TFO
    nNodesTfo = Ntk_NetworkComputeNodeTfo( p->pNet, pWndCore->ppNodes, pWndCore->nNodes, nLevelsTfo, 0, fExistPath );
    if ( fVerbose ) Ntk_NetworkPrintSpecial( p->pNet );
    // select the nodes exactly nLevelsTfo away with fanouts outside themselves
    p->ppRoots = ALLOC( Ntk_Node_t *, nNodesTfo + Ntk_NetworkReadCoNum(p->pNet) );
    p->nRoots = Wn_WindowSelectRoots( p->pNet, p->ppRoots );
    assert( p->nRoots <= nNodesTfo + Ntk_NetworkReadCoNum(p->pNet) );
    if ( fVerbose ) Ntk_NetworkPrintArray( p->ppRoots, p->nRoots );

    // (2) find part of starting leaves
    // link the nodes in the limited TFI
    nNodesStart = Ntk_NetworkComputeNodeTfi( p->pNet, pWndCore->ppNodes, pWndCore->nNodes, nLevelsTfi, 0, fExistPath );
    if ( fVerbose ) Ntk_NetworkPrintSpecial( p->pNet );
    // select the nodes exactly nLevelsTfi away with fanins outside themselves
    pNodesStart = ALLOC( Ntk_Node_t *, nNodesStart + Ntk_NetworkReadCiNum(p->pNet) );
    nNodesStart = Wn_WindowSelectLeaves( p->pNet, pNodesStart );
    if ( fVerbose ) Ntk_NetworkPrintArray( pNodesStart, nNodesStart );

    // (3) mark the nodes in the limited TFO of the leaves
    nLevels = Wn_WindowGetNumLevels( p->pWndCore );
    Ntk_NetworkComputeNodeTfo( p->pNet, pNodesStart, nNodesStart, nLevelsTfi + nLevelsTfo + nLevels - 1, 0, fExistPath );
    // make sure the current roots are marked
    for ( i = 0; i < p->nRoots; i++ )
        assert( Ntk_NodeIsTravIdCurrent(p->ppRoots[i]) );
    if ( fVerbose ) Ntk_NetworkPrintSpecial( p->pNet );

    // (4) collect the nodes in the limited TFI of the roots 
    // that overlap with the limited TFO of the leaves
    nNodesAll = Wn_WindowComputeTfiMarked( p->pNet, p->ppRoots, p->nRoots, nLevelsTfi + nLevelsTfo + nLevels - 1, fExistPath );
    // make sure the starting leaves are marked
    for ( i = 0; i < nNodesStart; i++ )
        assert( Ntk_NodeIsCi(pNodesStart[i]) || Ntk_NodeIsTravIdCurrent(pNodesStart[i]) );
    FREE( pNodesStart );
    // save these nodes
    p->ppNodes = ALLOC( Ntk_Node_t *, nNodesAll );
    p->nNodes = Ntk_NetworkCreateArrayFromSpecial( p->pNet, p->ppNodes );
    assert( p->nNodes == nNodesAll );
    if ( fVerbose ) Ntk_NetworkPrintSpecial( p->pNet );

    // (5) select the fanins of these nodes that are outside these nodes
    nLeaves = Wn_WindowComputeLeaves( p->pNet );
    // put these nodes into the array of leaves
    p->ppLeaves = ALLOC( Ntk_Node_t *, nLeaves );
    p->nLeaves = Ntk_NetworkCreateArrayFromSpecial( p->pNet, p->ppLeaves );
    if ( fVerbose ) Ntk_NetworkPrintSpecial( p->pNet );

    // (6) verify that the leaves are indeed the leaves of the window
    // make sure that the leaves fanout into nodes of the set
    // make sure that the roots fanin into nodes of the set
    Wn_WindowVerifyWindow( p );
    return p;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Wn_Window_t * Wn_WindowInit( Wn_Window_t * pWndCore, int nLevelsTfi, int nLevelsTfo )
{
    Wn_Window_t * p;
    p = ALLOC( Wn_Window_t, 1 );
    memset( p, 0, sizeof(Wn_Window_t) );
    p->nLevelsTfi = nLevelsTfi;
    p->nLevelsTfo = nLevelsTfo;
    p->pWndCore   = pWndCore;
    p->pNet       = pWndCore->pNet;
    return p;
}


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

  Synopsis    [Select the roots from the list of TFO nodes.]

  Description [The roots are the nodes belonging to the limited TFO cone
  that (1) fanout outside of this cone (possibly into COs), and 
  (2) have at least one fanin that is not the root itself.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Wn_WindowSelectRoots( Ntk_Network_t * pNet, Ntk_Node_t * ppNodes[] )
{
    Ntk_Node_t * pNode, * pFanout;
    Ntk_Pin_t * pPin;
    int nRoots;

    // mark all the nodes that belong to the limited TFO cone
    Ntk_NetworkIncrementTravId( pNet );
    Ntk_NetworkForEachNodeSpecial( pNet, pNode )
        Ntk_NodeSetTravIdCurrent( pNode );

    // go through these nodes and collect those of them that fanout outside
    nRoots = 0;
    Ntk_NetworkForEachNodeSpecial( pNet, pNode )
    {
        // check the node's fanins
        Ntk_NodeForEachFanout( pNode, pPin, pFanout )
            if ( !Ntk_NodeIsTravIdCurrent(pFanout) )
            {
                ppNodes[ nRoots++ ] = pNode;
                break;
            }
    }
    return nRoots;
}

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

  Synopsis    [Select the leaves from the list of TFI nodes.]

  Description [The leaves are the nodes that (1) are exactly the given
  distance away and (2) have at least one fanout that is not a leaf itself.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Wn_WindowSelectLeaves( Ntk_Network_t * pNet, Ntk_Node_t * ppNodes[] )
{
    Ntk_Node_t * pNode, * pFanin, * pFanout;
    Ntk_Pin_t * pPin;
    int nLeaves;

    // mark all the nodes that have level 0
    Ntk_NetworkIncrementTravId( pNet );
    Ntk_NetworkForEachNodeSpecial( pNet, pNode )
        if ( pNode->Level == 0 )
            Ntk_NodeSetTravIdCurrent( pNode );

    // go through these nodes and collect those
    // that have at least one fanout that not marked
    nLeaves = 0;
    Ntk_NetworkForEachNodeSpecial( pNet, pNode )
    {
        // if the node has CI fanins that are not added yet, add them
        Ntk_NodeForEachFanin( pNode, pPin, pFanin )
            if ( Ntk_NodeIsCi(pFanin) )
            { // the fanin is CI
                if ( !Ntk_NodeIsTravIdCurrent(pFanin) ) // is not visited
                {
                     ppNodes[ nLeaves++ ] = pFanin; // add
                     Ntk_NodeSetTravIdCurrent( pFanin ); // mark as visited
                }
            }

        if ( pNode->Level == 0 )
        {   // check the node's fanins
            Ntk_NodeForEachFanout( pNode, pPin, pFanout )
                if ( !Ntk_NodeIsTravIdCurrent(pFanout) )
                {
                    ppNodes[ nLeaves++ ] = pNode;
                    break;
                }
        }
        else
        { 
        }
    }
    return nLeaves;
}

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

  Synopsis    [Collects the marked limited TFI of the set of nodes.]