ntkisweep.c

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

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

  FileName    [ntkiSweep.c]

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

  Synopsis    [Implementation of the standard network sweep.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

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

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

#include "ntkiInt.h"

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

static bool Ntk_NetworkSweepIsetsDeriveTransformers( Ntk_Node_t * pNode, 
     Ntk_Node_t ** ppTrans1, Ntk_Node_t ** ppTrans2, bool fVerbose );


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

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

  Synopsis    [Standard network sweep.]

  Description [This command does the following interatively till 
  convergence: (1) removes the nodes that does not fanout (except PI nodes);
  (2) propagates constant nodes; (3) propagates single-output nodes whenever 
  possible (for example if the inverter feeds into a PO node, it is not 
  possible to collapse it into its fanout (it may be impossible if the 
  fanout in the primary output; (4) sweeps the constant-0 and duplicated
  i-sets of each node. Returns 1 if changes have been made to the network.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
bool Ntk_NetworkSweep( Ntk_Network_t * pNet, bool fSweepConsts, bool fSweepBuffers, bool fSweepIsets, bool fVerbose )
{
    Ntk_Node_t * pNode, * pNode2;
    bool fChange, fRecentChange;

    // assume there will be no changes
    fChange = 0;

    // perform topological cleanup
    do 
    {
        fRecentChange = 0;
        Ntk_NetworkForEachNodeSafe( pNet, pNode, pNode2 )
        {
            if ( Ntk_NodeReadFanoutNum(pNode) == 0 ) 
            {
                Ntk_NetworkDeleteNode( pNet, pNode, 1, 1 );
                fChange = fRecentChange = 1;
            }
        }
    }
    while ( fRecentChange );

    // perform combinational sweep
    if ( fSweepConsts || fSweepBuffers )
    {
        Ntk_NetworkDfs( pNet, 1 );
        Ntk_NetworkForEachNodeSpecial( pNet, pNode )
        {
            if ( Ntk_NetworkSweepNode( pNode, fSweepConsts, fSweepBuffers, fVerbose ) )
                fChange = 1;
        }
    }

    // in the MV networks, also sweep the i-sets
    if ( fSweepIsets )
    {
        Ntk_NetworkDfs( pNet, 1 );
        Ntk_NetworkForEachNodeSpecial( pNet, pNode )
        {
            if ( Ntk_NetworkSweepIsets( pNode, fVerbose ) )
                fChange = 1;
        }
    }

    // perform topological cleanup
    do 
    {
        fRecentChange = 0;
        Ntk_NetworkForEachNodeSafe( pNet, pNode, pNode2 )
        {
            if ( Ntk_NodeReadFanoutNum(pNode) == 0 ) 
            {
                Ntk_NetworkDeleteNode( pNet, pNode, 1, 1 );
                fChange = fRecentChange = 1;
            }
        }
    }
    while ( fRecentChange );

    if ( !Ntk_NetworkCheck( pNet ) )
        fprintf( Ntk_NetworkReadMvsisOut(pNet), "Ntk_NetworkSweep(): Network check has failed.\n" );
    return fChange;
}

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

  Synopsis    [Node sweep.]

  Description [If the first flag (fSweepConsts) is set, this procedure
  looks at the fanins of the node and collapses the constant fanins.
  Similarly, if the second flex (fSweepBuffers) is set, it collapses
  single-input fanins (these are buffers/inverters in the binary network,
  but may have more complex functionality in an MV network).]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
bool Ntk_NetworkSweepNode( Ntk_Node_t * pNode, bool fSweepConsts, bool fSweepBuffers, bool fVerbose )
{
    Ntk_Node_t * pFanin, * pFaninFanin;
    Ntk_Pin_t * pPin;
    bool fRecentChange;
    bool fChange;

    // TO DO: add here skipping the 'persistent' nodes

    // if this is a PO node and the fanin is the buffer, sweep it
    if ( pNode->Type == MV_NODE_CO && fSweepBuffers )
    {
        pFanin = Ntk_NodeReadFaninNode( pNode, 0 );
        // if the fanin has only one input, make sure its Cvr is derived
        if ( Ntk_NodeReadFaninNum(pFanin) == 1 )
            Ntk_NodeGetFuncCvr(pFanin);
        // check if the node is the binary buffer (this function uses Cvr)
        if ( Ntk_NodeIsBinaryBuffer(pFanin) )
        {
            // get the fanin's fanin
            pFaninFanin = Ntk_NodeReadFaninNode( pFanin, 0 );
            // patch the fanin of the CO node with the new fanin
            Ntk_NodePatchFanin( pNode, pFanin, pFaninFanin );
            // if the buffer does not fanout, it will be swept later
            return 1;
        }
        return 0;
    }

    // skip the nodes without functionality
    if ( pNode->Type != MV_NODE_INT )
        return 0;

    // collapse constant and single-input nodes
    fChange = 0;
    if ( fSweepConsts || fSweepBuffers )
    { 
        do
        {
            fRecentChange = 0;
            Ntk_NodeForEachFanin( pNode, pPin, pFanin )
            {
                if ( pFanin->Type == MV_NODE_CI )
                    continue;
                if ( fSweepConsts && Ntk_NodeReadFaninNum(pFanin) == 0 )
                {
                    if ( Ntk_NetworkCollapseNodes( pNode, pFanin ) )
                    {
                        fRecentChange = fChange = 1;
                        break;
                    }
                }
                if ( fSweepBuffers && Ntk_NodeReadFaninNum(pFanin) == 1 )
                {
                    if ( Ntk_NetworkCollapseNodes( pNode, pFanin ) )
                    {
                        fRecentChange = fChange = 1;
                        break;
                    }
                }
            }
        }
        while ( fRecentChange );
    }

    return fChange;
}


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

  Synopsis    [I-set sweep.]

  Description [This procedure looks at the i-sets of the node.
  If the node has an empty i-set or a duplicated i-set these are 
  reduced and the fanout nodes are updated accordingly.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
bool Ntk_NetworkSweepIsets( Ntk_Node_t * pNode, bool fVerbose )
{
    Ntk_Node_t * pTrans1, * pTrans2;
    Ntk_Node_t * pFanout;
    Ntk_Pin_t * pPin;

    // skip the nodes without functionality
    // TO DO: add here skipping the 'persistent' nodes
    if ( pNode->Type != MV_NODE_INT )
        return 0;
    // value sweep makes no sense for binary nodes