shnetwork.c

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

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

  FileName    [shNetwork.c]

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

  Synopsis    []

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: shNetwork.c,v 1.2 2003/05/27 23:14:51 alanmi Exp $]

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

#include "shInt.h"

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

static int Sh_NetworkDfs_rec( Sh_Network_t * pNet, Sh_Node_t * pNode );
static int Sh_NetworkInterleaveNodes_rec( Sh_Network_t * pNet, Sh_Node_t * pNode );
static void Sh_NodePrintTree_rec( Sh_Node_t * pNode );

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

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

  Synopsis    [Computes the DFS ordering of the nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Sh_NetworkDfs( Sh_Network_t * pNet )
{
    int nNodesRes, i;
    // set the traversal ID for this DFS ordering
    Sh_NetworkIncrementTravId( pNet );
    // start the linked list
    Sh_NetworkStartSpecial( pNet );
    // traverse the TFI cones of all nodes in the array
    nNodesRes = 0;
    for ( i = 0; i < pNet->nOutputs; i++ )
        nNodesRes += Sh_NetworkDfs_rec( pNet, Sh_Regular(pNet->ppOutputs[i]) );
    for ( i = 0; i < pNet->nInputsCore; i++ )
        nNodesRes += Sh_NetworkDfs_rec( pNet, Sh_Regular(pNet->ppInputsCore[i]) );
    // finalize the linked list
    Sh_NetworkStopSpecial( pNet );
    pNet->nNodes = nNodesRes;
//    Sh_NetworkPrintSpecial( pNet );
    return nNodesRes;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Sh_NetworkDfs_rec( Sh_Network_t * pNet, Sh_Node_t * pNode )
{
    int nNodes;

    assert( !Sh_IsComplement(pNode) );

    // if this node is already visited, skip
    if ( Sh_NodeIsTravIdCurrent(pNet, pNode) )
    {
        // move the insertion point to be after this node
//        Sh_NetworkMoveSpecial( pNet, pNode );
        return 0;
    }

    // mark the node as visited
    Sh_NodeSetTravIdCurrent( pNet, pNode );

    // visit the transitive fanin
    nNodes = 0;
    if ( shNodeIsAnd(pNode) )
    {
        nNodes += Sh_NetworkDfs_rec( pNet, Sh_Regular(pNode->pOne) );
        nNodes += Sh_NetworkDfs_rec( pNet, Sh_Regular(pNode->pTwo) );
    }

    // add the node to the list 
    Sh_NetworkAddToSpecial( pNet, pNode );
    nNodes++;
    return nNodes;
}


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

  Synopsis    [Computes the interleaved ordering of nodes in the network.]

  Description [Interleaves the nodes using the algorithmm described
  in the paper: Fujii et al., "Interleaving Based Variable Ordering 
  Methods for OBDDs", ICCAD 1993.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Sh_NetworkInterleaveNodes( Sh_Network_t * pNet )
{
    int nNodesRes, i;
    // set the traversal ID for this DFS ordering
    Sh_NetworkIncrementTravId( pNet );
    // start the linked list
    Sh_NetworkStartSpecial( pNet );
    // traverse the TFI cones of all nodes in the array
    nNodesRes = 0;
    for ( i = 0; i < pNet->nOutputs; i++ )
        nNodesRes += Sh_NetworkInterleaveNodes_rec( pNet, Sh_Regular(pNet->ppOutputs[i]) );
    for ( i = 0; i < pNet->nInputsCore; i++ )
        nNodesRes += Sh_NetworkInterleaveNodes_rec( pNet, Sh_Regular(pNet->ppInputsCore[i]) );
    // finalize the linked list
    Sh_NetworkStopSpecial( pNet );
    pNet->nNodes = nNodesRes;
//    Sh_NetworkPrintSpecial( pNet );
    return nNodesRes;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Sh_NetworkInterleaveNodes_rec( Sh_Network_t * pNet, Sh_Node_t * pNode )
{
    int nNodes;

    assert( !Sh_IsComplement(pNode) );

    // if this node is already visited, skip
    if ( Sh_NodeIsTravIdCurrent(pNet, pNode) )
    {
        // move the insertion point to be after this node
        Sh_NetworkMoveSpecial( pNet, pNode );
        return 0;
    }

    // mark the node as visited
    Sh_NodeSetTravIdCurrent( pNet, pNode );

    // visit the transitive fanin
    nNodes = 0;
    if ( shNodeIsAnd(pNode) )
    {
        nNodes += Sh_NetworkInterleaveNodes_rec( pNet, Sh_Regular(pNode->pOne) );
        nNodes += Sh_NetworkInterleaveNodes_rec( pNet, Sh_Regular(pNode->pTwo) );
    }

    // add the node to the list 
    Sh_NetworkAddToSpecial( pNet, pNode );
    nNodes++;
    return nNodes;
}


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

  Synopsis    [Cleans the data fields of the nodes in the network.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sh_NetworkCleanData( Sh_Network_t * pNet )
{
    Sh_Node_t * pNode;
    int i;

    for ( i = 0; i < pNet->nInputs; i++ )
    {
        pNode = pNet->pMan->pVars[i];
        pNode->pData = pNode->pData2 = 0;
    }
    for ( i = 0; i < pNet->nSpecials; i++ )
    {
        pNode = Sh_Regular(pNet->ppSpecials[i]);
        pNode->pData = pNode->pData2 = 0;
    }
    for ( i = 0; i < pNet->nOutputsCore; i++ )
    {
        pNode = Sh_Regular(pNet->ppOutputsCore[i]);
        pNode->pData = pNode->pData2 = 0;
    }
    Sh_NetworkForEachNodeSpecial( pNet, pNode )
    {
        pNode->pData = pNode->pData2 = 0;
    }
}


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

  Synopsis    [Prints the array of nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sh_NodePrintTrees( Sh_Node_t * ppNodes[], int nNodes )
{
    int i;
    for ( i = 0; i < nNodes; i++ )
    {
        printf( "Root %2d :  \n", i );
        Sh_NodePrintTree_rec( Sh_Regular(ppNodes[i]) );
    }
}

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

  Synopsis    [Prints the array of nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sh_NodePrintTree_rec( Sh_Node_t * pNode )
{
    Sh_NodePrint( pNode );
    if ( shNodeIsAnd(pNode) )
    {
        Sh_NodePrintTree_rec( Sh_Regular(pNode->pOne) );
        Sh_NodePrintTree_rec( Sh_Regular(pNode->pTwo) );
    }
}


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

  Synopsis    [Prints the array of nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sh_NodePrintArray( Sh_Node_t * ppNodes[], int nNodes )
{
    int i;
    for ( i = 0; i < nNodes; i++ )
    {
        printf( "Node %2d :  ", i );
        Sh_NodePrint( ppNodes[i] );
    }
}

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

  Synopsis    [Prints the node and its "cofactors".]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sh_NodePrint( Sh_Node_t * pNode )
{
    Sh_NodePrintOne( pNode );
    if ( shNodeIsAnd(pNode) )
    {
        Sh_NodePrintOne( Sh_Regular(pNode)->pOne );
        Sh_NodePrintOne( Sh_Regular(pNode)->pTwo );
    }
    printf( "\n" );
}

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

  Synopsis    [Prints the node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sh_NodePrintOne( Sh_Node_t * pNode )
{
    Sh_Node_t * pNodeR;
    bool fCompl;

    pNodeR = Sh_Regular(pNode);
    fCompl = Sh_IsComplement(pNode);

    if ( (((unsigned)pNodeR) & ~0xffff) == 0 )
    {
        printf( "Error!  " );
        return;
    }

    printf( "num = %3d %c   ", pNodeR->Num, fCompl? 'c': ' ' );
    if ( shNodeIsConst(pNodeR) )
    {
        printf( "Const 1 " );
        return;
    }
    if ( !shNodeIsAnd(pNodeR) )
    {
        printf( "Var %3d ", (int)pNodeR->pTwo );
        return;
    }
    printf( "and     " );
}

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