ntkiresub.c

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

    Ntk_NetworkIncrementTravId( pNode->pNet );

    // start the linked list
    Ntk_NetworkStartSpecial( pNode->pNet );
    // go through the fanin's fanouts
    nCands = 0;
    Ntk_NodeForEachFanin( pNode, pPin, pFanin )
    {
        Ntk_NodeForEachFanout( pFanin, pPin2, pFanout )
        {
            // skip the nodes in the TFO of node
            if ( Ntk_NodeIsTravIdPrevious(pFanout) )
                continue;
            // skip the visited node
            if ( Ntk_NodeIsTravIdCurrent(pFanout) )
                continue;
            // skip the CI/CO nodes
            if ( !Ntk_NodeIsInternal(pFanout) )
                continue;
            // mark the node as visited
            Ntk_NodeSetTravIdCurrent( pFanout );

            // skip if pFanout is a fanin of pNode
            if ( Ntk_NodeReadFaninIndex( pNode, pFanout ) >= 0 )
                continue;
            // skip the nodes, whose support is not contained
            if ( !Ntk_NodeSupportContain( pNode, pFanout ) )
                continue;
            // skip the dangling nodes
            if ( !Ntk_NodeHasCoInTfo( pFanout ) )
                continue;

            // add and mark the node
            Ntk_NetworkAddToSpecial( pFanout );
            // count the node
            nCands++;
            if ( nCands >= 100 )
                break;
        }
        if ( nCands >= 100 )
            break;
    }
    // finalize the linked list
    Ntk_NetworkStopSpecial( pNode->pNet );

    // take the smallest nCandMax candidates
    if ( nCands <= nCandMax )
        return nCands;
    Ntk_NetworkSortResubCands( pNode->pNet, nCands, nCandMax );
    return nCandMax;
}

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

  Synopsis    [Derives the relation of the node after resubstitution.]

  Description [Takes the network with the list of candidates (nCands).
  Returns the network with the list of candidates (nCandLimit), 
  the smallest by size.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Ntk_NetworkSortResubCands( Ntk_Network_t * pNet, int nCands, int nCandLimit )
{
    Ntk_Node_t ** ppNodes;
    int RetValue, i;

    assert( nCands > nCandLimit );
    ppNodes = ALLOC( Ntk_Node_t *, nCands );
    RetValue = Ntk_NetworkCreateArrayFromSpecial( pNet, ppNodes );
    assert( RetValue == nCands );

    // sort
    qsort( (void *)ppNodes, nCands, sizeof(Ntk_Node_t *), 
        (int (*)(const void *, const void *)) Ntk_NetworkResubCompareNodes );
    assert( Ntk_NetworkResubCompareNodes( ppNodes, ppNodes + nCands - 1 ) <= 0 );

    // take the largest nCandLimit resub candidates available
    Ntk_NetworkStartSpecial( pNet );
    for ( i = 0; i < nCandLimit; i++ )
        Ntk_NetworkAddToSpecial( ppNodes[i] );
    Ntk_NetworkStopSpecial( pNet );
    FREE( ppNodes );
}

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

  Synopsis    [Compares two nodes by the number of their fanins.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_NetworkResubCompareNodes( Ntk_Node_t ** ppN1, Ntk_Node_t ** ppN2 )
{
    // compare using number of fanins
    if ( (*ppN1)->lFanins.nItems < (*ppN2)->lFanins.nItems )
        return  1;
    if ( (*ppN1)->lFanins.nItems > (*ppN2)->lFanins.nItems )
        return -1;
    return 0;
}

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

  Synopsis    [Derives the relation of the node after resubstitution.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Mvr_Relation_t * Ntk_NetworkDeriveResubMvr( Ntk_Node_t * pNode, 
     Mvr_Relation_t * pMvr, Ntk_Node_t * ppCands[], int nCands )
{
    Ntk_Node_t * pFanin;
    Ntk_Pin_t * pPin;
    DdManager * dd;
    Vm_VarMap_t * pVm, * pVmNew;
    Vmx_VarMap_t * pVmx, * pVmxCand, * pVmxNew;
    DdNode * bRelNew, * bComp, * bTemp;
    Mvr_Relation_t * pMvrCand, * pMvrNew;
    int * pValues, * pValuesNew;
    int * pTransMapInv, * pTransMap;
    int i, k, nVarsIn, nVarsTotal;

    // read the parameters
    pVm     = Mvr_RelationReadVm(pMvr);
    pVmx    = Mvr_RelationReadVmx(pMvr);
    assert( pVm == Ntk_NodeReadFuncVm(pNode) );

    nVarsIn    = Vm_VarMapReadVarsInNum( pVm );
    nVarsTotal = nVarsIn + nCands + 1;
    pValues    = Vm_VarMapReadValuesArray( pVm );

    // create the var map for the resulting relation
    pValuesNew = ALLOC( int, nVarsTotal );
    pTransMapInv = ALLOC( int, nVarsTotal ); // for each new var, its place in the old map
    for ( i = 0; i < nVarsIn; i++ )
    {
        pValuesNew[i] = pValues[i];
        pTransMapInv[i] = i;
    }
    for ( i = 0; i < nCands; i++ )
    {
        pValuesNew[nVarsIn+i] = ppCands[i]->nValues;
        pTransMapInv[nVarsIn+i] = -1;
    }
    pValuesNew[nVarsIn+nCands] = pValues[nVarsIn];
    pTransMapInv[nVarsIn+nCands] = nVarsIn;

    pVmNew  = Vm_VarMapLookup( Vm_VarMapReadMan(pVm), nVarsTotal - 1, 1, pValuesNew );
    pVmxNew = Vmx_VarMapCreateExpanded( pVmx, pVmNew, pTransMapInv );
    FREE( pValuesNew );
    FREE( pTransMapInv );

    // remap the relations of the nodes and add them to the original relation
    pTransMap = ALLOC( int, nVarsTotal );  // for each old var, its place in the new map
    dd        = Mvr_RelationReadDd( pMvr );
    bRelNew   = Mvr_RelationReadRel(pMvr);  Cudd_Ref( bRelNew );
    for ( i = 0; i < nCands; i++ )
    {
        // get the relation of the node
        pMvrCand = Ntk_NodeGetFuncMvr( ppCands[i] );
        // create the var map for remapping the relation
        for ( k = 0; k < nVarsTotal; k++ )
            pTransMap[k] = -1;
        Ntk_NodeForEachFaninWithIndex( ppCands[i], pPin, pFanin, k )
        {
            pTransMap[k] = Ntk_NodeReadFaninIndex( pNode, pFanin );
            assert( pTransMap[k] >= 0 );
        }
        pTransMap[k] = nVarsIn + i; // the output
        // permute the relation
        bComp    = Mvr_RelationReadRel(pMvrCand);
        pVmxCand = Mvr_RelationReadVmx(pMvrCand);
        bComp = Mvr_RelationRemap( pMvrCand, bComp, pVmxCand, pVmxNew, pTransMap );
        Cudd_Ref( bComp );

        // add the permuted relation
        bRelNew = Cudd_bddOr( dd, bTemp = bRelNew, Cudd_Not(bComp) ); Cudd_Ref( bRelNew );
        Cudd_RecursiveDeref( dd, bTemp );
        Cudd_RecursiveDeref( dd, bComp );
    }
    FREE( pTransMap );

    // create the relation
    pMvrNew = Mvr_RelationCreate( Mvr_RelationReadMan(pMvr), pVmxNew, bRelNew ); 
    Cudd_Deref( bRelNew );
    // reorder the relation
    Mvr_RelationReorder( pMvrNew );
    return pMvrNew;
}



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

  Synopsis    [Orders the internal nodes by level.]

  Description [Orders the internal nodes by level. If the flag is set to 1,
  the DFS is performed starting from the COs. In this case, levels are 
  assigned starting from the CIs. The resulting array begins with nodes 
  that are closest to the CIs and ends with the nodes that are closest 
  to the COs. If the flag is set to 0, the situation is reversed.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Ntk_Node_t ** Ntk_NetworkOrderNodesByLevel( Ntk_Network_t * pNet, bool fFromOutputs )
{
    Ntk_Node_t ** ppNodes;
    Ntk_Node_t * pNode;
    int nNodes, Level, i;

    // collect all nodes into an array
    nNodes = Ntk_NetworkReadNodeIntNum( pNet );
    ppNodes = ALLOC( Ntk_Node_t *, nNodes );
    i = 0;
    Ntk_NetworkForEachNode( pNet, pNode )
        ppNodes[i++] = pNode;
    assert( i == nNodes );

    // levelize the nodes
    Ntk_NetworkLevelizeNodes( ppNodes, nNodes, fFromOutputs );

    // collect nodes into the array by level
    i = 0;
    for ( Level = 0; Level <= pNet->nLevels + 1; Level++ )
        Ntk_NetworkForEachNodeSpecialByLevel( pNet, Level, pNode )
            if ( Ntk_NodeIsInternal(pNode) )
            {
                ppNodes[i++] = pNode;
                // set the number of literals
                pNode->pCopy = (Ntk_Node_t *)Cvr_CoverReadLitFacNum( Ntk_NodeGetFuncCvr(pNode) );

            }
    assert( i == nNodes );

    // sort the nodes by level and then by the number of literals
    qsort( (void *)ppNodes, nNodes, sizeof(Ntk_Node_t *), 
        (int (*)(const void *, const void *)) Ntk_NetworkMfsCompareNodes );
    assert( Ntk_NetworkMfsCompareNodes( ppNodes, ppNodes + nNodes - 1 ) <= 0 );

    return ppNodes;
}

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

  Synopsis    [Compares two nodes by the number of their fanins.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Ntk_NetworkMfsCompareNodes( Ntk_Node_t ** ppN1, Ntk_Node_t ** ppN2 )
{
    // compare using number of levels
    if ( (*ppN1)->Level < (*ppN2)->Level )
        return -1;
    if ( (*ppN1)->Level > (*ppN2)->Level )
        return  1;
    // now compute using the number of lits in the FF
    if ( (*ppN1)->pCopy > (*ppN2)->pCopy )
        return -1;
    if ( (*ppN1)->pCopy < (*ppN2)->pCopy )
        return  1;
    return 0;
}

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