simpfull.c

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

        aTemp1 = sarray_fetch(sarray_t *, aLevelAll, i);
        if (pInfo->verbose)
            printf("BFS [%d]:", i);
        
        /* last set consists of all PIs (hassle free) */
        if ( i == aLevelAll->num - 1 ) {
            sarrayForEachItem(Ntk_Node_t *, aTemp1, j, pNode) {
                if (pNode) {
                    sarray_insert_last( Ntk_Node_t *, aListFinal, pNode );
                    if (pInfo->verbose)
                        printf(" %s", Ntk_NodeGetNamePrintable(pNode));
                }
            }
            sarray_free(aTemp1);
            if (pInfo->verbose)
                printf("\n");
            continue;
        }
        
        /* insert into the final list */
        if ( aTemp1->num > 1 ) {
            sarray_sort( aTemp1, SimpNodeSupportCompare );
        }
        
        for ( j = 0; j < aTemp1->num; ++j) {
            pNode = sarray_fetch(Ntk_Node_t *, aTemp1, j);
            if (pNode) {
                sarray_insert_last( Ntk_Node_t *, aListFinal, pNode );
                if (pInfo->verbose)
                    printf(" %s", Ntk_NodeGetNamePrintable(pNode));
            }
        }
        sarray_free(aTemp1);
        if (pInfo->verbose) printf("\n");
    }
    sarray_free(aLevelAll);
    
    return aListFinal;
}



/*---------------------------------------------------------------------------*/
/* Definition of static functions                                            */
/*---------------------------------------------------------------------------*/

/**Function********************************************************************
  Synopsis    [Compute the CODC set and simplify the node.]
  Description [Return true if a timeout has occured.]
  SideEffects []
  SeeAlso     []
******************************************************************************/
bool
SimpSimplifyWithCodc(
    Ntk_Node_t  *pNode,
    Simp_Info_t *pInfo)
{
    bool         timeout_occured, fChanged;
    DdNode      *pCodc;
    Ntk_Node_t  *pNodeDc;
    Simp_Node_t *simp_data;
    
    /* some sanity checks */
    simp_data = Simp_DaemonGetNodeData(pNode);
    if ( simp_data == NULL) return 0;
    
    /* skip constant and CI nodes */
    if (Ntk_NodeIsCi(pNode) ||
        Ntk_NodeReadFaninNum(pNode)<=1 ) {
        simp_data->pCodc = Cudd_ReadLogicZero(pInfo->ddmg);
        Cudd_Ref(simp_data->pCodc);
        return 0;
    }
    if (pInfo->verbose) {
        printf("\nFull-simplify start node [%s]\n",
               Ntk_NodeGetNamePrintable(pNode));
    }
    
    /* special treatment for floating nodes */
    if ( SimpNodeIsOrphan( pNode, simp_data ) ){
        
        simp_data->fBadnode = TRUE;
        if ( simp_data->pCodc ) {
            Cudd_RecursiveDeref( pInfo->ddmg, simp_data->pCodc );
            simp_data->pCodc = NULL;
        }
        
        SimpProcessOrphanRecur(pNode);
        if (pInfo->verbose) {
            printf("warning: node %s has no fanout\n",
                   Ntk_NodeGetNamePrintable(pNode));
        }
        return 0;
    }
    
    /* start recording time budget */
    timeout_occured = 0;
    fChanged = FALSE;
    pNodeDc  = NULL;
    pCodc    = NULL;
    SimpTimeOutStartNode(pInfo, pInfo->timeout_node);
    
    /* compute CODC in MDDs */
    if ( pInfo->dc_type == 1 ) {      /* SDC */
        pCodc = NULL;
    }
    else if ( pInfo->dc_type == 3 ) { /* Complete */
        pCodc = Simp_ComputeFlex( pInfo, pNode );
    }
    else {                            /* MODC/CODC */
        pCodc = Simp_ComputeCodc(pInfo, pNode);
    }
    pInfo->time_cspf += clock() - pInfo->time_start_node;
    timeout_occured = SimpTimeOutCheckNode(pInfo);
    
    
    /* compute image in the local support */
    if (!timeout_occured) {
        pNodeDc = Simp_ComputeImage(pInfo, pNode, pCodc);
    }
    pInfo->time_imag += clock() - pInfo->time_start_node;
    timeout_occured = SimpTimeOutCheckNode(pInfo);
    
    /* dispose of the CODC */
    if (pCodc) Cudd_RecursiveDeref(pInfo->ddmg, pCodc);
    
    if ( pInfo->verbose ) {
        Vm_VarMap_t *pVm;
        Cvr_Cover_t *pCf, *pCd;
        pVm = Ntk_NodeReadFuncVm( pNode );
        pCf = Ntk_NodeGetFuncCvr( pNode );
        pCd = (pNodeDc)?Ntk_NodeReadFuncCvr( pNodeDc ):NULL;
        
        printf("Simplifying: nValsIn[%3d] nValsOut[%3d] nCubesOn[%3d] nCubesDc[%3d]\n",
               Vm_VarMapReadValuesInNum( pVm ),
               Vm_VarMapReadValuesOutNum( pVm ),
               Cvr_CoverReadCubeNum( pCf ),
               (pCd) ? Cvr_CoverReadCubeNum( pCd ) : 0 );
    }
    
    /* minimize the node */
    fChanged = Simp_NodeSimplifyDc(pNode, pNodeDc,
                                   pInfo->method,  pInfo->accept,
                                   pInfo->fSparse, pInfo->fConser,
                                   pInfo->fPhase,  pInfo->fRelatn);
    
    if ( pInfo->verbose && fChanged ) {
        printf( "Simplified!\n" );
    }
    
    pInfo->time_mini += clock() - pInfo->time_start_node;
    timeout_occured = SimpTimeOutCheckNode(pInfo);
    
    /* dispose of the local CODC node */
    if ( pNodeDc ) {
        Ntk_NodeDelete( pNodeDc );
    }
    
    /* rebuild the global BDD only when the old node is replaced;
       also, CO nodes always have the same (or less) global function
    */
    if (fChanged) {
        SimpNodeUpdate( pNode, pInfo );
        pInfo->time_glob += clock() - pInfo->time_start_node;
        timeout_occured = SimpTimeOutCheckNode(pInfo);
    }
    
    assert( Ntk_NetworkCheckNode(pInfo->network, pNode) );
    
    /* compute MODC for fanin edges (codc|modc) */
    if ( !timeout_occured &&
         (pInfo->dc_type == 0 || pInfo->dc_type == 2) ) {
        SimpComputeMspf(pNode, pInfo);
    }
    
    return timeout_occured;
}

/**Function********************************************************************
  Synopsis    [Compute the MDD array (local and global) for all nodes.]
  Description [Should allow giving-up gracefully if the MDD size explode.]
  SideEffects []
  SeeAlso     []
******************************************************************************/
bool
SimpComputeMddGlobal(
    Ntk_Network_t * pNet,
    Simp_Info_t   * pInfo) 
{
    int            i, k, nBits, nLeaves, nValues, iStick, iIndex;
    int          * pValuesFirst;
    int          * pBits, *pBitsFirst, *pBitsOrder;
    char        ** psLeavesByName;
    Ntk_Node_t   * pNode, * pNodeCi;
    Vmx_VarMap_t * pVmx;
    DdNode      ** pbCodes, ** pbFuncs;
    DdManager    * ddmg;

    ddmg = pInfo->ddmg;
    
    // get the CI variable order
    psLeavesByName = Ntk_NetworkOrderArrayByName( pNet, 0 );
    // get the variable map
    pVmx = Ntk_NetworkGlobalGetVmx( pNet, psLeavesByName );
    pInfo->pVmx = pVmx;
    
    // extend the global manager if necessary
    nBits = Vmx_VarMapReadBitsNum( pVmx );
    for ( i = ddmg->size; i < nBits; i++ )
        Cudd_bddIthVar( ddmg, i );
    
    // encode the CI variables
    pbCodes = Vmx_VarMapEncodeMap( ddmg, pVmx );
    // get the pointer to the first values
    pValuesFirst = Vm_VarMapReadValuesFirstArray( Vmx_VarMapReadVm(pVmx) );
    // assign the elementary BDDs to the values of the CIs
    nLeaves = Ntk_NetworkReadCiNum( pNet );
    
    /* store relationship between BDD ID and node */
    pInfo->ppNodes = ALLOC( Ntk_Node_t *, Cudd_ReadSize( ddmg ) );
    memset( pInfo->ppNodes, 0, Cudd_ReadSize(ddmg) * sizeof(Ntk_Node_t *));
    pBits      = Vmx_VarMapReadBits(pVmx);
    pBitsFirst = Vmx_VarMapReadBitsFirst(pVmx);
    pBitsOrder = Vmx_VarMapReadBitsOrder(pVmx);
    
    for ( i = 0; i < nLeaves; i++ )
    {
        pNodeCi = Ntk_NetworkFindNodeByName( pNet, psLeavesByName[i] );
        assert( pNodeCi );
        // copy the elementary MDDs into the CIs
        nValues = Ntk_NodeReadValueNum( pNodeCi );
        pbFuncs = ALLOC( DdNode *, nValues );
        k = 0;
        do {
            pbFuncs[k] = (pbCodes + pValuesFirst[i])[k];
            Cudd_Ref( pbFuncs[k++] );
        }
        while ( k < nValues );
        Ntk_NodeWriteFuncGlo( pNodeCi, pbFuncs );
        
        /* store the BDD ID info */
        iStick = 0;
        for (k=0; k<pBits[i]; ++k) {
            
            iIndex = pBitsOrder[pBitsFirst[i] + k];
            if ( iStick != iIndex ) {
                pInfo->ppNodes[iIndex] = pNodeCi;
                iStick = iIndex;
            }
        }
    }
    // deref the codes 
    Vmx_VarMapEncodeDeref( ddmg, pVmx, pbCodes );
    
    Ntk_NetworkDfs(pNet, 1);
    
    Ntk_NetworkForEachNodeSpecial(pNet, pNode) {
        
        /* compute global function only if neccessary */
        if ( Ntk_NodeIsCi(pNode) || Ntk_NodeIsCo(pNode) )
            /* SimpNodeIsSubset(pNode)*/
            continue;
        pbFuncs = Ntk_NodeGlobalMdd( ddmg, pNode);
        Ntk_NodeWriteFuncGlo(pNode, pbFuncs);
    }
    
    FREE( psLeavesByName );
    return 0;
}


/**Function********************************************************************
  Synopsis    [Initialize the simplify related data structure for a node.]
  Description [Initialize the simplify related data structure for a node. A
  new structure is returned, which should be freed by the user. ]
  SideEffects []
  SeeAlso     []
******************************************************************************/
Simp_Node_t *
SimpNodeInit(
    Ntk_Network_t *pNet,
    Ntk_Node_t    *pNode) 
{
    Simp_Node_t *pSimp;
    
    pSimp = ALLOC(Simp_Node_t, 1);
    memset(pSimp, 0, sizeof(Simp_Node_t));
    
    pSimp->stCi  = SimpNodeSupportCi(pNet, pNode);
    return pSimp;
}

/**Function********************************************************************
  Synopsis    [Free the simplify related data structure for a node.]
  Description [Free the simplify related data structure for a node.]
  SideEffects []
  SeeAlso     []
******************************************************************************/
void
SimpNodeEnd(
    Simp_Info_t *pInfo,
    Ntk_Node_t  *pNode) 
{
    int i, nFanins;
    Simp_Node_t *pSimp;
    DdManager   *dd;
    
    pSimp = Simp_DaemonGetNodeData(pNode);