pdpairdecode.c

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

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

  FileName    [pdPairDecode.c]

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

  Synopsis    [.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: pdPairDecode.c,v 1.11 2003/05/27 23:33:41 wjiang Exp $]

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

#include "pdInt.h"

static int _MinimizeValues( Ntk_Node_t * pDec );

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

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

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

  Synopsis    [.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Pd_PairDecode( Ntk_Network_t * pNet, int threshValue, int iCost, int resubOption, int timelimit, int fVerbose )
{
    Ntk_Node_t * pNode1, * pNode2, * a, * b, * pFanout;
    Ntk_Node_t * new_ab;
    Ntk_Pin_t * pin;
    int i, j, bestValue, value, changed;
    array_t *nodeVec;

    // we only handle two cost functions for now
    if ( iCost > 1 ) iCost = 1;
    if ( fVerbose )
        printf(" search starts\n");

    bestValue = -INFINITY;
    changed = 0;
    nodeVec = array_alloc( Ntk_Node_t *, 0 );

    // collect all nodes in network to nodeVec
    Ntk_NetworkForEachCi( pNet, pNode1 ) 
    {
        array_insert_last( Ntk_Node_t *, nodeVec, pNode1 );
    }
    Ntk_NetworkForEachNode( pNet, pNode1 ) 
    {
        array_insert_last( Ntk_Node_t *, nodeVec, pNode1 );
    }

    // search good pairs
    for ( i = 0; i < array_n(nodeVec); i++ ) 
    {
        pNode1 = array_fetch( Ntk_Node_t *, nodeVec, i );
        for ( j = i+1; j < array_n(nodeVec); j++ )
        {
            // timeout comes in
            if ( clock() > timelimit )
                break;
            pNode2 = array_fetch( Ntk_Node_t *, nodeVec, j );
            value = Pd_PairValue( pNode1, pNode2, iCost );
            // printf( "node1 %s node2 %s value %d\n", Ntk_NodeReadName( pNode1 ), Ntk_NodeReadName( pNode2 ), value );
    	    if( value > bestValue )
            {
    	        a = pNode1;
	            b = pNode2;
		        bestValue = value;
	        }   
	    }
        if ( clock() > timelimit )
            break;
    }
    array_free( nodeVec );

    // debug
    if ( fVerbose )
        printf(" search ends\n" );

    if ( bestValue >= threshValue ) 
    {	
	    // this function do the real pair work
    	new_ab = Pd_PairNodes_Simp( a, b );
        if ( new_ab ) 
        {
            changed = 1;
        	// to avoid infinite loop
            nodeVec = array_alloc( Ntk_Node_t *, 0 );
	        Ntk_NodeForEachFanout( new_ab, pin, pFanout ) 
            {
                array_insert_last( Ntk_Node_t *, nodeVec, pFanout );
            }
            for ( i=0; i<array_n( nodeVec ); i++ )
            {
                pFanout = array_fetch( Ntk_Node_t *, nodeVec, i );
	            Ntk_NodeMakeMinimumBase( pFanout );
            }
	        if ( Ntk_NodeReadFanoutNum(new_ab) == 0 )
	            changed = 0;
            array_free( nodeVec );
        }
        // verbose
        if ( changed && fVerbose )
            Ntk_NodePrintCvr( stdout, new_ab, 0, 0 );
    }    
    return changed;
}

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

  Synopsis       [calculate the saving of pairing a and b]

  Description    [The saving includes the changes in the fanouts of a and b. We 
  consider two options: create a new node with a and b as fanins, merge a and b.
  The one that leads to larger saving is taken.

  Variable 'merge' is set to 1 if we will merge a and b, 0 otherwise.]

  SideEffects    []

******************************************************************************/
int Pd_PairValue( Ntk_Node_t *p1, Ntk_Node_t *p2, int iCost ) 
{
    int i, j, v, index1, index2, value, nVal, nWords;
    int sameoutput, paired;
    Ntk_Node_t * fanout;
    pdst_table * cube_table;
    Cvr_Cover_t * pCvr;
    Ntk_Pin_t * pin1;
    Vm_VarMap_t *pVm;
    Mvc_Cover_t **tempppMvc;
    Mvc_Cube_t * pCube, * mask, * temp, * dummy;
    int nVarsIn, nValuesIn;
    int * pValues, iValues;
    bool fDontCare;
    int Counter, start1, start2;

    // check if p1 and p2 have same output. If not, no need to pair them
    sameoutput = 0;
    Ntk_NodeForEachFanout( p1, pin1, fanout ) 
    {
        index2 = Ntk_NodeReadFaninIndex( fanout, p2 );
        if ( index2 != -1 ) 
        {
	        sameoutput = 1;
	        break;
	    }
    }
    if( sameoutput == 0 ) {
        return -INFINITY;
    }

    // check if p1 and p2 are already paired
    // NOTE: if we don't check here, if thresh is given low enough, there will be permenent loop
    // if p1 and p2 has single fanout, which only has them as fanins, we do not pair them
    paired = 0;
    /*
    if ( (Ntk_NodeReadFanoutNum(p1) == 1) && (Ntk_NodeReadFanoutNum(p2) == 1) ) 
    {  
    */
        Ntk_NodeForEachFanout( p1, pin1, fanout )  
        {
	        if ( Ntk_NodeReadFaninNum( fanout ) == 2 && Ntk_NodeReadFaninIndex( fanout, p2 ) != -1 )
	            paired = 1;
	    }
    // }
    if( paired == 1 ) 
    {
        return -INFINITY;
    }     

    // The number of values no more than 32!!
    i = Ntk_NodeReadValueNum( p1 );
    j = Ntk_NodeReadValueNum( p2 );
    if ( i*j > 32 ) 
    {
        return -INFINITY;
    }
        
    /* value is the possible saving by pairing two nodes in the fanouts*/
    value = 0;
    Ntk_NodeForEachFanout( p1, pin1, fanout ) 
    {
        // added by Yunjian for data-path 
        if ( Ntk_NodeBelongsToLatch( fanout ) ) continue;
	    index2 = Ntk_NodeReadFaninIndex( fanout, p2 );
    	if( index2 == -1 )  continue;
	    index1 = Ntk_NodeReadFaninIndex( fanout, p1 );
        if ( index1 > index2 )
        {
            i = index1;
            index1 = index2;
            index2 = i;
        }
        pCvr = Ntk_NodeGetFuncCvr( fanout );
        pVm  = Ntk_NodeGetFuncVm( fanout );

 	    // set the values of p1 and p2 to be the same in all cubes 
        nVal = Vm_VarMapReadValuesOutNum( pVm );
        tempppMvc = Cvr_CoverReadIsets( pCvr );
        for ( i=0; i<nVal; i++ )
        {
            if ( tempppMvc[i] != NULL )
                break;
        }
        mask = Mvc_CubeAlloc( tempppMvc[i] );
        Mvc_CubeNBitClean( mask );
        nWords = Mvc_CoverReadWordNum( tempppMvc[i] );
        // get the var map parameters
        nVarsIn   = Vm_VarMapReadVarsInNum( pVm );
        nValuesIn = Vm_VarMapReadValuesInNum( pVm );
        pValues   = Vm_VarMapReadValuesArray( pVm );
        iValues = 0;
        for ( i=0; i<index1; i++ )
        {
            iValues += pValues[i];
        }
        start1 = iValues;
        for ( i=0; i<pValues[index1]; i++ )
        {
            Mvc_CubeBitInsert( mask, iValues + i );
        }
        for ( i=index1; i<index2; i++ )
        {
            iValues += pValues[i];
        }
        start2 = iValues;
        for ( i=0; i<pValues[index2]; i++ )
        {
            Mvc_CubeBitInsert( mask, iValues + i );
        }

        for ( i=0; i<nVal; i++ ) 
        {
            if ( tempppMvc[i]==NULL )
                continue;
            cube_table = pdst_init_table( pdst_cubecmp, pdst_cubehash );
            temp = Mvc_CubeAlloc( tempppMvc[i] );
            Mvc_CoverForEachCube( tempppMvc[i], pCube )
            {
                Mvc_CubeNBitOr( temp, pCube, mask );
                if ( !pdst_lookup( cube_table, temp, &dummy ) )
                {
                    if ( iCost == NTK_COST_LIT )
                    {
                        for ( j = 0; j < pValues[index1]; j++ )
                            if ( !Mvc_CubeBitValue( pCube, start1 + j ) )
                            {
                                for ( v = 0; v < pValues[index2]; v++ )
                                {
                                    if ( !Mvc_CubeBitValue( pCube, start2 + v ) )
                                    {
                                        value++;
                                        break;
                                    }
                                }
                                break;
                            }
                    }
                    pdst_insert( cube_table, temp, NIL(Mvc_Cube_t) );
                    temp = Mvc_CubeAlloc( tempppMvc[i] );
                }
                else 
                {
                    if ( iCost == NTK_COST_LIT )
                    {
                        // count the number of literals in pCube
                        Counter = 0;
                        iValues = 0;
                        for ( j=0; j<nVarsIn; j++ )
                        {
                            fDontCare = 1;
                            for ( v = 0; v < pValues[j]; v++ )
                                if ( !Mvc_CubeBitValue( pCube, iValues + v ) )
                                {
                                    fDontCare = 0;
                                    break;
                                }
                            if ( !fDontCare )
                                Counter++;
                            iValues += pValues[j];
                        }
                        value += Counter;
                    }
                    else
                        value++;
                }
            }
            pdst_free_table( cube_table );
            Mvc_CubeFree( tempppMvc[i], temp );
        }

        // memory free
        for ( i=0; i<nVal; i++ )
        {
            if ( tempppMvc[i] != NULL )