wnstrash.c

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

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

  FileName    [wnStrash.c]

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

  Synopsis    [Performs structural hashing on the logic in the window.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

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

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

#include "wnInt.h"

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

static void        Wn_WindowStrashCollect( Sh_Manager_t * pMan, Vm_VarMap_t * pVm, Ntk_Node_t * ppNodes[], int nNodes, Sh_Node_t * ppShInputs[], int nOutputs  );
static void        Wn_WindowStrashNode( Sh_Manager_t * pMan, Ntk_Node_t * pNode, Sh_Node_t * ppShInputs[] );
static Sh_Node_t * Wn_WindowStrashNode_rec( Sh_Manager_t * pMan, Ft_Tree_t * pTree, Ft_Node_t * pFtNode, Sh_Node_t * ppShInputs[] );
static Sh_Node_t * Wn_WindowStrashNodeOr( Sh_Manager_t * pMan, Ft_Tree_t * pTree, Sh_Node_t * ppShInputs[], unsigned Signature, int nNodes );
static void        Wn_WindowStrashNodeDeref( Ntk_Node_t * pNode );
static void        Wn_WindowStrashAddUnique( Sh_Manager_t * pMan, Ntk_Node_t * pNode );

static void        Wn_WindowStrashPrint( Sh_Manager_t * pMan, Wn_Window_t * pWnd );
static void        Wn_WindowStrashPrintOne( Sh_Manager_t * pMan, Ntk_Node_t * pNode );


static void        Wn_WindowStrashCoreConstruct_rec( Sh_Manager_t * pMan, Ntk_Node_t * pNode, Wn_Window_t * pWnd );
static void        Wn_WindowStrashCoreClean( Sh_Manager_t * pMan, Ntk_Node_t * pNode );
static void        Wn_WindowStrashCoreClean_rec( Ntk_Node_t * pNode );
static bool        Wn_WindowStrashCoreNodeIsStrashed( Ntk_Node_t * pNode );
static void        Wn_WindowStrashCoreCleanStrashings( Ntk_Node_t * pNode );

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

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

  Synopsis    [Derives strashed network SS-equivalent to nodes in the window.]

  Description [If the original window has a core, this core is marked.
  If the flag fUseUnique is set, we mark the special nodes and introduce
  unique AND gates at the outputs of these nodes.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Sh_Network_t * Wn_WindowStrash( Sh_Manager_t * pMan, Wn_Window_t * pWnd, bool fUseUnique )
{
    Sh_Network_t * pShNet;
    Sh_Node_t ** ppShInputs;
    Sh_Node_t ** ppShOutputs;
    Sh_Node_t ** ppShNodes;
    Ntk_Node_t * pNode, ** ppNodes;
    int nNodes, nValuesIn;
    int nShInputs, nShOutputs;
    int RetValue, i;

    // to be fixed later
//    ppNodes    = ALLOC( Ntk_Node_t *, 1000 );
//    ppShInputs = ALLOC( Sh_Node_t *,  1000 );
    ppNodes    = pWnd->pNet->pArray1;
    ppShInputs = (Sh_Node_t **)pWnd->pNet->pArray2;

    // create the MV var maps for the window
    Wn_WindowCreateVarMaps( pWnd );

    // start the network
    nShInputs  = Vm_VarMapReadValuesInNum( pWnd->pVmL );
    nShOutputs = Vm_VarMapReadValuesInNum( pWnd->pVmR );
    pShNet     = Sh_NetworkCreate( pMan, nShInputs, nShOutputs );
    Sh_NetworkSetVmL( pShNet, pWnd->pVmL );
    Sh_NetworkSetVmR( pShNet, pWnd->pVmR );
    Sh_NetworkSetVmS( pShNet, pWnd->pVmS );

    // DFS order the nodes in the window
    RetValue = Wn_WindowDfs( pWnd );
    assert( RetValue );

    // mark the special nodes and the root nodes
    if ( fUseUnique )
    {
        Ntk_NetworkForEachNodeSpecial( pWnd->pNet, pNode )
            pNode->pData = (char*)0;
        for ( i = 0; i < pWnd->pWndCore->nRoots; i++ )
            pWnd->pWndCore->ppRoots[i]->pData = (char*)1;
        for ( i = 0; i < pWnd->nSpecials; i++ )
            pWnd->ppRoots[i]->pData = (char*)1;
    }

    // mark the leaves of the window and set their numbers
    Ntk_NetworkIncrementTravId( pWnd->pNet );
    for ( i = 0; i < pWnd->nLeaves; i++ )
    {
        Ntk_NodeSetTravIdCurrent( pWnd->ppLeaves[i] );
        pWnd->ppLeaves[i]->pCopy = (Ntk_Node_t *)i;
    }

    // go through the nodes in the window
    Ntk_NetworkForEachNodeSpecial( pWnd->pNet, pNode )
    {
        // collect fanins into array
        nNodes = Ntk_NodeReadFanins( pNode, ppNodes );
        // set the input Sh_Nodes
        nValuesIn = Vm_VarMapReadValuesInNum( Ntk_NodeReadFuncVm(pNode) );
        Wn_WindowStrashCollect( pMan, pWnd->pVmL, ppNodes, nNodes, ppShInputs, nValuesIn );
        // strash the node
        Wn_WindowStrashNode( pMan, pNode, ppShInputs );

        // add the unique AND-gates
        if ( fUseUnique && pNode->pData )
            Wn_WindowStrashAddUnique( pMan, pNode );
    }

    // collect the pointers to the roots after strashing
    ppShOutputs = Sh_NetworkReadOutputs( pShNet );
    Wn_WindowStrashCollect( pMan, pWnd->pVmL, pWnd->ppRoots, pWnd->nRoots, ppShOutputs, nShOutputs );
    // reference them nodes
    for ( i = 0; i < nShOutputs; i++ )
        Sh_NodeRef( ppShOutputs[i] );

    // if the core is defined, collect the pointers to the leaves/roots after strashing
    if ( pWnd->pWndCore )
    {
        // create the MV var maps for the core window
        Wn_WindowCreateVarMaps( pWnd->pWndCore );
        Sh_NetworkSetVmLC( pShNet, pWnd->pWndCore->pVmL );
        Sh_NetworkSetVmRC( pShNet, pWnd->pWndCore->pVmR );
 
        // collect the core leaves
        nShInputs = Vm_VarMapReadValuesInNum( pWnd->pWndCore->pVmL );
        ppShNodes = Sh_NetworkAllocInputsCore( pShNet, nShInputs );
        Wn_WindowStrashCollect( pMan, pWnd->pVmL, 
            pWnd->pWndCore->ppLeaves, pWnd->pWndCore->nLeaves, ppShNodes, nShInputs );
        for ( i = 0; i < nShInputs; i++ )
            Sh_NodeRef( ppShNodes[i] );

        // collect the core roots
        nShOutputs = Vm_VarMapReadValuesInNum( pWnd->pWndCore->pVmR );
        ppShNodes  = Sh_NetworkAllocOutputsCore( pShNet, nShOutputs );
        Wn_WindowStrashCollect( pMan, pWnd->pVmL, 
            pWnd->pWndCore->ppRoots, pWnd->pWndCore->nRoots, ppShNodes, nShOutputs );
        for ( i = 0; i < nShOutputs; i++ )
            Sh_NodeRef( ppShNodes[i] );
    }

    // if the window has special nodes, collect the pointers after strashing
    if ( pWnd->nSpecials > 0 )
    {
        // collect the special nodes
        nShInputs = Vm_VarMapReadValuesInNum( pWnd->pVmS );
        ppShNodes = Sh_NetworkAllocSpecials( pShNet, nShInputs );
        Wn_WindowStrashCollect( pMan, pWnd->pVmL, 
            pWnd->pWndCore->ppSpecials, pWnd->pWndCore->nSpecials, ppShNodes, nShInputs );
        for ( i = 0; i < nShInputs; i++ )
            Sh_NodeRef( ppShNodes[i] );
    }
//    Wn_WindowStrashPrint( pMan, pWnd );

    // dereference the temporary pointers in the nodes
    Ntk_NetworkForEachNodeSpecial( pWnd->pNet, pNode )
        Wn_WindowStrashNodeDeref( pNode );

//    FREE( ppNodes );
//    FREE( ppShInputs );
    return pShNet;
}

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

  Synopsis    [Derives strashed network SS-equivalent to nodes in the window.]

  Description [If the original window has a core, this core is marked.
  If the flag fUseUnique is set, we mark the special nodes and introduce
  unique AND gates at the outputs of these nodes.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Sh_Network_t * Wn_WindowStrashCore( Sh_Manager_t * pMan, Wn_Window_t * pWnd, Wn_Window_t * pWndC )
{
    Sh_Network_t * pShNet;
    Sh_Node_t ** ppShInputs;
    Sh_Node_t ** ppShOutputs;
    Sh_Node_t ** ppShNodes;
    Ntk_Node_t ** ppNodes;
    int nShInputs, nShOutputs;
//    Ntk_Node_t * pNode;
    int i;

    // to be fixed later
//    ppNodes    = ALLOC( Ntk_Node_t *, 1000 );
//    ppShInputs = ALLOC( Sh_Node_t *,  1000 );
    ppNodes    = pWnd->pNet->pArray1;
    ppShInputs = (Sh_Node_t **)pWnd->pNet->pArray2;

    // create the MV var maps for the window
    Wn_WindowCreateVarMaps( pWndC );

    assert( pWnd->pVmL );
    assert( pWndC->pVmL );

    // start the network
    nShInputs  = Vm_VarMapReadValuesInNum( pWnd->pVmL );
    nShOutputs = Vm_VarMapReadValuesInNum( pWnd->pVmR );
    pShNet     = Sh_NetworkCreate( pMan, nShInputs, nShOutputs );
    Sh_NetworkSetVmL( pShNet, pWnd->pVmL );
    Sh_NetworkSetVmR( pShNet, pWnd->pVmR );
    Sh_NetworkSetVmS( pShNet, pWnd->pVmS );
    Sh_NetworkSetVmLC( pShNet, pWndC->pVmL );
    Sh_NetworkSetVmRC( pShNet, pWndC->pVmR );

    // set the numbers of the leaves
    for ( i = 0; i < pWnd->nLeaves; i++ )
        pWnd->ppLeaves[i]->pCopy = (Ntk_Node_t *)i;

//    i = 0;
//    Ntk_NetworkForEachCi( pWndC->pNet, pNode )
//        pNode->pCopy = (Ntk_Node_t *)i;

//Ntk_NetworkForEachNode( pWnd->pNet, pNode )
//    Wn_WindowStrashCoreCleanStrashings( pNode );

    // clean the TFOs of roots
    for ( i = 0; i < pWndC->nRoots; i++ )
        Wn_WindowStrashCoreClean( pMan, pWndC->ppRoots[i] );

    // increment trav id to prevent clashes with Wn_WindowStrashCollect()
    Ntk_NetworkIncrementTravId( pWnd->pNet );

    // construct the Sh_Node_t pointers for the outputs of the node
    for ( i = 0; i < pWndC->nRoots; i++ )
        Wn_WindowStrashCoreConstruct_rec( pMan, pWndC->ppRoots[i], pWnd );

    // set the unique outputs for these nodes
    for ( i = 0; i < pWndC->nRoots; i++ )
        Wn_WindowStrashAddUnique( pMan, pWndC->ppRoots[i] );

    // construct the Sh_Node_t pointers for the outputs of the network
    for ( i = 0; i < pWnd->nRoots; i++ )
        Wn_WindowStrashCoreConstruct_rec( pMan, pWnd->ppRoots[i], pWnd );

    // collect the pointers to the roots after strashing
    ppShOutputs = Sh_NetworkReadOutputs( pShNet );
    Wn_WindowStrashCollect( pMan, pWnd->pVmL, pWnd->ppRoots, pWnd->nRoots, ppShOutputs, nShOutputs );
 
    // collect the core leaves
    nShInputs = Vm_VarMapReadValuesInNum( pWndC->pVmL );
    ppShNodes = Sh_NetworkAllocInputsCore( pShNet, nShInputs );
    Wn_WindowStrashCollect( pMan, pWnd->pVmL, 
        pWndC->ppLeaves, pWndC->nLeaves, ppShNodes, nShInputs );

    // collect the core roots
    nShOutputs = Vm_VarMapReadValuesInNum( pWndC->pVmR );
    ppShNodes  = Sh_NetworkAllocOutputsCore( pShNet, nShOutputs );
    Wn_WindowStrashCollect( pMan, pWnd->pVmL, 
        pWndC->ppRoots, pWndC->nRoots, ppShNodes, nShOutputs );

    // clean the PFO of the core roots from the temporary Sh_Node_t pointers
    for ( i = 0; i < pWndC->nRoots; i++ )
        Wn_WindowStrashCoreClean( pMan, pWndC->ppRoots[i] );

//    FREE( ppNodes );
//    FREE( ppShInputs );
    return pShNet;
}


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

  Synopsis    [Collects the result of strashing of the nodes.]

  Description [This procedure assumes that strashing for nodes
  in the array (ppNodes, nNodes) has been finished. It collects the
  entries saved in pTree->uRootData or takes the elementary vars
  if the node is a leaf. The result is returned in ppShInputs.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Wn_WindowStrashCollect( Sh_Manager_t * pMan, Vm_VarMap_t * pVm, 
    Ntk_Node_t * ppNodes[], int nNodes, Sh_Node_t * ppShInputs[], int nOutputs )
{
    Sh_Node_t * pShNode;
    Ntk_Node_t * pFanin;
    Ft_Tree_t * pTree;
    Cvr_Cover_t * pCvr;
    int * pValues, * pValuesFirst;
    int iValue, iLeaf, i, k;

    pValues = Vm_VarMapReadValuesArray( pVm );
    pValuesFirst = Vm_VarMapReadValuesFirstArray( pVm );

    // prepare the input data for strashing
    iValue = 0;
    for ( i = 0; i < nNodes; i++ )
    {
        pFanin = ppNodes[i];
//        if ( Ntk_NodeIsTravIdCurrent(pFanin) ) // the node is the leaf
        if ( Ntk_NodeIsCi(pFanin) || Ntk_NodeIsTravIdCurrent(pFanin) ) // the node is the leaf
        {
            // get the leaf number
            iLeaf = (int)pFanin->pCopy;
            assert( pValues[iLeaf] == pFanin->nValues );

            // treat the binary case
            if ( pFanin->nValues == 2 )
            {
                // get the positive literal
                pShNode = Sh_ManagerReadVar( pMan, pValuesFirst[iLeaf] + 1 );
                assert( pShNode );
                ppShInputs[iValue++] = Sh_Not(pShNode);
                ppShInputs[iValue++] = pShNode;        
            }
            else
            {
                // set the corresponding Sh_Nodes into uLeafData
                for ( k = 0; k < pValues[iLeaf]; k++ )
                {
                    pShNode = Sh_ManagerReadVar( pMan, pValuesFirst[iLeaf] + k );
                    assert( pShNode );
                    ppShInputs[iValue++] = pShNode;    
                }
            }
        }
        else // the node has already been processed as part of this window
        {
            pCvr = Ntk_NodeGetFuncCvr( pFanin );
            pTree = Cvr_CoverFactor( pCvr );
            assert( pTree->nRoots == pFanin->nValues );

            for ( k = 0; k < pFanin->nValues; k++ )
            {
                // get the node from the root data
                pShNode = (Sh_Node_t *)pTree->uRootData[k];
                assert( pShNode );
                ppShInputs[iValue++] = pShNode;  
            }
        }
    }
    assert( iValue == nOutputs );
}

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

  Synopsis    [Strashes the node and sets the result in root data.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Wn_WindowStrashNode( Sh_Manager_t * pMan, Ntk_Node_t * pNode, Sh_Node_t * ppShInputs[] )
{
    Ft_Tree_t * pTree;
    Cvr_Cover_t * pCvr;
    Sh_Node_t * pShNode;
    unsigned Signature;
    int i, DefValue;


    // get the factored form of this node
    pCvr = Ntk_NodeGetFuncCvr( pNode );
/*
    DefValue = Cvr_CoverReadDefault(pCvr);
    if ( DefValue >= 0 )
    {
        Mvc_Cover_t ** ppIsets;
        ppIsets = Cvr_CoverReadIsets( pCvr );
        ppIsets[DefValue] = Ntk_NodeComputeDefault(pNode);

        Cvr_CoverFreeFactor(pCvr);
    }
*/

    pTree = Cvr_CoverFactor( pCvr );

/*
    DefValue = Cvr_CoverReadDefault(pCvr);
    if ( DefValue >= 0 )
    {
        Mvc_Cover_t ** ppIsets;
        ppIsets = Cvr_CoverReadIsets( pCvr );
        ppIsets[DefValue] = Ntk_NodeComputeDefault(pNode);

        pTree->pRoots[DefValue] = Ft_Factor( pTree, ppIsets[DefValue] );

//       Mvc_CoverFree( ppIsets[DefValue] );
//        ppIsets[DefValue] = NULL;

    }
*/

    DefValue = -1;
    if ( pNode->fNdTfi ) // means that the node is in the TFO of an ND node
    {
        assert( pNode->fNdTfi == 1 );
        DefValue = Cvr_CoverReadDefault(pCvr);
        if ( DefValue >= 0 )
            pTree->pRoots[DefValue] = Ntk_NodeFactorDefault( pNode );
    }

    for ( i = 0; i < pTree->nRoots; i++ )
        if ( pTree->pRoots[i] )
        {
            pShNode = Wn_WindowStrashNode_rec( pMan, pTree, pTree->pRoots[i], ppShInputs );
            shNodeRef( pShNode );
            pTree->uRootData[i] = (unsigned)pShNode;
        }
        else