cvrfunc.c

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

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

  FileName    [cvrFunc.c]

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

  Synopsis    [The APIs of the Cvr package.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: cvrFunc.c,v 1.17 2003/05/27 23:14:57 alanmi Exp $]

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

#include "cvrInt.h"

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

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

/**Function*************************************************************
  Synopsis    [Compute the default cover by complementing other i-sets.]
  Description []
  SideEffects []
  SeeAlso     []
***********************************************************************/
void
Cvr_CoverComputeDefault (Cvr_Cover_t *cvr)
{
    Mvc_Cover_t *pCunion, *pCtmp;
    int i, iDef, nVal;
    
    assert(cvr);
    iDef = Cvr_CoverReadDefault(cvr);
    if (iDef < 0) return;
    
    nVal = Vm_VarMapReadValuesOutNum(cvr->pVm);
    
    pCunion = NULL;
    for (i=0; i<nVal; i++) {
        if (cvr->ppCovers[i]==NULL) continue;
        if (pCunion==NULL) {
            pCunion = Mvc_CoverDup(cvr->ppCovers[i]);
        }
        else {
            pCtmp   = pCunion;
            pCunion = Mvc_CoverBooleanOr(pCtmp, cvr->ppCovers[i]);
            Mvc_CoverFree(pCtmp);
        }
    }
    
    /* should use filtering for complementation here */
    cvr->ppCovers[iDef] = Cvr_CoverComplement( cvr->pVm, pCunion );
    Mvc_CoverFree(pCunion);
    return;
}

 
/**Function*************************************************************
  Synopsis    [Recompute the default iset as the one with largest cost]
  Description []
  SideEffects []
  SeeAlso     []
***********************************************************************/
void
Cvr_CoverResetDefault (Cvr_Cover_t *cvr)
{
    int i, nVal, nWst, iWst, nTmp;
    
    assert(cvr);
    Cvr_CoverComputeDefault(cvr);
    
    nWst = -1;
    nVal = Vm_VarMapReadValuesOutNum(cvr->pVm);
    for (i=0; i<nVal; i++) {
        nTmp = Mvc_CoverReadCubeNum(cvr->ppCovers[i]);
        if (nWst < nTmp) {
            nWst = nTmp;
            iWst = i;
        }
    }
    Mvc_CoverFree(cvr->ppCovers[iWst]);
    cvr->ppCovers[iWst] = NULL;

    if ( cvr->pTree )
    {
        if ( cvr->pTree->pRoots[iWst] )
        {
            // update the literal counter
            cvr->pTree->nNodes -= Ft_FactorCountLeavesOne( cvr->pTree->pRoots[iWst] );
            // remove the root
            Ft_TreeFreeRoot( cvr->pTree, iWst );
        }
    }
    return;
}


/**Function*************************************************************
  Synopsis    []
  Description []
  SideEffects []
  SeeAlso     []
***********************************************************************/
void
Cvr_CoverSetDefault  ( Cvr_Cover_t * pCvr, int DefValue ) 
{
    assert(DefValue>=0 && DefValue<Vm_VarMapReadValuesOutNum(pCvr->pVm));
    if (pCvr->ppCovers[DefValue] == NULL) return;
    
    Cvr_CoverComputeDefault(pCvr);
    Mvc_CoverFree(pCvr->ppCovers[DefValue]);
    pCvr->ppCovers[DefValue] = NULL;
    
    return;
}


/**Function*************************************************************
  Synopsis    [Test if a cover is constant]
  Description [Return ture is the cover is constant. Bit vector bPos contain
  the output values that are const. (non-deterministic const)]
  SideEffects []
  SeeAlso     []
***********************************************************************/
bool
Cvr_CoverIsConst (
    Cvr_Cover_t *pCvr,
    unsigned    *bPos) 
{
    int i, nVal, nCount=0;
    
    assert(pCvr);
    nVal = Vm_VarMapReadValuesOutNum(pCvr->pVm);
    *bPos = 0;
    
    for (i=0; i<nVal; ++i) {
        if (pCvr->ppCovers[i]==NULL) continue;
        
        if (Mvc_CoverIsTautology(pCvr->ppCovers[i])) {
            nCount++;
            (*bPos) |= (1<<i);
        }
        else if (!Mvc_CoverIsEmpty(pCvr->ppCovers[i])) {
            return FALSE;
        }
    }
    return (nCount);
}

/**Function*************************************************************
  Synopsis    [Adjust the covers to a new variable map.]
  Description [pnPos[i] tells the new position of current variable i]
  SideEffects []
  SeeAlso     []
***********************************************************************/
void
Cvr_CoverAdjust  (
    Cvr_Cover_t *pCvr,
    Vm_VarMap_t *pVmNew,
    int         *pnPos)
{
    int  iVal, nVal;
    Mvc_Cover_t *pMvcNew;
    
    // nVal was not assigned - alanmi
    nVal = Vm_VarMapReadValuesOutNum(pCvr->pVm);

    for (iVal=0; iVal<nVal; ++iVal) {
        if (pCvr->ppCovers[iVal] == NULL) continue;
        pMvcNew = Cvr_IsetAdjust (pCvr->ppCovers[iVal],pVmNew,pCvr->pVm,pnPos);
        Mvc_CoverFree(pCvr->ppCovers[iVal]);
        pCvr->ppCovers[iVal] = pMvcNew;
    }
    return;
}

/**Function*************************************************************
  Synopsis    [Creates the adjusted cover without deallocating the old cover.]
  Description [pnPos[i] tells the new position of current variable i]
  SideEffects []
  SeeAlso     []
***********************************************************************/
Cvr_Cover_t *
Cvr_CoverCreateAdjusted(
    Cvr_Cover_t *pCvr,
    Vm_VarMap_t *pVmNew,
    int         *pnPos)
{
    Mvc_Cover_t ** ppIsets;
    int  iVal, nVal;
    
    nVal = Vm_VarMapReadValuesOutNum(pCvr->pVm);
    ppIsets = ALLOC( Mvc_Cover_t *, nVal );
    for (iVal=0; iVal<nVal; ++iVal) 
    {
        if (pCvr->ppCovers[iVal] == NULL) 
        {
            ppIsets[iVal] = NULL;
            continue;
        }
        ppIsets[iVal] = Cvr_IsetAdjust (pCvr->ppCovers[iVal],pVmNew,pCvr->pVm,pnPos);
    }
    return Cvr_CoverCreate( pVmNew, ppIsets );
}


/**Function*************************************************************
  Synopsis    [Adjust the covers to a new variable map.]
  Description [pnPos[i] tells the new position of current variable i]
  SideEffects []
  SeeAlso     []
***********************************************************************/
Mvc_Cover_t*
Cvr_IsetAdjust (
    Mvc_Cover_t *pIset,
    Vm_VarMap_t *pMnew,
    Vm_VarMap_t *pMold, 
    int         *pnPos)
{
    int  nBits, nVars, nVals, iPos, i, k;
    int *pnBits, *pnFirst;
    Mvc_Cover_t *pMvcNew;
    
    nVars = Vm_VarMapReadVarsInNum(pMold);
    nBits = Vm_VarMapReadValuesInNum(pMnew);
    pnFirst = Vm_VarMapReadValuesFirstArray(pMnew);
    pnBits = ALLOC(int, nBits);
    for ( i=0; i<nBits; ++i ) {
        pnBits[i] = -1;
    }
    
    for (i=0; i<nVars; ++i) {
        nVals = Vm_VarMapReadValues(pMold, i);
        iPos  = Vm_VarMapReadValuesFirst(pMold, i);
        for (k=0; k<nVals; ++k) {
            /* pnBits[new position] = old position */
            pnBits[pnFirst[pnPos[i]]+k] = iPos+k;
        }
    }
    pMvcNew = Mvc_CoverRemap(pIset, pnBits, nBits);
    
    FREE( pnBits );
    return pMvcNew;
}

/**Function*************************************************************
  Synopsis    [Adjust the covers to a new variable map return a new cover.]
  Description [pnPos[i] tells the new position of current variable i]
  SideEffects []
  SeeAlso     []
***********************************************************************/
Cvr_Cover_t *
Cvr_CoverCreateAdjust  (
    Cvr_Cover_t *pCvr,
    Vm_VarMap_t *pVmNew,
    int         *pnPos)
{
    int  iVal, nVal;
    Cvr_Cover_t *pCvrNew;
    
    if (pCvr==NULL) return NULL;
    
    /* clone the information */
    pCvrNew = ALLOC( Cvr_Cover_t, 1 );
    pCvrNew->pVm = pVmNew;
    pCvrNew->pTree = NULL;
    
    nVal = Vm_VarMapReadValuesOutNum(pCvr->pVm);
    pCvrNew->ppCovers = ALLOC( Mvc_Cover_t *, nVal );
    
    for (iVal=0; iVal<nVal; ++iVal) {
        if (pCvr->ppCovers[iVal]) {
            pCvrNew->ppCovers[iVal] = Cvr_IsetAdjust (pCvr->ppCovers[iVal],pVmNew,pCvr->pVm,pnPos);
        }
        else {
            pCvrNew->ppCovers[iVal] = NULL;
        }
    }
    
    return pCvrNew;
}

/**Function*************************************************************
  Synopsis    [Create a new cover after permuting fanins of the node.]
  Description [This function create a new Cvr after the node's fanins
  have been permuted. The permutation array contains, for each new
  MV variable (i), its place in the old variable order of MV variables
  (pPermuteInv[i]).]
  SideEffects []
  SeeAlso     []
***********************************************************************/
Cvr_Cover_t *
Cvr_CoverCreatePermuted( 
    Cvr_Cover_t * pCvr, 
    int * pPermuteInv )
{
    Mvc_Cover_t * pCover;
    Mvc_Cover_t ** ppIsets;
	Vm_VarMap_t * pVm, * pVmNew;
    int nValues, nVarsIn, i, v;
    int * pValuesNew, * pValuesFirstNew;
    int * pValuesOld, * pValuesFirstOld;
    int * pBitPermute;

    // get the old MV var map
    pVm = Cvr_CoverReadVm( pCvr );
    // create the new permuted Vm
	pVmNew = Vm_VarMapCreatePermuted( pVm, pPermuteInv );
    
    // get the parameters
    // the number of inputs and the number of output values
    nVarsIn         = Vm_VarMapReadVarsInNum( pVm );
    nValues         = Vm_VarMapReadValuesOutNum( pVm );
    // the old value info
    pValuesOld      = Vm_VarMapReadValuesArray( pVm );
    pValuesFirstOld = Vm_VarMapReadValuesFirstArray( pVm );
    // the new value info
    pValuesNew      = Vm_VarMapReadValuesArray( pVmNew );
    pValuesFirstNew = Vm_VarMapReadValuesFirstArray( pVmNew );

    // get one of the old covers
    pCover = NULL;
    for ( i = 0; i < nValues; i++ )
        if ( pCvr->ppCovers[i] )
        {
            pCover = pCvr->ppCovers[i];
            break;
        }        

    // create the permutation of bits
    pBitPermute = ALLOC( int, pCover->nBits );
    // go through all variables of the new map
    for ( i = 0; i < nVarsIn; i++ )
        for ( v = 0; v < pValuesNew[i]; v++ )
        {
            // make sure that the number of values of old and new MV var is the same
            assert( pValuesNew[i] == pValuesOld[pPermuteInv[i]] );
            pBitPermute[ pValuesFirstNew[i] + v ] =
                pValuesFirstOld[pPermuteInv[i]] + v;
        }

    // create the new Cvr after permutation
    ppIsets = ALLOC( Mvc_Cover_t *, nValues );
    for ( i = 0; i < nValues; i++ )
        if ( pCvr->ppCovers[i] )
            ppIsets[i] = Mvc_CoverRemap( pCvr->ppCovers[i], pBitPermute, pCover->nBits );
        else
            ppIsets[i] = NULL;
    FREE( pBitPermute );
    // create and return the cover
    return Cvr_CoverCreate( pVmNew, ppIsets );
}


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

  Synopsis    [Counts the number of MV literals in the cover.]