simpimage.c

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

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

  FileName    [simpImage.c]

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

  Synopsis    [Image computation]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: simpImage.c,v 1.21 2003/05/27 23:16:15 alanmi Exp $]

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

#include "simpInt.h"
#include "var_set.h"


/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/

/**AutomaticStart*************************************************************/

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

static Ntk_Node_t  *SimpComputeImageIntern(Simp_Info_t *i,Ntk_Node_t *n,DdNode *codc);
static Mvc_Cover_t *SimpComputeRangeRecur(Simp_Info_t *pInfo, sarray_t **flist,
                                          sarray_t **aNodes, Vm_VarMap_t *pVm,
                                          Mvc_Data_t *pMvcData, int start_index);
static Mvc_Cover_t *SimpRangeOne   ( Simp_Info_t *pInfo, Vm_VarMap_t *pVm,
                                     int i, var_set_t *s,sarray_t *f );
static Mvc_Cover_t *SimpRangeTwo   ( Simp_Info_t *pInfo, Vm_VarMap_t *pVm,
                                     Mvc_Data_t *pMvcData,int i, var_set_t *s,
                                     sarray_t *f );
static Mvc_Cover_t *SimpRangeCofact( Simp_Info_t *info, Vm_VarMap_t *pVm,
                                     Mvc_Data_t *pMvcData, int i, var_set_t *s,
                                     sarray_t *f, sarray_t **n );

static Mvc_Cover_t *SimpCubeLiteral     (Mvc_Manager_t *pMem,Vm_VarMap_t *pVm, int iIndex, int iConst);
static Mvc_Cover_t *SimpCubeLiteralRange(Mvc_Manager_t *pMem,Vm_VarMap_t *pVm, int iIndex, sarray_t *r);
static Mvc_Cover_t *SimpCubeLiteralImage(Mvc_Manager_t *pMem,Vm_VarMap_t *pVm, DdManager *mg,
                                         int index, Mva_Func_t *pMva );


static sarray_t    *SimpDisjointSupports(sarray_t *nodes, sarray_t *funcs,
                                         int start_index, Simp_Info_t *pInfo);
static bool         SimpNodeCheckSupport(Ntk_Node_t *node);
static Mvc_Data_t * SimpAllocateMvcData( Ntk_Node_t *pNode );
static void         SimpFreeMvcData( Ntk_Node_t *pNode, Mvc_Data_t *pMvcData );


/**AutomaticEnd***************************************************************/


/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/

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

  Synopsis    [Compute the image of a don't care set.]

  Description [Compute the image of a don't care set. Given a don't care set
  represented in MDDs with CI variables, this routine uses recursively image
  computation to map the care-set to the local support of the node; and finaly
  complement again to give the local don't care set, returned as a separate
  node (may have different fanin nodes vs. the original one.) 
  If the image computation failed, then the SDC set of
  the local fanin support will be computed for substitute.]

  SideEffects []

  SeeAlso     []

******************************************************************************/
Ntk_Node_t *
Simp_ComputeImage(
    Simp_Info_t *pInfo,
    Ntk_Node_t  *pNode,
    DdNode      *bCodc)
{
    DdManager   *mg;
    DdNode      *bCare;
    Simp_Node_t *simp_data;
    Ntk_Node_t  *pNodeDc, *pNodeCare, *pNodeSdc, *pNodeTmp;
    
    if (pNode==NULL) return NULL;
    
    simp_data = Simp_DaemonGetNodeData(pNode);
    if (simp_data==NULL) return NULL;
    
    mg = pInfo->ddmg;
    
    /* special cases */
    if (bCodc == NULL) {
        bCodc = Cudd_ReadLogicZero(mg);
        Cudd_Ref( bCodc );
    }
    else if (bCodc == Cudd_ReadOne(mg)) {
        /* whole space is don't care, return constant one node */
        pNodeDc = Ntk_NodeCreateConstant( Ntk_NodeReadNetwork(pNode), 2, 2 );
        if (pInfo->verbose) {
            printf("CODC(PI): tautology\n");
        }
        return pNodeDc;
    }
    else {
        Cudd_Ref(bCodc);
        //bCodc = SimpFilterGlobal(pInfo, bCodc, simp_data->stCi);
    }
    
    if (pInfo->verbose) {
        printf("CODC(PI):\t[%d]\n", Cudd_DagSize(bCodc));
    }
    
    /* if all fanins are PI's and DC set is empty then return SDC */
    if (SimpNodeCheckSupport(pNode) && bCodc==Cudd_ReadLogicZero(mg)) {
        
        if (pInfo->verbose) {
            printf("SimpComputeImage: avoid image computation by SDC.\n");
        }
        Cudd_RecursiveDeref( mg, bCodc );
        if (pInfo->use_bres) {
            return Simp_ComputeSdcNewBase(pNode); /* boolean resub */
        } else {
            return Simp_ComputeSdcLocal(pNode);
        }
    }
    
    bCare = Cudd_Not(bCodc);
    
    /* the image would include SDC with boolean resub */
    
    SIMP_EXEC(pNodeCare=SimpComputeImageIntern(pInfo, pNode, bCare),
              pInfo->time_imag);
    Cudd_RecursiveDeref( mg, bCare );
    
    /* if image failed then return SDC */
    if (pNodeCare == NULL) {
        if ( pInfo->use_bres ) {
            pNodeDc = Simp_ComputeSdcNewBase(pNode);
        }
        else {
            pNodeDc = Simp_ComputeSdcLocal(pNode);
        }
    }
    else {
        pNodeDc  = SimpNodeComplement( pNodeCare );
        Ntk_NodeDelete( pNodeCare );
        Ntk_NodeOrderFanins( pNodeDc );
        
        /* supplement the image with subset support SDC */
        if (pInfo->use_bres) {
            
            pNodeSdc = Simp_ComputeSdcNewBase(pNode);
            if ( pNodeSdc ) {
                Ntk_NodeOrderFanins( pNodeSdc );
                pNodeTmp = SimpNodeOr( pNodeDc, pNodeSdc );
                Ntk_NodeDelete( pNodeDc );
                Ntk_NodeDelete( pNodeSdc );
                pNodeDc = pNodeTmp;
            }
        }
    }
    
    return pNodeDc;
}



/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/

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

  Synopsis    [Partition the array of function into disjoint support sets.]

  Description [Partition the array of function into disjoint support
  sets. Returns an array of var_set's; each var_set is a set of nodes with
  common supports; the var_set contains a set of indexes (int) into the
  original array.]]

  SideEffects []
  SeeAlso     []
******************************************************************************/
sarray_t *
SimpDisjointSupports(
    sarray_t *nodes,
    sarray_t *funcs,
    int      start_index,
    Simp_Info_t *pInfo) 
{
    int i,j,index, nFuncs, iFirst;
    char       *dummy;
    sarray_t   *listSupp, *listVars, *listInsect;
    var_set_t  *vsTemp, *vsCurr;
    
    Ntk_Node_t *pn, *tmpn;
    Mva_Func_t *pMva;
    
    st_table     *stCurr, *stTemp, *stSupp;
    st_generator *gen;
    
    nFuncs     = sarray_n(funcs);
    listSupp   = sarray_alloc( st_table *,  nFuncs); /* common support nodes   */
    listVars   = sarray_alloc( var_set_t *, nFuncs); /* indices of these nodes */
    listInsect = sarray_alloc( int,         nFuncs); /* intersection nodes     */
    
    for ( i=start_index; i<nFuncs; ++i) {
        
        pn = sarray_fetch(Ntk_Node_t *, nodes, i);
        if ( pn == NIL(Ntk_Node_t) ) continue;
        
        pMva = sarray_fetch( Mva_Func_t *, funcs, i);
        if ( pMva == NULL ) continue;
        
        stSupp = SimpMvaComputeSupport( pMva, pInfo );
        
        if ( sarray_n(listSupp)==0 ) {
            /* the first set */
            sarray_insert_last( st_table *, listSupp, stSupp );
            
            vsTemp = var_set_new( nFuncs );
            var_set_set_elt( vsTemp, i );
            sarray_insert_last( var_set_t *, listVars, vsTemp );
            continue;
        }
        
        listInsect->num = 0;
        /* record all disjoint groups that intersect */
        for (j=0; j<sarray_n(listSupp); ++j) {
            
            stCurr = sarray_fetch(st_table *, listSupp, j);
            if (stCurr==NIL(st_table)) {
                continue;
            }
            st_foreach_item(stSupp, gen, (char **)&tmpn, NIL(char*)) {
                if (st_lookup(stCurr, (char *)tmpn, &dummy)) {
                    sarray_insert_last( int, listInsect, j );
                    st_free_gen( gen );  /* pre-emption: memory leak */
                    break;
                }
            }
        }
        if (sarray_n(listInsect) == 0) {
            /* no intersection; create a new support set */
            sarray_insert_last( st_table *, listSupp, stSupp );
            
            vsTemp = var_set_new(nFuncs);
            var_set_set_elt(vsTemp, i);
            sarray_insert_last( var_set_t *, listVars, vsTemp );
            continue;
        }
        else {
            
            /* combine all st_tables that intersects this *pn */
            iFirst = -1;
            for (j=0; j<sarray_n(listInsect); ++j) {
                
                index  = sarray_fetch(int, listInsect, j);
                stTemp = sarray_fetch(st_table *, listSupp, index);
                vsTemp = sarray_fetch(var_set_t *, listVars, index);
                
                if ( iFirst < 0 ) iFirst = index;
                
                /* reuse the first existing table and var_set */
                if ( j==0 ) {
                    stCurr = stTemp;
                    vsCurr = vsTemp;
                }
                else {
                    st_foreach_item(stTemp, gen, (char **)&tmpn, NIL(char*)) {
                        st_insert(stCurr, (char *)tmpn, NIL(char));
                    }
                    st_free_table(stTemp);
                    
                    /* combine all sets into one */
                    var_set_or(vsCurr, vsCurr, vsTemp);
                    var_set_free(vsTemp);
                }
                sarray_insert( st_table *,  listSupp, index, NIL(st_table) );
                sarray_insert( var_set_t *, listVars, index, NIL(var_set_t));
            }
            
            /* combine with the current support set */
            st_foreach_item(stSupp, gen, (char **)&tmpn, NIL(char *)) {
                st_insert(stCurr, (char *)tmpn, NIL(char));
            }
            var_set_set_elt(vsCurr, i);
            
            sarray_insert( st_table *,  listSupp, iFirst, stCurr);
            sarray_insert( var_set_t *, listVars, iFirst, vsCurr);
            
            st_free_table(stSupp); // new
        }
    }
    sarray_free(listInsect);
    
    /* wrap up listSupp array of arrays */
    for (i=0; i<sarray_n(listSupp); ++i) {
        
        stCurr = sarray_fetch(st_table *, listSupp, i);
        if (stCurr==NIL(st_table)) continue;
        st_free_table(stCurr);
    }
    sarray_free( listSupp );
    sarray_compact( listVars );
    
    return listVars;
}



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

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

  Synopsis    [Compute the image of a set from primary inputs to a local
  support.]

  Description [Compute the image of a set from primary inputs to a local
  support. Given an MDD (assume support variables are combinational inputs),
  compute the image in local input of node. Result is in multi-valued SOP
  format as a separate node. ]

  SideEffects []

  SeeAlso     []

******************************************************************************/
Ntk_Node_t *
SimpComputeImageIntern(
    Simp_Info_t *pInfo,
    Ntk_Node_t *pNode,