ntkdfs.c

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

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

  FileName    [ntkDfs.c]

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

  Synopsis    [Various procedures to put/get/traverse nodes in the DFS order.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: ntkDfs.c,v 1.33 2003/05/27 23:14:21 alanmi Exp $]

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

#include "ntkInt.h"

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

static void Ntk_NetworkDfsFromOutputs_rec( Ntk_Node_t * pNode );
static void Ntk_NetworkDfsFromInputs_rec( Ntk_Node_t * pNode );
static int  Ntk_NetworkLevelizeFromOutputs_rec( Ntk_Node_t * pNode );
static int  Ntk_NetworkLevelizeFromInputs_rec( Ntk_Node_t * pNode );
static int  Ntk_NetworkGetNumLevels_rec( Ntk_Node_t * pNode );
static bool Ntk_NetworkIsAcyclic1_rec( Ntk_Node_t * pNode, st_table * tPath );
static bool Ntk_NetworkIsAcyclic2_rec( Ntk_Node_t * pNode, Ntk_Node_t ** pPath, int Step );
static bool Ntk_NetworkIsAcyclic_rec( Ntk_Node_t * pNode );
static int  Ntk_NetworkComputeNodeSupport_rec( Ntk_Node_t * pNode );
static int  Ntk_NetworkInterleaveNodes_rec( Ntk_Node_t * pNode );
static int  Ntk_NetworkComputeNodeTfi_rec( Ntk_Node_t * pNode, int Depth, bool fIncludeCis, bool fExistPath );
static int  Ntk_NetworkComputeNodeTfo_rec( Ntk_Node_t * pNode, int Depth, bool fIncludeCos, bool fExistPath );

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

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

  Synopsis    [Links the nodes of the network in the DFS order.]

  Description [The nodes that do not fanout into the COs are not collected.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Ntk_NetworkDfs( Ntk_Network_t * pNet, bool fFromOutputs )
{
    Ntk_Node_t * pNode;

    // set the traversal ID
    Ntk_NetworkIncrementTravId( pNet );
    // start the linked list
    Ntk_NetworkStartSpecial( pNet );
    // traverse and link the nodes
    if ( fFromOutputs )
    { // start DFS from the primary outputs
        Ntk_NetworkForEachCo( pNet, pNode )
            Ntk_NetworkDfsFromOutputs_rec( pNode );
    }
    else
    { // start DFS from the primary inputs
        Ntk_NetworkForEachCi( pNet, pNode )
            Ntk_NetworkDfsFromInputs_rec( pNode );
    }
    // finalize the linked list
    Ntk_NetworkStopSpecial( pNet );
}

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

  Synopsis    [Links the nodes reachable in the DFS order from the given nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Ntk_NetworkDfsNodes( Ntk_Network_t * pNet, Ntk_Node_t * ppNodes[], int nNodes, int fFromOutputs )
{
    int i;

    // set the traversal ID for this DFS ordering
    Ntk_NetworkIncrementTravId( pNet );
    // start the linked list
    Ntk_NetworkStartSpecial( pNet );
    // traverse and link the nodes
    if ( fFromOutputs )
    {
        for ( i = 0; i < nNodes; i++ )
            Ntk_NetworkDfsFromOutputs_rec( ppNodes[i] );
    }
    else
    {
        for ( i = 0; i < nNodes; i++ )
            Ntk_NetworkDfsFromInputs_rec( ppNodes[i] );
    }
    // finalize the linked list
    Ntk_NetworkStopSpecial( pNet );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Ntk_NetworkDfsFromOutputs_rec( Ntk_Node_t * pNode )
{
    Ntk_Node_t * pFanin;
    Ntk_Pin_t * pLink;

    // if this node is already visited, skip
    if ( Ntk_NodeIsTravIdCurrent( pNode ) )
        return;

    // mark the node as visited
    Ntk_NodeSetTravIdCurrent( pNode );

    // visit the transitive fanin
    if ( pNode->Type != MV_NODE_CI )
        Ntk_NodeForEachFanin( pNode, pLink, pFanin )
            Ntk_NetworkDfsFromOutputs_rec( pFanin );

    // add the node after the fanins have been added
    Ntk_NetworkAddToSpecial( pNode );
}


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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Ntk_NetworkDfsFromInputs_rec( Ntk_Node_t * pNode )
{
    Ntk_Node_t * pFanout;
    Ntk_Pin_t * pLink;

    // if this node is already visited, skip
    if ( Ntk_NodeIsTravIdCurrent( pNode ) )
        return;

    // mark the node as visited
    Ntk_NodeSetTravIdCurrent( pNode );

    // visit the transitive fanout
    if ( pNode->Type != MV_NODE_CO )
        Ntk_NodeForEachFanout( pNode, pLink, pFanout )
            Ntk_NetworkDfsFromInputs_rec( pFanout );

    // add the node after the fanouts have been added
    Ntk_NetworkAddToSpecial( pNode );
}

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

  Synopsis    [Levelizes the network.]

  Description [This procedure connects the nodes into linked lists 
  according to their levels. It returns the number of levels. The nodes
  in the levelized network can be traversed using iterators
  Ntk_NetworkForEachNodeByLevel.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_NetworkLevelize( Ntk_Network_t * pNet, int fFromOutputs )
{
    Ntk_Node_t * pNode;
    // free the previous array of pointers to levels
    if ( pNet->nLevels )
        FREE( pNet->ppLevels );
    // get the new number of levels
    pNet->nLevels = Ntk_NetworkGetNumLevels( pNet );
    // allocate the array of pointers
    pNet->ppLevels = ALLOC( Ntk_Node_t *, pNet->nLevels + 2 );
    memset( pNet->ppLevels, 0, sizeof(Ntk_Node_t *) * (pNet->nLevels + 2) );

    // set the traversal ID for this traversal
    Ntk_NetworkIncrementTravId( pNet );

    // traverse the network and add the nodes to the levelized structure
    if ( fFromOutputs )
    {
        Ntk_NetworkForEachCo( pNet, pNode )
            Ntk_NetworkLevelizeFromOutputs_rec( pNode );
    }
    else
    {
        Ntk_NetworkForEachCi( pNet, pNode )
            Ntk_NetworkLevelizeFromInputs_rec( pNode );
    }

    return pNet->nLevels;
}

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

  Synopsis    [Levelizes the TFI/TFO cone starting from the nodes.]

  Description [This procedure connects the nodes into linked lists 
  according to their levels. It returns the number of levels. The nodes
  in the levelized network can be traversed using iterators
  Ntk_NetworkForEachNodeByLevel.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_NetworkLevelizeNodes( Ntk_Node_t * ppNodes[], int nNodes, int fFromOutputs )
{
    Ntk_Network_t * pNet;
    int i;

    assert( nNodes > 0 );
    pNet = ppNodes[0]->pNet;
    // free the previous array of pointers to levels
    if ( pNet->nLevels )
        FREE( pNet->ppLevels );
    // get the new number of levels
    pNet->nLevels = Ntk_NetworkGetNumLevels( pNet );
    // allocate the array of pointers
    pNet->ppLevels = ALLOC( Ntk_Node_t *, pNet->nLevels + 2 );
    memset( pNet->ppLevels, 0, sizeof(Ntk_Node_t *) * (pNet->nLevels + 2) );

    // set the traversal ID for this traversal
    Ntk_NetworkIncrementTravId( pNet );

    // traverse the network and add the nodes to the levelized structure
    if ( fFromOutputs )
    {
        for ( i = 0; i < nNodes; i++ )
            Ntk_NetworkLevelizeFromOutputs_rec( ppNodes[i] );
    }
    else
    {
        for ( i = 0; i < nNodes; i++ )
            Ntk_NetworkLevelizeFromInputs_rec( ppNodes[i] );
    }

    return pNet->nLevels;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_NetworkLevelizeFromOutputs_rec( Ntk_Node_t * pNode )
{
    int LevelsMax, LevelsCur;
    Ntk_Node_t * pFanin;
    Ntk_Pin_t * pLink;

    // if this node is already visited, skip
    if ( Ntk_NodeIsTravIdCurrent( pNode ) )
        return pNode->Level;

    // mark the node as visited
    Ntk_NodeSetTravIdCurrent( pNode );

    // if this is a PI node, attach it and return 0 levels
    if ( pNode->Type == MV_NODE_CI )
    {  // set the level of this node
        pNode->Level = 0;
    }
    else
    {  // visit the transitive fanin
        LevelsMax = -1;
        Ntk_NodeForEachFanin( pNode, pLink, pFanin )
        {
            LevelsCur = Ntk_NetworkLevelizeFromOutputs_rec( pFanin );
            if ( LevelsMax < LevelsCur )
                LevelsMax = LevelsCur;
        }
        // set the level of this node
        pNode->Level = LevelsMax + 1;
    }

    // attach the node to the level number "pNode->Level"
    pNode->pOrder = pNode->pNet->ppLevels[pNode->Level];
    pNode->pNet->ppLevels[pNode->Level] = pNode;

    return pNode->Level;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_NetworkLevelizeFromInputs_rec( Ntk_Node_t * pNode )
{
    int LevelsMax, LevelsCur;
    Ntk_Node_t * pFanout;
    Ntk_Pin_t * pLink;

    // if this node is already visited, skip
    if ( Ntk_NodeIsTravIdCurrent( pNode ) )
        return pNode->Level;

    // mark the node as visited
    Ntk_NodeSetTravIdCurrent( pNode );

    // if this is a PI node, attach it and return 0 levels
    if ( pNode->Type == MV_NODE_CO )
    {  // set the level of this node
        pNode->Level = 0;
    }
    else
    {  // visit the transitive fanout
        LevelsMax = -1;
        Ntk_NodeForEachFanout( pNode, pLink, pFanout )
        {
            LevelsCur = Ntk_NetworkLevelizeFromInputs_rec( pFanout );
            if ( LevelsMax < LevelsCur )
                LevelsMax = LevelsCur;
        }
        // set the level of this node
        pNode->Level = LevelsMax + 1;
    }

    // attach the node to the level number "pNode->Level"
    pNode->pOrder = pNode->pNet->ppLevels[pNode->Level];
    pNode->pNet->ppLevels[pNode->Level] = pNode;

    return pNode->Level;
}


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

  Synopsis    [Computes the number of logic levels not counting PIs/POs.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_NetworkGetNumLevels( Ntk_Network_t * pNet )
{
    Ntk_Node_t * pNode;
    int LevelsMax, LevelsCur;