ntkdfs.c

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

  SeeAlso     []

***********************************************************************/
int Ntk_NetworkComputeNodeSupport_rec( Ntk_Node_t * pNode )
{
    Ntk_Node_t * pFanin;
    Ntk_Pin_t * pLink;
    int nNodes;

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

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

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

    // add the node to the list only if it a combinational input
    if ( pNode->Type == MV_NODE_CI )
    {
        Ntk_NetworkAddToSpecial( pNode );
        // increment the number of nodes in the list
        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 Ntk_NetworkInterleaveNodes( Ntk_Network_t * pNet, Ntk_Node_t * pNodes[], int nNodes )
{
    int nNodesRes, i;
    // set the traversal ID for this DFS ordering
    Ntk_NetworkIncrementTravId( pNet );
    // start the linked list
    Ntk_NetworkStartSpecial( pNet );
    // traverse the TFI cones of all nodes in the array
    nNodesRes = 0;
    for ( i = 0; i < nNodes; i++ )
        nNodesRes += Ntk_NetworkInterleaveNodes_rec( pNodes[i] );
    // finalize the linked list
    Ntk_NetworkStopSpecial( pNet );
//    Ntk_NetworkPrintSpecial( pNet );
    return nNodesRes;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_NetworkInterleaveNodes_rec( Ntk_Node_t * pNode )
{
    Ntk_Node_t * pFanin;
    Ntk_Pin_t * pLink;
    int nNodes;

    // if this node is already visited, skip
    if ( Ntk_NodeIsTravIdCurrent(pNode) )
    {
        // move the insertion point to be after this node
        Ntk_NetworkMoveSpecial( pNode );
        return 0;
    }
    // mark the node as visited
    Ntk_NodeSetTravIdCurrent( pNode );

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

    // add the node to the list 
    Ntk_NetworkAddToSpecial( pNode );
    nNodes++;
    return nNodes;
}


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

  Synopsis    [Computes the transitive fanin nodes of the given node.]

  Description [Computes the transitive fanin nodes by the DFS search
  from the given nodes. The return value in the number of nodes in the 
  TFI cones. The depth 0 returns only the nodes in the array. The depth 1 
  returns the first logic level of fanins of the given nodes, and so on. 
  The nodes are linked into the internal list, which can be traversed by 
  Ntk_NetworkForEachNodeSpecial. The CI nodes are included if the flag 
  fIncludeCis is set to 1. If the flag fExistPath is 1, the set of all nodes 
  is computed such that there is exist a path of the given length (Depth) 
  or shorter, If this flag is 0, the set of all node is computes such that 
  any path to them is the given length (Depth) or shorter. Note that
  if fExistPath is 0 the complexity of this procedure is higher. Therefore
  in those applications where it makes no difference, fExistPath = 1 is 
  preferable.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_NetworkComputeNodeTfi( Ntk_Network_t * pNet, Ntk_Node_t * pNodes[], int nNodes, int Depth, bool fIncludeCis, bool fExistPath )
{
    Ntk_Node_t * pNode, * pNode2;
    int nNodesRes, DepthReal, i;
    bool fFirst;
    // set the traversal ID
    Ntk_NetworkIncrementTravId( pNet );
    // start the linked list
    Ntk_NetworkStartSpecial( pNet );
    // start DFS from the primary outputs
    DepthReal = Depth + (!fExistPath) * 1000;
    nNodesRes = 0;
    for ( i = 0; i < nNodes; i++ )
        nNodesRes += Ntk_NetworkComputeNodeTfi_rec( pNodes[i], DepthReal, fIncludeCis, fExistPath );
    // finalize the linked list
    Ntk_NetworkStopSpecial( pNet );

    // remove from the list those nodes have the large real number of levels
    if ( !fExistPath )
    {
        fFirst = 1;
        nNodesRes = 0;
        Ntk_NetworkForEachNodeSpecialSafe( pNet, pNode, pNode2 )
        {
            if ( fFirst )
            { // restart the specialized list
                Ntk_NetworkStartSpecial( pNet );
                fFirst = 0;
            }
            if ( pNode->Level >= 1000 )
            { // if the node satisfies the criteria, add it to the specialized list
                Ntk_NetworkAddToSpecial( pNode );
                pNode->Level -= 1000;
                nNodesRes++;
            }
        }
        // finalize the linked list
        Ntk_NetworkStopSpecial( pNet );
    }
    return nNodesRes;
}

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

  Synopsis    [Performs the recursive step of Ntk_NetworkComputeNodeTfi().]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_NetworkComputeNodeTfi_rec( Ntk_Node_t * pNode, int Depth, bool fIncludeCis, bool fExistPath )
{
    Ntk_Node_t * pFanin;
    Ntk_Pin_t * pLink;
    int nNodes;

    // if the depth is out, skip
    if ( Depth == -1 )
        return 0;

    // if this node is already visited, check the level
    if ( Ntk_NodeIsTravIdCurrent( pNode ) )
    {
        nNodes = 0;
        if ( fExistPath && pNode->Level < Depth || (!fExistPath) && pNode->Level > Depth )
        {
            // update the path to be shortest possible
            pNode->Level = Depth;
            // visit the transitive fanin
            if ( pNode->Type != MV_NODE_CI )
                Ntk_NodeForEachFanin( pNode, pLink, pFanin )
                    nNodes += Ntk_NetworkComputeNodeTfi_rec( pFanin, Depth - 1, fIncludeCis, fExistPath );
        }
        return nNodes;
    }

    // mark the node as visited
    Ntk_NodeSetTravIdCurrent( pNode );
    // set the depth
    pNode->Level = Depth;

    // visit the transitive fanin
    nNodes = 0;
    if ( pNode->Type != MV_NODE_CI )
        Ntk_NodeForEachFanin( pNode, pLink, pFanin )
            nNodes += Ntk_NetworkComputeNodeTfi_rec( pFanin, Depth - 1, fIncludeCis, fExistPath );

    // add the node after the fanins are added
    if ( pNode->Type != MV_NODE_CI || fIncludeCis )
    {
        Ntk_NetworkAddToSpecial( pNode );
        nNodes++;
    }
    return nNodes;
}


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

  Synopsis    [Computes the transitive fanout nodes of the given node.]

  Description [Computes the transitive fanout nodes by the DFS search
  from the given nodes. The return value in the number of nodes in the 
  TFI cones. The depth 0 returns only the nodes in the array. The depth 1 
  returns the first logic level of fanouts of the given nodes, and so on. 
  The nodes are linked into the internal list, which can be traversed by 
  Ntk_NetworkForEachNodeSpecial. The CO nodes are included if the flag 
  fIncludeCos is set to 1. If the flag fExistPath is 1, the set of all nodes 
  is computed such that there is exist a path of the given length (Depth) 
  or shorter, If this flag is 0, the set of all node is computes such that 
  any path to them is the given length (Depth) or shorter. Note that
  if fExistPath is 0 the complexity of this procedure is higher. Therefore
  in those applications where it makes no difference, fExistPath = 1 is 
  preferable.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_NetworkComputeNodeTfo( Ntk_Network_t * pNet, Ntk_Node_t * pNodes[], int nNodes, int Depth, bool fIncludeCos, bool fExistPath )
{
    Ntk_Node_t * pNode, * pNode2;
    int nNodesRes, DepthReal, i;
    bool fFirst;
    // set the traversal ID
    Ntk_NetworkIncrementTravId( pNet );
    // start the linked list
    Ntk_NetworkStartSpecial( pNet );
    // start DFS from the primary outputs
    DepthReal = Depth + (!fExistPath) * 1000;
    nNodesRes = 0;
    for ( i = 0; i < nNodes; i++ )
        nNodesRes += Ntk_NetworkComputeNodeTfo_rec( pNodes[i], DepthReal, fIncludeCos, fExistPath );
    // finalize the linked list
    Ntk_NetworkStopSpecial( pNet );

    // remove from the list those nodes have the large real number of levels
    if ( !fExistPath )
    {
        fFirst = 1;
        nNodesRes = 0;
        Ntk_NetworkForEachNodeSpecialSafe( pNet, pNode, pNode2 )
        {
            if ( fFirst )
            { // restart the specialized list
                Ntk_NetworkStartSpecial( pNet );
                fFirst = 0;
            }
            if ( pNode->Level >= 1000 )
            { // if the node satisfies the criteria, add it to the specialized list
                Ntk_NetworkAddToSpecial( pNode );
                pNode->Level -= 1000;
                nNodesRes++;
            }
        }
        // finalize the linked list
        Ntk_NetworkStopSpecial( pNet );
    }
    return nNodesRes;
}

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

  Synopsis    [Performs the recursive step of Ntk_NetworkComputeNodeTfo().]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_NetworkComputeNodeTfo_rec( Ntk_Node_t * pNode, int Depth, bool fIncludeCos, bool fExistPath )
{
    Ntk_Node_t * pFanout;
    Ntk_Pin_t * pLink;
    int nNodes;

    // if the depth is out, skip
    if ( Depth == -1 )
        return 0;

    // if this node is already visited, check the level
    if ( Ntk_NodeIsTravIdCurrent( pNode ) )
    {
        nNodes = 0;
        if ( fExistPath && pNode->Level < Depth || (!fExistPath) && pNode->Level > Depth )
        {
            // update the path to be shortest possible
            pNode->Level = Depth;
            // visit the transitive fanin
            if ( pNode->Type != MV_NODE_CO )
                Ntk_NodeForEachFanout( pNode, pLink, pFanout )
                    nNodes += Ntk_NetworkComputeNodeTfo_rec( pFanout, Depth - 1, fIncludeCos, fExistPath );
        }
        return nNodes;
    }

    // mark the node as visited
    Ntk_NodeSetTravIdCurrent( pNode );
    // set the depth
    pNode->Level = Depth;

    // visit the transitive fanin
    nNodes = 0;
    if ( pNode->Type != MV_NODE_CO )
        Ntk_NodeForEachFanout( pNode, pLink, pFanout )
            nNodes += Ntk_NetworkComputeNodeTfo_rec( pFanout, Depth - 1, fIncludeCos, fExistPath );

    // add the node after the fanouts are added
    if ( pNode->Type != MV_NODE_CO || fIncludeCos )
    {
        Ntk_NetworkAddToSpecial( pNode );
        nNodes++;
    }
    return nNodes;
}

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

  Synopsis    [Returns 1 if the node has a CO in its TFO logic cone.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
bool Ntk_NodeHasCoInTfo( Ntk_Node_t * pNode )
{
    Ntk_Node_t * pFanout;
    Ntk_Pin_t * pPin;

    Ntk_NodeForEachFanout( pNode, pPin, pFanout )
    {
        if ( Ntk_NodeIsCo( pFanout ) )
            return 1;
        if ( Ntk_NodeHasCoInTfo( pFanout ) )
            return 1;
    }
    return 0;
}

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