ntkieliminate.c

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

    Ntk_NodeHeapStop( pHeap );
}


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

  Synopsis    [Work on the node after collapsing.]

  Description [Recalculates the collapsed nodes after the change.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Ntk_EliminateUpdate( Ntk_Network_t * pNet, Ntk_NodeHeap_t * pHeap, Ntk_Node_t ** ppFanouts, int nFanouts, bool fUseCostBdd )
{
    Ntk_Node_t * pNode, * pFanin, * pFanout;
    Ntk_Pin_t * pPin;
    int Weight,WeightOld;
    int i;

    // recalculate the cost of collapsing the affected nodes
    for ( i = 0; i < nFanouts; i++ )
    {
        // get the node
        pNode = ppFanouts[i];
        // try collapsing the fanins into this node
        Ntk_NodeForEachFanin( pNode, pPin, pFanin )
            if ( fUseCostBdd )
                Ntk_EliminateSetCollapsingWeightBdd( pNode, pPin, pFanin );
            else
                Ntk_EliminateSetCollapsingWeightSop( pNode, pPin, pFanin );
        // try collapsing this node into its fanout
        Ntk_NodeForEachFanout( pNode, pPin, pFanout )
            if ( fUseCostBdd )
                Ntk_EliminateSetCollapsingWeightBdd( pFanout, pPin->pLink, pNode );
            else
                Ntk_EliminateSetCollapsingWeightSop( pFanout, pPin->pLink, pNode );
    }

    // update the queque
    for ( i = 0; i < nFanouts; i++ )
    {
        // get the node
        pNode = ppFanouts[i];
        if ( Ntk_NodeIsCo(pNode) )
            continue;
        // update the node
        if ( !Ntk_NodeIsCoDriver(pNode) )
        {
            WeightOld = NTK_ELIMINATE_READ_WEIGHT( pNode );
            if ( fUseCostBdd )
                Weight = Ntk_EliminateGetNodeWeightBdd( pNode );
            else
                Weight = Ntk_EliminateGetNodeWeightSop( pNode );
            NTK_ELIMINATE_SET_WEIGHT( pNode, Weight );
            // update the node if it is in the heap
            if ( pNode->pData )
                Ntk_NodeHeapUpdate( pHeap, pNode );
        }
        // update the fanins
        Ntk_NodeForEachFanin( pNode, pPin, pFanin )
        {
            if ( pFanin->Type == MV_NODE_CI )
                continue;

            WeightOld = NTK_ELIMINATE_READ_WEIGHT( pFanin );
            if ( fUseCostBdd )
                Weight = Ntk_EliminateGetNodeWeightBdd( pFanin );
            else
                Weight = Ntk_EliminateGetNodeWeightSop( pFanin );
            NTK_ELIMINATE_SET_WEIGHT( pFanin, Weight );
            // update the node if it is in the heap
            if ( pFanin->pData )
                Ntk_NodeHeapUpdate( pHeap, pFanin );
        }
    }
}

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

  Synopsis    [Computes the weight of the current node.]

  Description [The weight is measured in terms of how many BDD
  nodes can be saved if the node is collapsed into its fanouts.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_EliminateGetNodeWeightBdd( Ntk_Node_t * pNode )
{
    Ntk_Node_t * pFanout;
    Ntk_Pin_t * pPin;
    int CostBefore, CostAfter;

    if ( Ntk_NodeIsCo(pNode) )
        return 0;

    // get the cost before elimination of this node
    CostBefore = Mvr_RelationGetNodes( Ntk_NodeGetFuncMvr(pNode) );
    Ntk_NodeForEachFanout( pNode, pPin, pFanout )
        if ( pFanout->Type != MV_NODE_CO )
            CostBefore += Mvr_RelationGetNodes( Ntk_NodeGetFuncMvr(pFanout) );

    // get the cost after elimination of this node
    // if the node fans out into a CO, it cannot be eliminated
    if ( Ntk_NodeIsCoFanin(pNode) )
        CostAfter = Mvr_RelationGetNodes( Ntk_NodeGetFuncMvr(pNode) );
    else
        CostAfter = 0;
    Ntk_NodeForEachFanout( pNode, pPin, pFanout )
        if ( pFanout->Type != MV_NODE_CO )
            CostAfter += (int)pPin->pLink->pData;
    return CostBefore - CostAfter;
}

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

  Synopsis    [Computes the cost of two nodes after collapsing.]

  Description [Assigns the cost to the fanin pin of the node.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_EliminateSetCollapsingWeightBdd( Ntk_Node_t * pNode, Ntk_Pin_t * pPin, Ntk_Node_t * pFanin )
{
    Ntk_Node_t * pCollapsed;
    int nNodes;
    assert( Ntk_NodeReadFaninIndex( pNode, pFanin ) != -1 );
    pCollapsed = Ntk_NodeCollapse( pNode, pFanin );
    if ( pCollapsed )
    {   // reorder the relation
//        Ntk_NodeReorderMvr( pCollapsed );
        // get the number of nodes after collapsing
        nNodes = Mvr_RelationGetNodes( Ntk_NodeGetFuncMvr(pCollapsed) );
        // set the cost of these nodes after collapsing
        pPin->pData = (char *)nNodes;
        Ntk_NodeDelete( pCollapsed );
        return nNodes;
    }
    else
    {
        pPin->pData = NULL;
        return 1000000;
    }
}


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

  Synopsis    [Computes the weight of the current node.]

  Description [The weight is the inverse of the classical
  elimination value of the node.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_EliminateGetNodeWeightSop( Ntk_Node_t * pNode )
{
    Ntk_Node_t * pFanout;
    Ntk_Pin_t * pPin;
    Cvr_Cover_t * pCvrNode;
    Ft_Tree_t * pTreeNode;
    int CostBefore, CostAfter;

    if ( Ntk_NodeIsCo(pNode) )
        return 0;

    // get the node's factored form
    pCvrNode = Ntk_NodeGetFuncCvr( pNode );
    // get the factored tree
    pTreeNode = Cvr_CoverFactor( pCvrNode );

    // get the cost before elimination of this node
    CostBefore = pTreeNode->nNodes;

    // get the cost after elimination of this node
    // if the node fans out into a CO, it cannot be eliminated
    if ( Ntk_NodeIsCoFanin(pNode) )
        CostAfter = pTreeNode->nNodes;
    else
        CostAfter = 0;
    Ntk_NodeForEachFanout( pNode, pPin, pFanout )
        if ( pFanout->Type != MV_NODE_CO )
            CostAfter += (int)pPin->pLink->pData;

//    assert( CostBefore - CostAfter <= 1 );
    return CostBefore - CostAfter;
}

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

  Synopsis    [Computes the cost of two nodes after collapsing.]

  Description [Assigns the cost to the fanin pin of the node.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_EliminateSetCollapsingWeightSop( Ntk_Node_t * pNode, Ntk_Pin_t * pPin, Ntk_Node_t * pFanin )
{
    Vm_VarMap_t * pVm;
    Cvr_Cover_t * pCvrNode;
    Cvr_Cover_t * pCvrFanin;
    Ft_Tree_t * pTreeNode;
    Ft_Tree_t * pTreeFanin;
    int iFanin, nValues, iValueFirst;
    int nFanoutLitOccurs, nFaninLits, Cost, i;

    iFanin = Ntk_NodeReadFaninIndex( pNode, pFanin );
    assert( iFanin != -1 );
    if ( pNode->Type != MV_NODE_INT || pFanin->Type != MV_NODE_INT )
    {
        pPin->pData = NULL;
        return 1000000;
    }

    // get the fanin's factored form
    pCvrFanin = Ntk_NodeGetFuncCvr( pFanin );
    // get the factored tree
    pTreeFanin = Cvr_CoverFactor( pCvrFanin );

    // get the node's factored form
    pCvrNode = Ntk_NodeGetFuncCvr( pNode );
    // get the factored tree
    pTreeNode = Cvr_CoverFactor( pCvrNode );
    // count the number of terminal literals in the FF
    if ( pTreeNode->fMark == 0 )
    {
        Ft_TreeCountLeafRefs( pTreeNode );
        pTreeNode->fMark = 1;
    }
 
    // count how many times the literals corresponding 
    // to pFanin occur in pNode's factored form
    pVm = Ntk_NodeReadFuncVm( pNode );
    nValues = Vm_VarMapReadValues( pVm, iFanin );
    iValueFirst = Vm_VarMapReadValuesFirst( pVm, iFanin );

    // get the cost of collapsing
    if ( nValues == 2 )
    {
        nFanoutLitOccurs = pTreeNode->uLeafData[iValueFirst] +
                           pTreeNode->uLeafData[iValueFirst + 1];
        nFaninLits = pTreeFanin->nNodes;
        Cost = nFanoutLitOccurs * (nFaninLits - 1);
    }
    else
    {
        Cost = 0;
        for ( i = iValueFirst; i < iValueFirst + nValues; i++ )
            if ( pTreeFanin->pRoots[i-iValueFirst] )
            {
                nFanoutLitOccurs = pTreeNode->uLeafData[i];
                nFaninLits = Ft_FactorCountLeavesOne(pTreeFanin->pRoots[i-iValueFirst]);
                Cost += nFanoutLitOccurs * (nFaninLits - 1);
            }
    }

    // set the cost
    pPin->pData = (char *)Cost;
    return Cost;
}

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

  Synopsis    [Computes the cost of two nodes after collapsing.]

  Description [Assigns the cost to the fanin pin of the node.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_NetworkGetNodeValueSop( Ntk_Node_t * pNode )
{
    Ntk_Node_t * pFanout;
    Ntk_Pin_t * pPin;
    int Value;
    // precompute the elimination value for collapsing
    Ntk_NodeForEachFanout( pNode, pPin, pFanout )
        Ntk_EliminateSetCollapsingWeightSop( pFanout, pPin->pLink, pNode );
    // get the elimination value for the node
    Value = - Ntk_EliminateGetNodeWeightSop( pNode );
    return Value;
}

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