cvrespresso.c

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

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

  FileName    [cvrEspresso.c]

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

  Synopsis    [Call Espresso for two-level minimization]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - March 15, 2003.]

  Revision    [$Id: cvrEspresso.c,v 1.27 2003/05/27 23:14:56 alanmi Exp $]

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

#include "mv.h"
#include "cvrInt.h"
#include "espresso.h"
#include "minimize.h"

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/
static pset_family * Cvr_CoverDerivePsfFromMvcVector(Mvc_Cover_t **ppMvc, int nCovers);
static pset_family   Cvr_CoverDerivePsfFromMvc(Mvc_Cover_t *pMvc);
static Mvc_Cover_t **Cvr_CoverDeriveMvcFromPsfVector(Mvc_Manager_t *pMem,
                                                     pset_family *ppCovers,
                                                     int nCovers);
static Mvc_Cover_t * Cvr_CoverDeriveMvcFromPsf(Mvc_Manager_t *pMem,
                                               pset_family pCover);

static void CvrSetupCube( int num_vars, int *part_size );
static void CvrSetupCdata( struct cube_struct *pCube );
static void CvrSetdownCube( void );
static void CvrSetdownCdata( void );

static void _PsetFamilyResetDefault( pset_family *pOnset, int nVal );
static void _PsetFamilyArrayPrint(FILE *pF, pset_family *pcovers,int size,bool verb);
static void _PsetFamilyPrint(FILE *pFile, pset_family psf, bool verb);
static void _PsetPrint(FILE *fp, pcube c, char *out_map);


/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/
static int  nCvrCubeAllocated=64;
static bool fCvrCubeAllocated=0;

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

/**Function********************************************************************
  Synopsis    [Simplify a multi-valued cover using don't cares provided.]
  Description [Simplify a multi-valued cover using don't cares
  provided. According to the `method' provided, call appropriate ESPRESSO
  routines for two-level SOP minimization. Assume the function f and don't
  care dc are made common base, i.e. having the same number of fanins and same
  value for each fanin.]
  SideEffects []
  SeeAlso     []
******************************************************************************/
void
Cvr_CoverEspresso(
    Cvr_Cover_t * pCf,
    Mvc_Cover_t * pCd,     /* binary cover */
    int           method,
    bool          fSparse,
    bool          fConserve,
    bool          fPhase) 
{
    Mvc_Cover_t **ppMvc, *pMvc;
    pset_family   dcset;
    pset_family   offset;
    pset_family  *ponset;
    int           nVal, i;
    bool          fDefault;
    
    if (pCf==NULL) return;
    
    /* deal with tautology i-set */
    if ( Cvr_CoverEspressoSpecial( pCf ) )
        return;
    
    nVal = Vm_VarMapReadValuesOutNum( pCf->pVm );
    
    Cvr_CoverEspressoSetup(pCf->pVm);  /* prepare the cube structure */
    
    
    /* for pure MV pla's, we have to resort to Espresso */
    if (cube.num_binary_vars==0
        && method != 3      /* DCSIMP */
        && method != 6      /* EBD_ISOP */
        && method != 7)     /* SIMPLE */ {
        method = 0;         /* ESPRESSO */
    }
    
    /* if conservative; skip large SOP's */
    if ( method == 0 && fConserve && Cvr_CoverIsTooLarge( pCf ) ) {
        method = 7;    /* conservative */
    }
    
    /* if asked to reset default */
    if ( fPhase ) {
        Cvr_CoverComputeDefault(pCf);
    }
    
    /* convert mvc covers to pset_family */
    ppMvc = Cvr_CoverReadIsets(pCf);
    ponset = Cvr_CoverDerivePsfFromMvcVector(ppMvc, nVal);
    
    
    if (pCd) {
        dcset = Cvr_CoverDerivePsfFromMvc(pCd);
    } else {
        dcset = sf_new(1,0);  /* constant zero */
    }
    
#ifdef DEBUG_ESPRESSO
    printf("\nONSET:\n");
    _PsetFamilyArrayPrint(stdout, ponset,nVal,1);
    printf("\nDCSET:\n");
    _PsetFamilyPrint(stdout, dcset,1);
#endif

    /* Set these to make Espresso() and Minimize() work */
    for (i=0; i<nVal; ++i) {
        if (ponset[i]==NULL || ponset[i]->sf_size==0)
            continue;
        pMvc = ppMvc[i];
        dcset->wsize   = ponset[i]->wsize;
        dcset->sf_size = ponset[i]->sf_size;
        break;
    }
    
    /* assume there is no default i-set */
    fDefault = FALSE;
    
    /* start minimization */
    switch(method) {
        case 0:  /* SIMP_ESPRESSO */
            if ( !fSparse ) {
                skip_make_sparse = 1;
            }
            else {
                skip_make_sparse = 0;
            }
            
            /* minimize each value at a time */
            for (i=0; i<nVal; i++) {
                if ( ponset[i] == NULL ) {
                    fDefault = TRUE;  //there is a default
                    continue;
                }
                if ( ponset[i]->count == 0 )
                    continue;
                
                if (dcset->sf_size==0||dcset->count==0) {
                    
                    if ( nVal == 2 && ponset[nVal-1-i] ) {
                        offset = sf_save( ponset[nVal-1-i] );
                    }
                    else {
                        offset = complement(cube1list(ponset[i]));
                    }
                }
                else  {
                    offset = complement(cube2list(ponset[i],dcset)); 
                }
                ponset[i] = espresso(ponset[i], dcset, offset);
                sf_free(offset); offset = NULL;
            }
            break;
            
        case 1:  /* SIMP_NOCOMP: */
            for (i=0; i<nVal; i++) {
                if ( ponset[i] == NULL ) {
                    fDefault = TRUE;
                    continue;
                }
                if ( ponset[i]->count==0 )
                    continue;
                ponset[i] = minimize(ponset[i], dcset, 0);  /* NOCOMP */
            }
            break;
            
        case 2: /* SIMP_SNOCOMP: */
            for (i=0; i<nVal; i++) {
                if ( ponset[i] == NULL ) {
                    fDefault = TRUE;
                    continue;
                }
                if ( ponset[i]->count==0 )
                    continue;
                ponset[i] = minimize(ponset[i], dcset, 1); /* SNOCOMP */
            }
            break;
            
        case 3: /* SIMP_DCSIMP: */
            for (i=0; i<nVal; i++) {
                if ( ponset[i] == NULL ) {
                    fDefault = TRUE;
                    continue;
                }
                if ( ponset[i]->count==0 )
                    continue;
                ponset[i] = minimize(ponset[i], dcset, 2);  /* DCSIMP */
            }
            break;
            
        case 4: /* SIMP_EXACT: */
            for (i=0; i<nVal; i++) {
                if ( ponset[i] == NULL ) {
                    fDefault = TRUE;
                    continue;
                }
                if ( ponset[i]->count==0 )
                    continue;
                ponset[i] = minimize_exact(ponset[i], dcset, NIL(set_family_t), 1);
            }
            break;
            
        case 5: /* SIMP_EXACT_LITS: */
            for (i=0; i<nVal; i++) {
                if ( ponset[i] == NULL ) {
                    fDefault = TRUE;
                    continue;
                }
                if ( ponset[i]->count==0 )
                    continue;
                ponset[i] = minimize_exact_literals(ponset[i], dcset, NIL(set_family_t), 1);
            }
            break;
            /***
        case SIMP_EBD_ISOP:
            for (i=0; i<nVal; i++) {
                if (ponset[i] == NULL) continue;
                ponset[i] = Simp_EbdIsopCompute(cubestruct, ponset[i],dcset);
            }
            break;
            ***/
        case 7: /* SIMP_SIMPLE: */
            for (i=0; i<nVal; i++) {
                int j;
                if ( ponset[i] == NULL ) {
                    fDefault = TRUE;
                    continue;
                }
                if ( ponset[i]->count==0 )
                    continue;
                
                for (j = 0; j < cube.num_vars; j++) {
                     ponset[i] = d1merge(ponset[i], j);
                }
                ponset[i] = sf_contain( ponset[i] );
            }
            break;
        default:
        {}
    }
    
#ifdef DEBUG_ESPRESSO
    printf("\nRESULT:\n");
    _PsetFamilyArrayPrint(stdout, ponset,nVal,1);
#endif
    
    /* reset the default if asked to do so, or all i-sets are present */
    if ( fPhase || !fDefault ) {
        _PsetFamilyResetDefault( ponset, nVal );
    }
    
    /* convert pset_family to mvc covers in the same mem manager */
    ppMvc = Cvr_CoverDeriveMvcFromPsfVector(pMvc->pMem, ponset, nVal);
    
    /* free temporary pset_families */
    sf_free(dcset);
    for (i=0; i<nVal; ++i) {
        if (ponset[i]) sf_free(ponset[i]);
    }
    FREE( ponset );
    
    /* save the result */
    Cvr_CoverSetIsets(pCf, ppMvc);
    
    /* clean the recycled pset_family's - added by alanmi to prevent memory leaks */
    sf_cleanup();
    Cvr_CoverEspressoSetdown(pCf->pVm);
    return;
}


/**Function********************************************************************
  Synopsis    [Minimize only an i-set]
  Description [Minimize only an i-set. assume that the onset and dcset have
  the same domain. dcset can be set to NULL. need to give the cube structure
  which both f and dc share. Input dcset will remain; a new pointer onset
  will be returned; THE OLD ONSET IS DISPOSED OF!]
  SideEffects []
  SeeAlso     []
******************************************************************************/
Mvc_Cover_t *
Cvr_IsetEspresso(
    Vm_VarMap_t *  pVm,
    Mvc_Cover_t *  pMvcOnset,
    Mvc_Cover_t *  pMvcDcset,
    int            method,
    bool           fSparse,
    bool           fConserve )
{
    bool fCubeAllocated;
    pset_family pOffset, pDcset, pOnset;
    Mvc_Cover_t *pMvcNew;
    
    if ( pMvcOnset==NULL )
        return NULL;
    if ( Mvc_CoverIsEmpty( pMvcOnset ) || Mvc_CoverIsTautology( pMvcOnset ) )
        return Mvc_CoverDup( pMvcOnset );
    
    fCubeAllocated = (cube.fullset == NULL);
    if ( fCubeAllocated ) {
        Cvr_CoverEspressoSetup(pVm);
    }
    
    if (cube.num_binary_vars==0
        && method != 3      /* DCSIMP */
        && method != 6      /* EBD_ISOP */
        && method != 7)     /* SIMPLE */ {
        method = 0;         /* ESPRESSO */
    }
    
    /* conservative; use d1merge */
    if ( method == 0 && fConserve && Cvr_IsetIsTooLarge( pVm, pMvcOnset ) ) {
        method = 7;
    }
    
    /* convert mvc covers to pset_family */
    pOnset = Cvr_CoverDerivePsfFromMvc(pMvcOnset);