ntkdfs.c

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

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

    // perform the traversal
    LevelsMax = -1;
    Ntk_NetworkForEachCo( pNet, pNode )
    {
        LevelsCur = Ntk_NetworkGetNumLevels_rec( Ntk_NodeReadFaninNode(pNode,0) );
        if ( LevelsMax < LevelsCur )
            LevelsMax = LevelsCur;
        pNode->Level = LevelsCur;
    }
    return LevelsMax;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_NetworkGetNumLevels_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, return 0 levels
    if ( pNode->Type == MV_NODE_CI )
    {
        pNode->Level = 0;
        return 0;
    }

    // visit the transitive fanin
    LevelsMax = -1;
    Ntk_NodeForEachFanin( pNode, pLink, pFanin )
    {
        LevelsCur = Ntk_NetworkGetNumLevels_rec( pFanin );
        if ( LevelsMax < LevelsCur )
            LevelsMax = LevelsCur;
    }

    // set the number of levels
    pNode->Level = LevelsMax + 1;
    return pNode->Level;
}

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

  Synopsis    [Detects combinational loops.]

  Description [This procedure is based on the idea suggested by Donald Chai. 
  As we traverse the network and visit the nodes, we need to distinquish 
  three types of nodes: (1) those that are visited for the first time, 
  (2) those that have been visited in this traversal but are currently not 
  on the traversal path, (3) those that have been visited and are currently 
  on the travesal path. When the node of type (3) is encountered, it means 
  that there is a combinational loop. To mark the three types of nodes, 
  two new values of the traversal IDs are used.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
bool Ntk_NetworkIsAcyclic( Ntk_Network_t * pNet )
{
    Ntk_Node_t * pNode;
    int fAcyclic;

    // set the traversal ID for this DFS ordering
    pNet->nTravIds += 2;   
    // pNode->TravId == pNet->nTravIds      means "pNode is on the path"
    // pNode->TravId == pNet->nTravIds - 1  means "pNode is visited but is not on the path"
    // pNode->TravId < pNet->nTravIds - 1   means "pNode is not visited"

    // traverse the network to detect cycles
    fAcyclic = 1;
    Ntk_NetworkForEachCo( pNet, pNode )
    {
        if ( Ntk_NodeReadFanoutNum( pNode ) )
        {
            fprintf( Ntk_NetworkReadMvsisOut(pNet), "Ntk_NetworkIsAcyclic(): Combinational output \"%s\" has fanouts! This should not happen.\n", pNode->pName );
            continue;

        }
        // traverse the output logic cone to detect the combinational loops
        if ( (fAcyclic = Ntk_NetworkIsAcyclic_rec( pNode )) == 0 ) 
        { // stop as soon as the first loop is detected
            fprintf( Ntk_NetworkReadMvsisOut(pNet), " (the output node)\n" );
            break;
        }
    }
    return fAcyclic;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
bool Ntk_NetworkIsAcyclic_rec( Ntk_Node_t * pNode )
{
    Ntk_Network_t * pNet = pNode->pNet;
    Ntk_Node_t * pFanin;
    Ntk_Pin_t * pLink;
    int fAcyclic;

    // make sure the node is not visited
    assert( pNode->TravId != pNet->nTravIds - 1 );
    // check if the node is part of the combinational loop
    if ( pNode->TravId == pNet->nTravIds )
    {
        fprintf( Ntk_NetworkReadMvsisOut(pNet), "Network \"%s\" contains combinational loop!\n", pNet->pName );
        fprintf( Ntk_NetworkReadMvsisOut(pNet), "Node \"%s\" is encountered twice on the following path:\n", Ntk_NodeGetNameLong(pNode) );
        fprintf( Ntk_NetworkReadMvsisOut(pNet), " %s", Ntk_NodeGetNameLong(pNode) );
        return 0;
    }
    // mark this node as a node on the current path
    pNode->TravId = pNet->nTravIds;
    // visit the transitive fanin
    Ntk_NodeForEachFanin( pNode, pLink, pFanin )
    {
        // make sure there is no mixing of networks
        assert( pFanin->pNet == pNode->pNet );

        // check if the fanin is visited
        if ( pFanin->TravId == pNet->nTravIds - 1 ) 
            continue;
        // traverse searching for the loop
        fAcyclic = Ntk_NetworkIsAcyclic_rec( pFanin );
        // return as soon as the loop is detected
        if ( fAcyclic == 0 ) 
        {
            if ( !Ntk_NodeHasCoName(pNode) )
                fprintf( Ntk_NetworkReadMvsisOut(pNet), "  <--  %s", Ntk_NodeGetNameLong(pNode) );
            return 0;
        }
    }
    // mark this node as a visited node
    pNode->TravId = pNet->nTravIds - 1;
    return 1;
}



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

  Synopsis    [Detects combinational loops.]

  Description [This procedure uses the hash table similar to SIS.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
bool Ntk_NetworkIsAcyclic1( Ntk_Network_t * pNet )
{
    st_table * tPath;
    Ntk_Node_t * pNode;
    int fAcyclic;

    tPath = st_init_table( st_ptrcmp, st_ptrhash );
    // set the traversal ID for this DFS ordering
    Ntk_NetworkIncrementTravId( pNet );
    // traverse the network to detect cycles
    Ntk_NetworkForEachCo( pNet, pNode )
    {
        fAcyclic = Ntk_NetworkIsAcyclic1_rec( pNode, tPath );
        if ( fAcyclic == 0 ) // return as soon as the loop is detected
            break;
    }
    st_free_table( tPath );

    return fAcyclic;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
bool Ntk_NetworkIsAcyclic1_rec( Ntk_Node_t * pNode, st_table * tPath )
{
    Ntk_Node_t * pFanin;
    Ntk_Pin_t * pLink;
    int fAcyclic;

    // if this node is already visited, make sure it is not on the path
    if ( Ntk_NodeIsTravIdCurrent( pNode ) )
    {
        if ( st_is_member( tPath, (char*)pNode ) )
            return 0;
        return 1;
    }

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

    // if this is a PI node, return 1 because a PI cannot be in the loop
    if ( pNode->Type == MV_NODE_CI )
        return 1;

    // put the current node on the path
    st_insert( tPath, (char *)pNode, NULL );

    // visit the transitive fanin
    Ntk_NodeForEachFanin( pNode, pLink, pFanin )
    {
        // traverse searching for the loop
        fAcyclic = Ntk_NetworkIsAcyclic1_rec( pFanin, tPath );
        // return as soon as the loop is detected
        if ( fAcyclic == 0 ) 
            return 0;
    }

    // remove the current node from the path
    st_delete( tPath, (char **)&pNode, NULL );

    return 1;
}

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

  Synopsis    [Detects combinational loops.]

  Description [This procedure does not use the hash table (like the one in SIS).
  It uses the array instead. Several hash table lookups per call may be worth 
  iterating through the array if the array is not that large. Even if the number
  of logic level is substantial, this procedure should not be very slow.
  The above conclusion is confirmed experimentally. Even for very "deep" 
  networks (many logic levels) this procedure is not much slower, but for
  some shallow networks it can even be faster than Ntk_NetworkIsAcyclic1().]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
bool Ntk_NetworkIsAcyclic2( Ntk_Network_t * pNet )
{
    Ntk_Node_t ** pPath;
    Ntk_Node_t * pNode;
    int fAcyclic;

    // allocate place where the nodes on the current path are stored
    pPath = ALLOC( Ntk_Node_t *, Ntk_NetworkGetNumLevels(pNet) + 2 );
    // set the traversal ID for this DFS ordering
    Ntk_NetworkIncrementTravId( pNet );

    // traverse the network to detect cycles
    fAcyclic = 1;
    Ntk_NetworkForEachCo( pNet, pNode )
    {
        fAcyclic = Ntk_NetworkIsAcyclic2_rec( pNode, pPath, 0 );
        if ( fAcyclic == 0 ) // return as soon as the loop is detected
            break;
    }
    free( pPath );
    return fAcyclic;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_NetworkIsAcyclic2_rec( Ntk_Node_t * pNode, Ntk_Node_t ** pPath, int Step )
{
    Ntk_Node_t * pFanin;
    Ntk_Pin_t * pLink;
    int i;

    // if this node is already visited, make sure it is not on the path
    if ( Ntk_NodeIsTravIdCurrent( pNode ) )
    {
        for ( i = 0; i < Step; i++ )
            if ( pNode == pPath[i] )
                return 0;
        return 1;
    }

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

    // if this is a PI node, return 1 because a PI cannot be in the loop
    if ( pNode->Type == MV_NODE_CI )
        return 1;

    // put the current node on the path
    pPath[Step] = pNode;

    // visit the transitive fanin
    Ntk_NodeForEachFanin( pNode, pLink, pFanin )
    {
        // return as soon as the loop is detected
        if ( !Ntk_NetworkIsAcyclic2_rec( pFanin, pPath, Step + 1 ) ) 
            return 0;
    }

    // remove the current node from the path
    pPath[Step] = pNode;
    return 1;
}


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

  Synopsis    [Computes the combinational support of the given nodes.]

  Description [Computes the combinational support by the DFS searh
  from the given nodes. The nodes are linked into the list pNet->pOrder,
  which can be traversed Ntk_NetworkForEachNodeSpecial. The return values 
  in the number of CI nodes in the combinational support.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_NetworkComputeNodeSupport( 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_NetworkComputeNodeSupport_rec( pNodes[i] );
    // finalize the linked list
    Ntk_NetworkStopSpecial( pNet );

    return nNodesRes;
}

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

  Synopsis    []

  Description []
               
  SideEffects []