mvrutils.c

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

    {
        pbIsetsRes[i][0] = NULL;
        pbIsetsRes[i][1] = b0;   Cudd_Ref( b0 );
    }

    // add the original i-sets to the corresponding cofactors of the res relations
    for ( v = 0; v < nTotalValues; v++ )
    {
        // skip the unused code
        if ( pValueAssign[v] == -1 )
            continue;
        // assign this i-set to all the res relations that have 1 in the code
        for ( i = 0; i < CodeWidth; i++ )
            if ( v & (1 << i) )
            {
                pbIsetsRes[i][1] = Cudd_bddOr( dd, bTemp = pbIsetsRes[i][1], pbIsetsInit[pValueAssign[v]] ); 
                Cudd_Ref( pbIsetsRes[i][1] );
                Cudd_RecursiveDeref( dd, bTemp );
            }
    }

    // derive the negative cofactors by complementing the positive
    for ( i = 0; i < CodeWidth; i++ )
    {
        pbIsetsRes[i][0] = Cudd_Not( pbIsetsRes[i][1] );
        Cudd_Ref( pbIsetsRes[i][0] );
    }

    // dereference the original i-sets
    Mvr_RelationCofactorsDeref( pMvrInit, pbIsetsInit, pVmInit->nVarsIn, nOutputValues );

    // create the resulting relations
    for ( i = 0; i < CodeWidth; i++ )
    {
        ppMvrsRes[i]       = Mvr_RelationAlloc();
        ppMvrsRes[i]->pMan = pMan;
        ppMvrsRes[i]->pVmx = pVmx;
        // create the relation from cofactors
        Mvr_RelationCofactorsDeriveRelation( ppMvrsRes[i], pbIsetsRes[i], pVmInit->nVarsIn, 2 );
        Mvr_RelationCofactorsDeref( ppMvrsRes[i], pbIsetsRes[i], pVmInit->nVarsIn, 2 );
    }
}


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

  Synopsis    [Creates relation of the decoder.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Mvr_Relation_t * Mvr_RelationCreateCollector( Mvr_Manager_t * pMan, Vmx_Manager_t * pManVmx, Vm_Manager_t * pManVm, int nValues, int DefValue )
{
    DdManager * dd = pMan->pDdLoc;
    Mvr_Relation_t * pMvr;
    Vm_VarMap_t * pVm;
    DdNode ** ppCodes;
    DdNode ** pbIsets;
    DdNode * bTemp;
    int * pValues;
    bool fDefIsUsed;
    int i, k;
    // create the variable map
    fDefIsUsed = (bool)(DefValue >= 0);
    pValues = ALLOC( int, nValues + 1 );
    for ( i = 0; i < nValues - fDefIsUsed; i++ )
        pValues[i] = 2;
    pValues[i] = nValues;
    pVm        = Vm_VarMapLookup( pManVm, nValues - fDefIsUsed, 1, pValues ); 
    pMvr       = Mvr_RelationAlloc();
    pMvr->pMan = pMan;
    pMvr->pVmx = Vmx_VarMapLookup( pManVmx, pVm, -1, NULL );
    FREE( pValues );

    // get storage for i-sets
    pbIsets = ALLOC( DdNode *, nValues );
    // get the input encoding cubes
    ppCodes = Vmx_VarMapEncodeMap( dd, pMvr->pVmx );

    // create the i-sets 
    k = 0;
    for ( i = 0; i < nValues; i++ )
        if ( i != DefValue )
        {
            pbIsets[i] = ppCodes[2*(k++) + 1];  Cudd_Ref( pbIsets[i] );
        }
        else
            pbIsets[i] = NULL;

    // get the default i-set
    if ( fDefIsUsed )
    {
        k = 0;
        assert( pbIsets[DefValue] == NULL );
        pbIsets[DefValue] = b1;  Cudd_Ref( b1 );
        for ( i = 0; i < nValues; i++ )
            if ( i != DefValue )
            {
                pbIsets[DefValue] = Cudd_bddAnd( dd, bTemp = pbIsets[DefValue], ppCodes[2*(k++)] ); 
                Cudd_Ref( pbIsets[DefValue] );
                Cudd_RecursiveDeref( dd, bTemp );
            }
    }
    // deref the cubes
    Vmx_VarMapEncodeDeref( dd, pMvr->pVmx, ppCodes );

    // create the relation from cofactors
    Mvr_RelationCofactorsDeriveRelation( pMvr, pbIsets, nValues - fDefIsUsed, nValues );
    Mvr_RelationCofactorsDeref( pMvr, pbIsets, nValues - fDefIsUsed, nValues );
    FREE( pbIsets );
    return pMvr;
}

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

  Synopsis    [Relation make minimum base.]

  Description [Creates the minimum base relation.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Mvr_Relation_t * Mvr_RelationCreateMinimumBase( Mvr_Relation_t * pMvr, int * pSuppMv )
{
    Mvr_Relation_t * pMvrNew;
    int * pVarTrans;
    Vm_VarMap_t * pVmOld, * pVmNew;
    int nVmOld, nVmNew;
    int nSuppNew, i;

    pMvrNew = Mvr_RelationAlloc();
    pMvrNew->pMan   = pMvr->pMan;
    pMvrNew->nBddNodes = pMvr->nBddNodes;
    pMvrNew->pVmx   = Vmx_VarMapCreateReduced( pMvr->pVmx, pSuppMv );
//Vmx_VarMapPrint( pMvr->pVmx );
//Vmx_VarMapPrint( pMvrNew->pVmx );

    // get the parameters
    pVmOld    = pMvr->pVmx->pVm;
    pVmNew    = pMvrNew->pVmx->pVm;
    nVmOld    = pVmOld->nVarsIn + pVmOld->nVarsOut;
    nVmNew    = pVmNew->nVarsIn + pVmNew->nVarsOut;

    // create the variable transition map, which shows where each of the 
    // currently present MV vars goes in the reduced relation
    pVarTrans = Vm_VarMapGetStorageArray1( pVmOld );
    nSuppNew  = 0;
    for ( i = 0; i < nVmOld; i++ )
        if ( pSuppMv[i] )
            pVarTrans[i] = nSuppNew++;
        else
            pVarTrans[i] = -1;
    assert( nSuppNew == nVmNew );

    pMvrNew->bRel = Mvr_RelationRemap( pMvr, pMvr->bRel, pMvr->pVmx, pMvrNew->pVmx, pVarTrans ); 
    Cudd_Ref( pMvrNew->bRel );
    return pMvrNew;
}


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

  Synopsis    [Derive the collapsed relation.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Mvr_Relation_t * Mvr_RelationCreateCollapsed( Mvr_Relation_t * pMvrN, Mvr_Relation_t * pMvrF, 
        Vm_VarMap_t * pVmNew, int * pTransMapNInv, int * pTransMapF )
{
    Mvr_Relation_t * pMvrNew;
    Vm_VarMap_t * pVmN, * pVmF;
    Vmx_VarMap_t * pVmxN, * pVmxF;
    DdManager * dd = pMvrN->pMan->pDdLoc;
    DdNode ** pbCofsN, ** pbCofsF;
    DdNode * bRelCol, * bComp, * bTemp;
    DdNode * bRelF;
    int nValuesF;
    int i;

    // get the maps
    pVmN  = Mvr_RelationReadVm( pMvrN );
    pVmF  = Mvr_RelationReadVm( pMvrF );
    pVmxN = Mvr_RelationReadVmx( pMvrN );
    pVmxF = Mvr_RelationReadVmx( pMvrF );
    nValuesF = Vm_VarMapReadValuesOutput( pVmF );
    
    // create the new relation
    pMvrNew = Mvr_RelationAlloc();
    pMvrNew->pMan = pMvrN->pMan;

    // create the variable map of the relation after collapsing 
    // by extending the variable map for the node (pNode) in such a way
    // the remapping of the BDD of the relation is not necessary
//Vmx_VarMapPrint( pVmxN );
//Vmx_VarMapPrint( pVmxF );
    pMvrNew->pVmx = Vmx_VarMapCreateExpanded( pVmxN, pVmNew, pTransMapNInv );
//Vmx_VarMapPrint( pMvrNew->pVmx );

    // resize the manager if necessary
    if ( dd->size < pMvrNew->pVmx->nBits )
    {
        for ( i = dd->size; i < pMvrNew->pVmx->nBits + 10; i++ )
            Cudd_bddIthVar( dd, i );
        Cudd_zddVarsFromBddVars( dd, 2 );
    }

    // remap the relation of the fanin (pFanin) to match the new map
    bRelF = Mvr_RelationRemap( pMvrF, pMvrF->bRel,  pVmxF, pMvrNew->pVmx, pTransMapF ); Cudd_Ref( bRelF );

    // get the i-sets of the remapped relation of pFanin
    // set the relation of pFanin into the new relation, to compute the cofactors
    pbCofsF = ALLOC( DdNode *, nValuesF );
    pMvrNew->bRel = bRelF;
    Mvr_RelationCofactorsDerive( pMvrNew, pbCofsF, pTransMapF[pVmF->nVarsIn], nValuesF );
    Cudd_RecursiveDeref( dd, bRelF );
    pMvrNew->bRel = NULL;


    // get the i-set of pNode
    // set the relation of pNode into the new relation, to compute the cofactors
    pbCofsN = ALLOC( DdNode *, nValuesF );
    pMvrNew->bRel = pMvrN->bRel;
    Mvr_RelationCofactorsDerive( pMvrNew, pbCofsN, pTransMapF[pVmF->nVarsIn], nValuesF );
    pMvrNew->bRel = NULL;

    // create the resulting relation
    bRelCol = b0;    Cudd_Ref( bRelCol );
    for ( i = 0; i < nValuesF; i++ )
    {
        bComp = Cudd_bddAnd( dd, pbCofsN[i], pbCofsF[i] );  Cudd_Ref( bComp );
        bRelCol = Cudd_bddOr( dd, bTemp = bRelCol, bComp );   Cudd_Ref( bRelCol );
        Cudd_RecursiveDeref( dd, bComp );
        Cudd_RecursiveDeref( dd, bTemp );
    }

    // deref the intermediate cofactors
    Mvr_RelationCofactorsDeref( pMvrNew, pbCofsN, pTransMapF[pVmF->nVarsIn], nValuesF );
    FREE( pbCofsN );
    Mvr_RelationCofactorsDeref( pMvrNew, pbCofsF, pTransMapF[pVmF->nVarsIn], nValuesF );
    FREE( pbCofsF );

    // set the new relation
    pMvrNew->bRel = bRelCol;  // comes referenced
    return pMvrNew;
}


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

  Synopsis    [Creates the relation with the permuted MV vars.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Mvr_Relation_t * Mvr_RelationCreatePermuted( Mvr_Relation_t * pMvr, int * pPermuteInv )
{
    Mvr_Relation_t * pMvrNew;
    pMvrNew = Mvr_RelationAlloc();
    // copy the relation
    pMvrNew->pMan   = pMvr->pMan;
    pMvrNew->nBddNodes = pMvr->nBddNodes;
    pMvrNew->bRel   = pMvr->bRel;      Cudd_Ref( pMvr->bRel );
    // get the new variable map
    pMvrNew->pVmx   = Vmx_VarMapCreatePermuted( pMvr->pVmx, pPermuteInv );
//Vmx_VarMapPrint( pMvr->pVmx );
//Vmx_VarMapPrint( pMvrNew->pVmx );
    return pMvrNew;
}


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

  Synopsis    [Derives the power of the given relation.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Mvr_Relation_t * Mvr_RelationCreatePower( Mvr_Relation_t * pMvr, int Degree )
{
    Mvr_Relation_t * pMvrRes;
    DdManager * dd = pMvr->pMan->pDdLoc;
    DdNode * bRelBase, * bRelShift, * bRelRes, * bTemp;
    int i;

    assert( Degree > 1 );

    // resize the manager if necessary
    if ( pMvr->pMan->pDdLoc->size < pMvr->pVmx->nBits * Degree )
    {
        for ( i = pMvr->pMan->pDdLoc->size; i < pMvr->pVmx->nBits * Degree + 10; i++ )
            Cudd_bddIthVar( dd, i );
        Cudd_zddVarsFromBddVars( dd, 2 );
    }

    // allocate the relation and create the power var maps
    pMvrRes = Mvr_RelationAlloc();
    pMvrRes->pMan = pMvr->pMan;
    pMvrRes->pVmx = Vmx_VarMapCreatePower( pMvr->pVmx, Degree );

    // create the new relation
    bRelBase = Extra_bddStretch( dd, pMvr->bRel, Degree );  Cudd_Ref( bRelBase );
    bRelRes  = bRelBase;   Cudd_Ref( bRelRes );
    for ( i = 1; i < Degree; i++ )
    {
        bRelShift = Extra_bddShift( dd, bRelBase, 0 );             Cudd_Ref( bRelShift );
        bRelRes   = Cudd_bddAnd( dd, bTemp = bRelRes, bRelShift ); Cudd_Ref( bRelRes );
        Cudd_RecursiveDeref( dd, bTemp );
        // update the base
        Cudd_RecursiveDeref( dd, bRelBase );
        bRelBase = bRelShift; // takes ref
    }
    Cudd_RecursiveDeref( dd, bRelBase );
    pMvrRes->bRel = bRelRes;  // takes ref
    return pMvrRes;
}

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

  Synopsis    [Derives the relation of the local function from the global MDD.]

  Description [The parameters are: the global BDD manager (ddGlo), the local 
  manager (ddLoc), the ext var map manager (pManVmx), the CI variable map (pVm),
  the MDD of the node in the global manager (ddGlo). and the number of values.
  This function computes the new variable map (pVmNew), the new extended variable
  map (pVmxNew), remaps the BDDs into the local manager and finally derives the
  relation (the return value).]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Mvr_Relation_t * Mvr_RelationCreateFromGlobal( DdManager * ddGlo, Mvr_Manager_t * pManMvr, 
        Vmx_Manager_t * pManVmx, Vm_VarMap_t * pVm, DdNode ** pbMdds, int nValues )
{
    DdManager * ddLoc = pManMvr->pDdLoc;
    Mvr_Relation_t * pMvr;
    DdNode ** pbMddsNew;
    Vm_VarMap_t * pVmNew;
    Vmx_VarMap_t * pVmxNew;
    int * pBitOrder;
    int nBitsOld, nBitsNew, i;

    // derive the new variable map
    pVmNew = Vm_VarMapCreateExtended( pVm, nValues );

    // get the number of bits in the new map
    nBitsOld = 0;
    for ( i = 0; i < pVm->nVarsIn; i++ )
        nBitsOld += Extra_Base2Log( pVm->pValues[i] );
    // get the ordering of bits in the extended variable map
    pBitOrder = ALLOC( int, ddGlo->size + nValues );
    for ( i = 0; i < nBitsOld; i++ )
        pBitOrder[i] = ddGlo->perm[i];
    // add the remaining bits for the last variable
    nBitsNew = nBitsOld + Extra_Base2Log( nValues );
    for ( i = nBitsOld; i < nBitsNew; i++ )
        pBitOrder[i] = i;
    // HERE THERE IS THE PROBLEM WITH THE MAPPING OF VARS IN THE dd MANAGER
    // IF THERE ARE MORE VARIABLES THAN nBits, IT WILL NOT WORK!!!


    // derive the new extended variable map
    pVmxNew = Vmx_VarMapLookup( pManVmx, pVmNew, nBitsNew, pBitOrder );
    FREE( pBitOrder );

    // extend the local manager if necessary
    if ( ddLoc->size < nBitsNew )
    {
        for ( i = ddLoc->size; i < nBitsNew + 10; i++ )
            Cudd_bddIthVar( ddLoc, i );
        Cudd_zddVarsFromBddVars( ddLoc, 2 );
    }

    // remap the i-sets into the local manager
    pbMddsNew = ALLOC( DdNode *, nValues );
    for ( i = 0; i < nValues; i++ )
    {
        pbMddsNew[i] = Extra_TransferPermute( ddGlo, ddLoc, pbMdds[i], ddGlo->perm );
        Cudd_Ref( pbMddsNew[i] );
    }

    // create the new relation
    pMvr = Mvr_RelationAlloc();
    pMvr->pMan = pManMvr;
    pMvr->pVmx = pVmxNew;

    // create the relation from i-sets
    Mvr_RelationCofactorsDeriveRelation( pMvr, pbMddsNew, pVmNew->nVarsIn, nValues );
    // deref the i-sets
    for ( i = 0; i < nValues; i++ )
        Cudd_RecursiveDeref( ddLoc, pbMddsNew[i] );
    FREE( pbMddsNew );

    return pMvr;
}


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

  Synopsis    [Remaps BEMDD from the old map to the new map.]

  Description [Takes a BEMDD of any function that depends on the old
  variable map (pMapOld) (this function can be an i-set or a relation itself). 
  Assuming that this BEMDD is expressed using the old variable map (pMapOld), 
  this procedure remaps it to the new variable map (pMapNew). Additional 
  information for the remapping is given in the array pVarTrans. For each 
  MV variable in the old var map, this array contains the corresponding 
  MV variable in the new var map.  Array pVarTrans may contain entry -1,
  if this variable is not used in the function to be remapped. Obviously, 
  the number of values in the corresponding pairs of MV variables (one
  from the old map, another from the new map) should be the same.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
DdNode * Mvr_RelationRemap( Mvr_Relation_t * pMvr, DdNode * bFunc,
    Vmx_VarMap_t * pVmxOld, Vmx_VarMap_t * pVmxNew, int * pVarTrans )
{
    DdManager * dd = pMvr->pMan->pDdLoc;
    DdNode * bRes;
    Vm_VarMap_t * pVmOld, * pVmNew;
    int nVmOld, v, b, index;
    int * pPermute, i;

    // get the parameters
    pVmOld = pVmxOld->pVm;
    pVmNew = pVmxNew->pVm;
    nVmOld = pVmOld->nVarsIn + pVmOld->nVarsOut;