ntknodecol.c

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

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

  FileName    [ntkCollapse.c]

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

  Synopsis    [Procedures to perform collapsing of two nodes.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: ntkNodeCol.c,v 1.23 2003/05/28 03:16:55 alanmi Exp $]

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

#include "ntkInt.h"

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

static Ntk_Node_t * Ntk_NodeCollapseSpecialCase( Ntk_Node_t * pNode, Ntk_Node_t * pFanin );
static Ntk_Node_t * Ntk_NodeCombineFanins( Ntk_Node_t * pNode, Ntk_Node_t * pFanin, 
     int * pTransMapNInv, int * pTransMapF );


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

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

  Synopsis    [Collapses the fanin into the node.]

  Description [Derives the node, which is the result of substitution of 
  pFanin into pNode. Makes this node minimum base and sorts the nodes
  fanins to be in the accepted fanin order. Replaces pNode by the new
  node in the network. Leaves pFanin unchanged and does not remove it
  from the network, even if its only fanout was pNode.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
bool Ntk_NetworkCollapseNodes( Ntk_Node_t * pNode, Ntk_Node_t * pFanin )
{
    Ntk_Node_t * pNodeNew;
    // derive the collapsed node 
    // this node is not minimum-base and is not in the network
    pNodeNew = Ntk_NodeCollapse( pNode, pFanin );
    if ( pNodeNew == NULL )
        return 0;
    // make the node minimum-base
    Ntk_NodeMakeMinimumBase( pNodeNew );
    // replace the old node with the new one
    Ntk_NodeReplace( pNode, pNodeNew ); // disposes of pNodeNew
    return 1;
}


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

  Synopsis    [Derives the collapsed node.]

  Description [Derives the collapsed node without making it minimum base
  and without adding it to the network. This node contains the relation 
  after collapsing, which can be used to approximate the complexity of 
  the collapsed node, for example, during eliminate.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Ntk_Node_t * Ntk_NodeCollapse( Ntk_Node_t * pNode, Ntk_Node_t * pFanin )
{
    Ntk_Node_t * pNodeNew;
    Vm_VarMap_t * pVm, * pVmNew;
    Mvr_Relation_t * pMvrN, * pMvrF, * pMvrNew;
    Cvr_Cover_t * pCvrN, * pCvrF, * pCvrNew;
    int * pTransMapNInv, * pTransMapF;

    // check conditions when collapsing makes no sense
    if ( Ntk_NodeReadFaninIndex( pNode, pFanin ) == -1 )
        return NULL;
    if ( pNode->Type != MV_NODE_INT || pFanin->Type != MV_NODE_INT )
        return NULL;

    // consider the special case when pFanin is a constant or a buffer
    // and both nodes are binary and have SOP representation available
    if ( pNodeNew = Ntk_NodeCollapseSpecialCase( pNode, pFanin ) )
        return pNodeNew;

    // get the temporary storage for "translation maps"
    pVm           = Ntk_NodeReadFuncVm( pNode );   
    pTransMapNInv = Vm_VarMapGetStorageSupport1( pVm );
    pTransMapF    = Vm_VarMapGetStorageSupport2( pVm );

    // derive the collapsed node; fill the translation maps 
    pNodeNew = Ntk_NodeCombineFanins( pNode, pFanin, pTransMapNInv, pTransMapF );
    pVmNew  = Ntk_NodeReadFuncVm( pNodeNew );   

    // consider the case when both Cvrs are available
    // in this case, it is better to use the SOP representation for collapsing
    pCvrN = Ntk_NodeReadFuncCvr( pNode );
    pCvrF = Ntk_NodeReadFuncCvr( pFanin );
    if ( pCvrN && pCvrF )
    { 
        // derive the relation of the collapsed node
        pCvrNew = Cvr_CoverCreateCollapsed( pCvrN, pCvrF, pVmNew, pTransMapNInv, pTransMapF );
        // set the new relation at the new node
        Ntk_NodeWriteFuncCvr( pNodeNew, pCvrNew );
    }
    else // the SOPs are not available, use BDDs
    {
        pMvrN = Ntk_NodeGetFuncMvr( pNode );
        pMvrF = Ntk_NodeGetFuncMvr( pFanin );
        // derive the relation of the collapsed node
        pMvrNew = Mvr_RelationCreateCollapsed( pMvrN, pMvrF, pVmNew, pTransMapNInv, pTransMapF );
        // set the new relation at the new node
        Ntk_NodeWriteFuncMvr( pNodeNew, pMvrNew );
    }
    return pNodeNew;
}

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

  Synopsis    [Derives the collapsed node when the fanin is a simple node.]

  Description [Derives the collapsed node without making iy minimum base
  and without adding it to the network. Considers the special case when
  pFanin is an inverter or a buffer, and when both the node and the fanin 
  are binary nodes with SOPs derived.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Ntk_Node_t * Ntk_NodeCollapseSpecialCase( Ntk_Node_t * pNode, Ntk_Node_t * pFanin )
{
    Ntk_Node_t * pNodeNew, * pFaninFanin;
    Cvr_Cover_t * pCvrNode, * pCvrFanin, * pCvrNew;
    Mvc_Cover_t * pMvcNode, * pMvcFanin, * pMvcNew;
    Mvc_Cover_t ** pIsetsNew;
    Vm_VarMap_t * pVm;
    int DefNode, DefFanin;
    int VarNum,  ValueFirst;
    int VarNumF, ValueFirstF;
    bool fNeedToPatchFanin;

    if ( pNode->nValues != 2 || pFanin->nValues != 2 )
        return NULL;
    if ( Ntk_NodeReadFaninNum(pFanin) > 1 )
        return NULL;

    pCvrNode  = Ntk_NodeReadFuncCvr(pNode);
    pCvrFanin = Ntk_NodeReadFuncCvr(pFanin);
    if ( pCvrNode == NULL || pCvrFanin == NULL )
        return NULL;

    DefNode  = Cvr_CoverReadDefault( pCvrNode );
    DefFanin = Cvr_CoverReadDefault( pCvrFanin );
    if ( DefNode < 0 || DefFanin < 0 )
        return NULL;
 
    // get the covers
    pMvcNode  = Cvr_CoverReadIsetByIndex( pCvrNode,  DefNode  ^ 1 );
    pMvcFanin = Cvr_CoverReadIsetByIndex( pCvrFanin, DefFanin ^ 1 );
//    assert( pMvcFanin->nBits == 0 || pMvcFanin->nBits == 2 );
    if ( pMvcFanin->nBits != 0 && pMvcFanin->nBits != 2 )
        return NULL;

    // fix the case when the fanin appears to be single-input 
    // (that is, pMvcFanin->nBits == 2) but is in fact constant 1
    if ( pMvcFanin->nBits == 2 && Mvc_CoverReadCubeNum(pMvcFanin) != 1 )
    {
        Mvc_CoverContain( pMvcFanin );
        if ( Mvc_CoverReadCubeNum(pMvcFanin) == 2 )
            Mvc_CoverMakeTautology( pMvcFanin );
        Ntk_NodeMakeMinimumBase( pFanin );
        // get the new version of pMvcFanin
        pCvrFanin = Ntk_NodeReadFuncCvr(pFanin);
        DefFanin  = Cvr_CoverReadDefault( pCvrFanin );
        pMvcFanin = Cvr_CoverReadIsetByIndex( pCvrFanin, DefFanin ^ 1 );
    }

    // get the number of pFanin in pNode and the starting bit
    VarNum = Ntk_NodeReadFaninIndex( pNode, pFanin );
    assert( VarNum >= 0 );
    pVm    = Ntk_NodeReadFuncVm( pNode );
    ValueFirst = Vm_VarMapReadValuesFirst( pVm, VarNum );
 
    // consider several cases
    fNeedToPatchFanin = 0;
    if ( pMvcFanin->nBits == 0 ) // constant node
    {
        if ( Mvc_CoverIsEmpty(pMvcFanin) ^ DefFanin )
            pMvcNew = Mvc_CoverCofactor( pMvcNode, ValueFirst, ValueFirst + 1 );
        else
            pMvcNew = Mvc_CoverCofactor( pMvcNode, ValueFirst + 1, ValueFirst );
        Mvc_CoverContain( pMvcNew );
    }
    else // buffer or interter
    {

        // two cases are possible: 
        // (1) the fanin's fanin is in the current support of the node
        // (2) the fanin's fanin is not in the current support of the node
        pFaninFanin = Ntk_NodeReadFaninNode( pFanin, 0 );
        VarNumF     = Ntk_NodeReadFaninIndex( pNode, pFaninFanin );

        if ( VarNumF >= 0 )
        { // case (1) 
            ValueFirstF = Vm_VarMapReadValuesFirst( pVm, VarNumF );
            // transform the cover by univerisally quantifying pFanin
            if ( Mvc_CoverIsBinaryBuffer(pMvcFanin) ^ DefFanin )
                pMvcNew = Mvc_CoverUnivQuantify( pMvcNode, ValueFirstF, ValueFirstF + 1, ValueFirst, ValueFirst + 1 );
            else
                pMvcNew = Mvc_CoverUnivQuantify( pMvcNode, ValueFirstF, ValueFirstF + 1, ValueFirst + 1, ValueFirst );
            Mvc_CoverContain( pMvcNew );
            // as a result of this operation, pFanin becomes a redundant variable of pNode
        }
        else
        { // case (2)
            if ( Mvc_CoverIsBinaryBuffer(pMvcFanin) ^ DefFanin )
                pMvcNew = Mvc_CoverDup( pMvcNode );
            else
                pMvcNew = Mvc_CoverFlipVar( pMvcNode, ValueFirst, ValueFirst + 1 );
            // this is the only case, when we need to patch the fanin
            fNeedToPatchFanin = 1;
        }
    }
    
    // create the empty Cvr
    pIsetsNew = ALLOC( Mvc_Cover_t *, 2 );
    pIsetsNew[DefNode  ] = NULL;
    pIsetsNew[DefNode^1] = pMvcNew;
    pCvrNew = Cvr_CoverCreate( pVm, pIsetsNew );

    // create the same node without functionality
    pNodeNew = Ntk_NodeClone( pNode->pNet, pNode );
    // set the functionality of the node
    Ntk_NodeWriteFuncVm( pNodeNew, pVm );
    Ntk_NodeWriteFuncCvr( pNodeNew, pCvrNew );

    // patch the new node's fanin (this will reorder fanins, if necessary)
    if ( fNeedToPatchFanin )
        Ntk_NodePatchFanin( pNodeNew, pFanin, pFaninFanin );
    return pNodeNew;
}


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

  Synopsis    [Merges the fanins of the nodes that are collapsed.]

  Description [This procedure looks at the fanins of pNode and pFanin
  and performs the following tasks: (1) merges two ordered fanin lists 
  into one ordered list and creates the new node with this fanin list;
  (2) assigns the "translation maps" for pNode/pFanin (an entry in the 
  translation map shows where the given fanin of pNode/pFanin goes
  in the new variable map); (3) creates the new variable map and 
  attaches it to the new node.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Ntk_Node_t * Ntk_NodeCombineFanins( Ntk_Node_t * pNode, Ntk_Node_t * pFanin, 
         int * pTransMapNInv, int * pTransMapF )