fxuupdate.c

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

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

  FileName    [fxuUpdate.c]

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

  Synopsis    [Updating the sparse matrix when divisors are accepted.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: fxuUpdate.c,v 1.6 2003/05/27 23:16:00 alanmi Exp $]

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

#include "fxuInt.h"

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

static void Fxu_UpdateDoublePairs( Fxu_Matrix * p, Fxu_Double * pDouble, Fxu_Var * pVar );
static void Fxu_UpdateMatrixDoubleCreateCubes( Fxu_Matrix * p, Fxu_Cube * pCube1, Fxu_Cube * pCube2, Fxu_Double * pDiv );
static void Fxu_UpdateMatrixDoubleClean( Fxu_Matrix * p, Fxu_Cube * pCubeUse, Fxu_Cube * pCubeRem );
static void Fxu_UpdateMatrixSingleClean( Fxu_Matrix * p, Fxu_Var * pVar1, Fxu_Var * pVar2, Fxu_Var * pVarNew );

static void Fxu_UpdateCreateNewVars( Fxu_Matrix * p, Fxu_Var ** ppVarC, Fxu_Var ** ppVarD, int nCubes );
static int  Fxu_UpdatePairCompare( Fxu_Pair ** ppP1, Fxu_Pair ** ppP2 );
static void Fxu_UpdatePairsSort( Fxu_Matrix * p, Fxu_Double * pDouble );

static void Fxu_UpdateCleanOldDoubles( Fxu_Matrix * p, Fxu_Double * pDiv, Fxu_Cube * pCube );
static void Fxu_UpdateAddNewDoubles( Fxu_Matrix * p, Fxu_Cube * pCube );
static void Fxu_UpdateCleanOldSingles( Fxu_Matrix * p );
static void Fxu_UpdateAddNewSingles( Fxu_Matrix * p, Fxu_Var * pVar );

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

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

  Synopsis    [Updates the matrix after selecting two divisors.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fxu_Update( Fxu_Matrix * p, Fxu_Single * pSingle, Fxu_Double * pDouble )
{
	Fxu_Cube * pCube, * pCubeNew;
	Fxu_Var * pVarC, * pVarD;
	Fxu_Var * pVar1, * pVar2;

    // consider trivial cases
    if ( pSingle == NULL )
    {
        assert( pDouble->Weight == Fxu_HeapDoubleReadMaxWeight( p->pHeapDouble ) );
        Fxu_UpdateDouble( p );
        return;
    }
    if ( pDouble == NULL )
    {
        assert( pSingle->Weight == Fxu_HeapSingleReadMaxWeight( p->pHeapSingle ) );
        Fxu_UpdateSingle( p );
        return;
    }

    // get the variables of the single
    pVar1 = pSingle->pVar1;
    pVar2 = pSingle->pVar2;

    // remove the best double from the heap
    Fxu_HeapDoubleDelete( p->pHeapDouble, pDouble );
	// remove the best divisor from the table
	Fxu_ListTableDelDivisor( p, pDouble );

    // create two new columns (vars)
    Fxu_UpdateCreateNewVars( p, &pVarC, &pVarD, 1 );
    // create one new row (cube)
    pCubeNew = Fxu_MatrixAddCube( p, pVarD, 0 );
    pCubeNew->pFirst = pCubeNew;
    // set the first cube of the positive var
    pVarD->pFirst = pCubeNew;

    // start collecting the affected vars and cubes
    Fxu_MatrixRingCubesStart( p );
    Fxu_MatrixRingVarsStart( p );
    // add the vars
    Fxu_MatrixRingVarsAdd( p, pVar1 );
    Fxu_MatrixRingVarsAdd( p, pVar2 );
    // remove the literals and collect the affected cubes
    // remove the divisors associated with this cube
   	// add to the affected cube the literal corresponding to the new column
	Fxu_UpdateMatrixSingleClean( p, pVar1, pVar2, pVarD );
	// replace each two cubes of the pair by one new cube
	// the new cube contains the base and the new literal
    Fxu_UpdateDoublePairs( p, pDouble, pVarC );
    // stop collecting the affected vars and cubes
    Fxu_MatrixRingCubesStop( p );
    Fxu_MatrixRingVarsStop( p );

    // add the literals to the new cube
    assert( pVar1->iVar < pVar2->iVar );
    assert( Fxu_SingleCountCoincidence( p, pVar1, pVar2 ) == 0 );
    Fxu_MatrixAddLiteral( p, pCubeNew, pVar1 );
    Fxu_MatrixAddLiteral( p, pCubeNew, pVar2 );

    // create new doubles; we cannot add them in the same loop
	// because we first have to create *all* new cubes for each node
    Fxu_MatrixForEachCubeInRing( p, pCube )
   		Fxu_UpdateAddNewDoubles( p, pCube );
    // update the singles after removing some literals
    Fxu_UpdateCleanOldSingles( p );

    // undo the temporary rings with cubes and vars
    Fxu_MatrixRingCubesUnmark( p );
    Fxu_MatrixRingVarsUnmark( p );
    // we should undo the rings before creating new singles

    // create new singles
    Fxu_UpdateAddNewSingles( p, pVarC );
    Fxu_UpdateAddNewSingles( p, pVarD );

	// recycle the divisor
	MEM_FREE_FXU( p, Fxu_Double, 1, pDouble );
	p->nDivs3++;
}

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

  Synopsis    [Updates after accepting single cube divisor.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fxu_UpdateSingle( Fxu_Matrix * p )
{
    Fxu_Single * pSingle;
	Fxu_Cube * pCube, * pCubeNew;
	Fxu_Var * pVarC, * pVarD;
	Fxu_Var * pVar1, * pVar2;

    // read the best divisor from the heap
    pSingle = Fxu_HeapSingleReadMax( p->pHeapSingle );
    // get the variables of this single-cube divisor
    pVar1 = pSingle->pVar1;
    pVar2 = pSingle->pVar2;

    // create two new columns (vars)
    Fxu_UpdateCreateNewVars( p, &pVarC, &pVarD, 1 );
    // create one new row (cube)
    pCubeNew = Fxu_MatrixAddCube( p, pVarD, 0 );
    pCubeNew->pFirst = pCubeNew;
    // set the first cube
    pVarD->pFirst = pCubeNew;

    // start collecting the affected vars and cubes
    Fxu_MatrixRingCubesStart( p );
    Fxu_MatrixRingVarsStart( p );
    // add the vars
    Fxu_MatrixRingVarsAdd( p, pVar1 );
    Fxu_MatrixRingVarsAdd( p, pVar2 );
    // remove the literals and collect the affected cubes
    // remove the divisors associated with this cube
   	// add to the affected cube the literal corresponding to the new column
	Fxu_UpdateMatrixSingleClean( p, pVar1, pVar2, pVarD );
    // stop collecting the affected vars and cubes
    Fxu_MatrixRingCubesStop( p );
    Fxu_MatrixRingVarsStop( p );

    // add the literals to the new cube
    assert( pVar1->iVar < pVar2->iVar );
    assert( Fxu_SingleCountCoincidence( p, pVar1, pVar2 ) == 0 );
    Fxu_MatrixAddLiteral( p, pCubeNew, pVar1 );
    Fxu_MatrixAddLiteral( p, pCubeNew, pVar2 );

    // create new doubles; we cannot add them in the same loop
	// because we first have to create *all* new cubes for each node
    Fxu_MatrixForEachCubeInRing( p, pCube )
   		Fxu_UpdateAddNewDoubles( p, pCube );
    // update the singles after removing some literals
    Fxu_UpdateCleanOldSingles( p );
    // we should undo the rings before creating new singles

    // unmark the cubes
    Fxu_MatrixRingCubesUnmark( p );
    Fxu_MatrixRingVarsUnmark( p );

    // create new singles
    Fxu_UpdateAddNewSingles( p, pVarC );
    Fxu_UpdateAddNewSingles( p, pVarD );
	p->nDivs1++;
}

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

  Synopsis    [Updates the matrix after accepting a double cube divisor.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fxu_UpdateDouble( Fxu_Matrix * p )
{
    Fxu_Double * pDiv;
	Fxu_Cube * pCube, * pCubeNew1, * pCubeNew2;
	Fxu_Var * pVarC, * pVarD;

    // remove the best divisor from the heap
    pDiv = Fxu_HeapDoubleGetMax( p->pHeapDouble );
	// remove the best divisor from the table
	Fxu_ListTableDelDivisor( p, pDiv );

    // create two new columns (vars)
    Fxu_UpdateCreateNewVars( p, &pVarC, &pVarD, 2 );
    // create two new rows (cubes)
    pCubeNew1 = Fxu_MatrixAddCube( p, pVarD, 0 );
    pCubeNew1->pFirst = pCubeNew1;
    pCubeNew2 = Fxu_MatrixAddCube( p, pVarD, 1 );
    pCubeNew2->pFirst = pCubeNew1;
    // set the first cube
    pVarD->pFirst = pCubeNew1;

    // add the literals to the new cubes
    Fxu_UpdateMatrixDoubleCreateCubes( p, pCubeNew1, pCubeNew2, pDiv );

    // start collecting the affected cubes and vars
    Fxu_MatrixRingCubesStart( p );
    Fxu_MatrixRingVarsStart( p );
	// replace each two cubes of the pair by one new cube
	// the new cube contains the base and the new literal
    Fxu_UpdateDoublePairs( p, pDiv, pVarD );
    // stop collecting the affected cubes and vars
    Fxu_MatrixRingCubesStop( p );
    Fxu_MatrixRingVarsStop( p );
    
    // create new doubles; we cannot add them in the same loop
	// because we first have to create *all* new cubes for each node
    Fxu_MatrixForEachCubeInRing( p, pCube )
   		Fxu_UpdateAddNewDoubles( p, pCube );
    // update the singles after removing some literals
    Fxu_UpdateCleanOldSingles( p );

    // undo the temporary rings with cubes and vars
    Fxu_MatrixRingCubesUnmark( p );
    Fxu_MatrixRingVarsUnmark( p );
    // we should undo the rings before creating new singles

    // create new singles
    Fxu_UpdateAddNewSingles( p, pVarC );
    Fxu_UpdateAddNewSingles( p, pVarD );

    // recycle the divisor
	MEM_FREE_FXU( p, Fxu_Double, 1, pDiv );
	p->nDivs2++;
}

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

  Synopsis    [Update the pairs.]

  Description []

  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fxu_UpdateDoublePairs( Fxu_Matrix * p, Fxu_Double * pDouble, Fxu_Var * pVar )
{
    Fxu_Pair * pPair;
    Fxu_Cube * pCubeUse, * pCubeRem;
    int i;

    // collect and sort the pairs
    Fxu_UpdatePairsSort( p, pDouble );
    for ( i = 0; i < p->nPairsTemp; i++ )
    {
        // get the pair
        pPair = p->pPairsTemp[i];
	    // out of the two cubes, select the one which comes earlier
	    pCubeUse = Fxu_PairMinCube( pPair );
	    pCubeRem = Fxu_PairMaxCube( pPair );
        // collect the affected cube
        assert( pCubeUse->pOrder == NULL );
        Fxu_MatrixRingCubesAdd( p, pCubeUse );

	    // remove some literals from pCubeUse and all literals from pCubeRem
	    Fxu_UpdateMatrixDoubleClean( p, pCubeUse, pCubeRem );
	    // add a literal that depends on the new variable
	    Fxu_MatrixAddLiteral( p, pCubeUse, pVar );	
        // check the literal count
        assert( pCubeUse->lLits.nItems == pPair->nBase + 1 );
        assert( pCubeRem->lLits.nItems == 0 );

	    // update the divisors by removing useless pairs
	    Fxu_UpdateCleanOldDoubles( p, pDouble, pCubeUse );
	    Fxu_UpdateCleanOldDoubles( p, pDouble, pCubeRem );
	    // remove the pair
	    MEM_FREE_FXU( p, Fxu_Pair, 1, pPair );
    }
    p->nPairsTemp = 0;
}

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

  Synopsis    [Add two cubes corresponding to the given double-cube divisor.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fxu_UpdateMatrixDoubleCreateCubes( Fxu_Matrix * p, Fxu_Cube * pCube1, Fxu_Cube * pCube2, Fxu_Double * pDiv )
{
	Fxu_Lit * pLit1, * pLit2;
    Fxu_Pair * pPair;
	int nBase, nLits1, nLits2;

	// fill in the SOP and copy the fanins
	nBase = nLits1 = nLits2 = 0;
	pPair = pDiv->lPairs.pHead;
	pLit1 = pPair->pCube1->lLits.pHead;
	pLit2 = pPair->pCube2->lLits.pHead;
	while ( 1 )
	{
		if ( pLit1 && pLit2 )
		{
			if ( pLit1->iVar == pLit2->iVar )
			{ // skip the cube free part
				pLit1 = pLit1->pHNext;
				pLit2 = pLit2->pHNext;
                nBase++;
			}
			else if ( pLit1->iVar < pLit2->iVar )
			{	// add literal to the first cube
                Fxu_MatrixAddLiteral( p, pCube1, pLit1->pVar );
				// move to the next literal in this cube
				pLit1 = pLit1->pHNext;
                nLits1++;
			}
			else
			{	// add literal to the second cube
                Fxu_MatrixAddLiteral( p, pCube2, pLit2->pVar );
				// move to the next literal in this cube
				pLit2 = pLit2->pHNext;
                nLits2++;
			}
		}
		else if ( pLit1 && !pLit2 )
		{	// add literal to the first cube
            Fxu_MatrixAddLiteral( p, pCube1, pLit1->pVar );
			// move to the next literal in this cube
			pLit1 = pLit1->pHNext;
            nLits1++;
		}
		else if ( !pLit1 && pLit2 )
		{	// add literal to the second cube
            Fxu_MatrixAddLiteral( p, pCube2, pLit2->pVar );
			// move to the next literal in this cube
			pLit2 = pLit2->pHNext;
            nLits2++;
		}
		else
			break;
	}
	assert( pPair->nLits1 == nLits1 );
	assert( pPair->nLits2 == nLits2 );
	assert( pPair->nBase == nBase );
}


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

  Synopsis    [Create the node equal to double-cube divisor.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fxu_UpdateMatrixDoubleClean( Fxu_Matrix * p, Fxu_Cube * pCubeUse, Fxu_Cube * pCubeRem )
{
	Fxu_Lit * pLit1, * bLit1Next;