wnutils.c

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

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

  FileName    [wnUtils.c]

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

  Synopsis    [Various windowing utilities.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

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

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

#include "wnInt.h"

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

static int Wn_WindowDfs_rec( Ntk_Node_t * pNode );
static int Wn_WindowGetNumLevels_rec( Ntk_Node_t * pNode );
static int Wn_WindowLevelizeFromInputs_rec( Ntk_Node_t * pNode );
static int Wn_WindowLevelizeFromOutputs_rec( Ntk_Node_t * pNode );

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

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

  Synopsis    [Returns 1 if the window has at least one ND node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
bool Wn_WindowIsND( Wn_Window_t * pWnd )
{
    Mvr_Relation_t * pMvr;
    Ntk_Node_t * pNode;

    // if the window is composed of binary nodes, no need to look for special
    // IF THERE ARE NO INCOMPLETELY SPECIFIED NODES!!!

    // collect the nodes into the special list
    Wn_WindowDfs( pWnd );
    // assume that there is no need to collect the special nodes
    Ntk_NetworkForEachNodeSpecial( pWnd->pNet, pNode )
    {
        if ( pNode->nValues == 2 ) // ???
            continue;
        if ( pNode->Type != MV_NODE_INT )
            continue;
        pMvr = Ntk_NodeGetFuncMvr( pNode );
        if ( Mvr_RelationIsND( pMvr ) ) 
            return 1;
    }
    return 0;
}

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

  Synopsis    [Returns the extended variable map for the window.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Wn_WindowCreateVarMaps( Wn_Window_t * pWnd )
{
    Vm_Manager_t * pManVm;
    int * pValues;
    int nNodesMax;
    int i;

    // get the pointer to the Vm manager
    pManVm = Fnc_ManagerReadManVm(pWnd->pNet->pMan);

    // get the max number of leaves/roots/specials
    nNodesMax = -1;
    if ( nNodesMax < pWnd->nLeaves )
        nNodesMax = pWnd->nLeaves;
    if ( nNodesMax < pWnd->nRoots )
        nNodesMax = pWnd->nRoots;
    if ( nNodesMax < pWnd->nSpecials )
        nNodesMax = pWnd->nSpecials;
    // allocate temporary storage for var values
    pValues = ALLOC( int, nNodesMax );

    // create the map for the leaves
    for ( i = 0; i < pWnd->nLeaves; i++ )
        pValues[i] = pWnd->ppLeaves[i]->nValues;
    pWnd->pVmL = Vm_VarMapLookup( pManVm, pWnd->nLeaves, 0, pValues );  

    // create the map for the roots
    for ( i = 0; i < pWnd->nRoots; i++ )
        pValues[i] = pWnd->ppRoots[i]->nValues;
    pWnd->pVmR = Vm_VarMapLookup( pManVm, pWnd->nRoots, 0, pValues );  

    // create the map for the specials
    for ( i = 0; i < pWnd->nSpecials; i++ )
        pValues[i] = pWnd->ppSpecials[i]->nValues;
    pWnd->pVmS = Vm_VarMapLookup( pManVm, pWnd->nSpecials, 0, pValues );  

    FREE( pValues );
}

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

  Synopsis    [DFS-order the nodes in the window.]

  Description [Roots are included, leaves are not included. Returns 0
  if the window is not specified correctly, that is, if there is a path
  from the roots to the CIs bypassing leaves.]
               
  SideEffects [Sets the trav IDs of the window nodes to the current one.]

  SeeAlso     []

***********************************************************************/
int Wn_WindowDfs( Wn_Window_t * pWnd )
{
    int RetValue, i;

    // mark the leaves - this way they will not be collected
    Ntk_NetworkIncrementTravId( pWnd->pNet );
    for ( i = 0; i < pWnd->nLeaves; i++ )
        Ntk_NodeSetTravIdCurrent( pWnd->ppLeaves[i] );

    // start the DFS and collect the nodes
    Ntk_NetworkStartSpecial( pWnd->pNet );
    RetValue = 1;
    for ( i = 0; i < pWnd->nRoots; i++ )
        if ( !Wn_WindowDfs_rec( pWnd->ppRoots[i] ) )
        {
            RetValue = 0;
            break; // detected window inconsistency  
        }
    Ntk_NetworkStopSpecial( pWnd->pNet );
    return RetValue;
}

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

  Synopsis    [Performs the recursive step of ordering the leaves.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Wn_WindowDfs_rec( Ntk_Node_t * pNode )
{
    Ntk_Node_t * pFanin;
    Ntk_Pin_t * pPin;

    if ( Ntk_NodeIsTravIdCurrent(pNode) ) // visited node
        return 1;
    // if the node is a CI, it is an inconsistency
    if ( Ntk_NodeIsCi(pNode) )
        return 0;

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

    // otherwise, call recursively
    Ntk_NodeForEachFanin( pNode, pPin, pFanin )
        if ( !Wn_WindowDfs_rec(pFanin) )
            return 0;

    // collect this node
    Ntk_NetworkAddToSpecial( pNode );
    return 1;
}


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

  Synopsis    [Collects the internal nodes of the window.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Wn_WindowCollectInternal( Wn_Window_t * pWnd )
{
    Ntk_Node_t * pNode;
    int RetValue, i;

    // DFS order the nodes in the window
    RetValue = Wn_WindowDfs( pWnd );
    assert( RetValue );
    FREE( pWnd->ppNodes );
    // get the number of internal nodes
    pWnd->nNodes = Ntk_NetworkCountSpecial( pWnd->pNet );
    pWnd->ppNodes = ALLOC( Ntk_Node_t *, pWnd->nNodes );
    // go through the nodes and collect them
    i = 0;
    Ntk_NetworkForEachNodeSpecial( pWnd->pNet, pNode )
    {
        assert( Ntk_NodeIsInternal(pNode) );
        pWnd->ppNodes[i++] = pNode;
    }
    assert( i == pWnd->nNodes );
}


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

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Wn_WindowGetNumLevels( Wn_Window_t * pWnd )
{
    Ntk_Node_t * pNode;
    int LevelsMax, LevelsCur;
    int i;

    // set the traversal ID for this traversal
    Ntk_NetworkIncrementTravId( pWnd->pNet );
    // mark the leaves - this way we will stop at them
    for ( i = 0; i < pWnd->nLeaves; i++ )
    {
        pNode = pWnd->ppLeaves[i];
        Ntk_NodeSetTravIdCurrent( pNode );
        pNode->Level = 0;
    }

    // perform the traversal
    LevelsMax = -1;
    for ( i = 0; i < pWnd->nRoots; i++ )
    {
        pNode = pWnd->ppRoots[i];
        LevelsCur = Wn_WindowGetNumLevels_rec( pNode );
        if ( LevelsMax < LevelsCur )
            LevelsMax = LevelsCur;
        pNode->Level = LevelsCur;
    }
    return LevelsMax;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

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

    if ( Ntk_NodeIsTravIdCurrent(pNode) ) // visited node
        return pNode->Level;
    assert( !Ntk_NodeIsCi(pNode) ); // otherwise, the window is wrong

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

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

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



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

  Synopsis    [Levelizes the TFI/TFO cone startign 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
  Wn_WindowForEachNodeByLevel.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Wn_WindowLevelizeNodes( Wn_Window_t * pWnd, int fFromRoots )
{
    Ntk_Network_t * pNet;
    Ntk_Node_t * pFanout;
    Ntk_Pin_t * pPin;
    int i;

    // free the previous array of pointers to levels
    pNet = pWnd->pNet;
    if ( pNet->nLevels )
        FREE( pNet->ppLevels );
    // get the new number of levels
    pNet->nLevels = Wn_WindowGetNumLevels( pWnd );
    // 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) );

    // traverse the network and add the nodes to the levelized structure
    if ( fFromRoots )
    {
        // set the traversal ID for this traversal
        Ntk_NetworkIncrementTravId( pWnd->pNet );
        // mark the leaves - this way we will stop at them
        for ( i = 0; i < pWnd->nLeaves; i++ )
        {
            Ntk_NodeSetTravIdCurrent( pWnd->ppLeaves[i] );
            pWnd->ppLeaves[i]->Level = 0;
        }
        // visit all the nodes starting from the roots
        for ( i = 0; i < pWnd->nRoots; i++ )
            Wn_WindowLevelizeFromOutputs_rec( pWnd->ppRoots[i] );
    }
    else
    {
        // mark all the windows nodes
        Wn_WindowDfs( pWnd );
        // set the traversal ID for this traversal
        Ntk_NetworkIncrementTravId( pWnd->pNet );
        // mark the roots - this way we will stop at them
        for ( i = 0; i < pWnd->nRoots; i++ )
        {
            Ntk_NodeSetTravIdCurrent( pWnd->ppRoots[i] );
            pWnd->ppRoots[i]->Level = 0;
        }

        // start DFS from the fanouts of the leaves
        // visit only the nodes that are in the window
        // they have the previous trav ID set by Wn_WindowDfs()
        for ( i = 0; i < pWnd->nLeaves; i++ )
            Ntk_NodeForEachFanout( pWnd->ppLeaves[i], pPin, pFanout )
                Wn_WindowLevelizeFromInputs_rec( pFanout );
    }

    return pNet->nLevels;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

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

    if ( Ntk_NodeIsTravIdCurrent(pNode) ) // visited node
        return pNode->Level;
    assert( !Ntk_NodeIsCi(pNode) ); // otherwise, the window is wrong

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

    // visit the transitive fanin
    LevelsMax = -1;
    Ntk_NodeForEachFanin( pNode, pLink, pFanin )
    {
        LevelsCur = Wn_WindowLevelizeFromOutputs_rec( pFanin );
        if ( LevelsMax < LevelsCur )
            LevelsMax = LevelsCur;
    }
    assert( LevelsMax >= 0 );
    // 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 Wn_WindowLevelizeFromInputs_rec( Ntk_Node_t * pNode )
{
    int LevelsMax, LevelsCur;
    Ntk_Node_t * pFanout;
    Ntk_Pin_t * pLink;

    if ( Ntk_NodeIsTravIdCurrent(pNode) ) // visited node
        return pNode->Level;
    if ( !Ntk_NodeIsTravIdPrevious(pNode) ) // the node is not in the window
        return -1;
    assert( !Ntk_NodeIsCo(pNode) ); // otherwise, the window is wrong

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

    // visit the transitive fanout
    LevelsMax = -1;
    Ntk_NodeForEachFanout( pNode, pLink, pFanout )
    {
        LevelsCur = Wn_WindowLevelizeFromInputs_rec( pFanout );
        if ( LevelsMax < LevelsCur )
            LevelsMax = LevelsCur;
    }
    assert( LevelsMax >= 0 );
    // 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;
}

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