cbclub.c

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

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

  FileName    [cbClub.c]

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

  Synopsis    [clubbing utilities]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: cbClub.c,v 1.3 2003/05/27 23:14:44 alanmi Exp $]

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

#include "cb.h"

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

static long     Cb_GraphGetRootWeight( Cb_Graph_t *pClub );
static long     Cb_GraphGetLeafWeight( Cb_Graph_t *pClub );
static bool     Cb_ClubCheckRootsRemain( Cb_Graph_t *pClub, Cb_Vertex_t *pV);


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


/**Function*************************************************************
  Synopsis    []
  Description []
  SideEffects []
  SeeAlso     []
***********************************************************************/
void
Cb_ClubAddVertexToTail( Cb_Graph_t *pClub, Cb_Vertex_t *pV )
{
    if ( pClub->pVertexHead == NULL ) {
        
        pClub->pVertexHead = pClub->pVertexTail = pV;
        pV->pNextClub = NULL;
    }
    else {
        
        pClub->pVertexTail->pNextClub = pV;
        pV->pNextClub = NULL;
        pClub->pVertexTail = pV;
    }
    
    pClub->nVertices++;
    
    return;
}

/**Function*************************************************************
  Synopsis    [remove vertex from club list]
  Description []
  SideEffects []
  SeeAlso     []
***********************************************************************/
void
Cb_ClubRemoveVertexFromList( Cb_Graph_t *pClub, Cb_Vertex_t *pV )
{
    Cb_Vertex_t *pPrev, *pSpec;
    
    /* check head */
    if ( pClub->pVertexHead == pV ) {
        
        pClub->pVertexHead = pV->pNextClub;
    }
    /* iterate through the list */
    else {
        
        pPrev = pClub->pVertexHead;
        pSpec = pPrev->pNextClub;
        while ( pSpec ) {
            if ( pSpec == pV ) {
                pPrev->pNextClub = pV->pNextClub;
                break;
            }
            pPrev = pSpec;
            pSpec = pSpec->pNextClub;
        }
    }
    pClub->nVertices--;
    return;
}


/**Function*************************************************************
  Synopsis    []
  Description [return true if a vertex can be included into a club according
  to the option specified.]
  SideEffects []
  SeeAlso     []
***********************************************************************/
bool
Cb_ClubCheckInclusion( Cb_Option_t *pOpt, Cb_Graph_t *pClub, Cb_Vertex_t *pSpecial )
{
    int          nCost;
    Cb_Vertex_t *pV;
    
    /* special case */
    if ( pClub->nVertices == 0 )
        return TRUE;
    
    /* limit in the size of the root domain */
    if ( Cb_ClubCheckVertexRoot( pClub, pSpecial ) &&
         Cb_GraphGetRootWeight( pClub ) >= (1<<pOpt->nMaxOut) )
        return FALSE;
    
    /* limit in the size of the leaf domain */
    if ( Cb_ClubCheckVertexLeaf( pClub, pSpecial ) &&
         Cb_GraphGetLeafWeight( pClub ) >= (1<<pOpt->nMaxIn) )
        return FALSE;
    
    /* disallow merging of graph root nodes (PO) */
    if ( !Cb_ClubCheckInclusionGraphRoot( pClub, pSpecial ) )
       return FALSE;
    
    /* limit in the amount of logic/area */
    nCost = 0;
    Cb_GraphForEachVertexClub( pClub, pV )
    {
        nCost += (int) pV->pData2;
    }
    if ( nCost > pOpt->nCost )
        return FALSE;
    
    /* no cycle is allowed */
    if ( Cb_ClubCheckVertexCyclic( pClub, pSpecial ) )
        return FALSE;
    
    return TRUE;
}


/**Function*************************************************************
  Synopsis    [check if the inclusion will result in merging a PO]
  Description [return TRUE if the inclusion is OK.]
  SideEffects []
  SeeAlso     []
***********************************************************************/
bool
Cb_ClubCheckInclusionGraphRoot( Cb_Graph_t *pClub, Cb_Vertex_t *pSpecial ) 
{
    int i;
    Cb_Vertex_t * pV;
    
    /* if new node is a root, check PO presence of current roots */
    if ( Cb_ClubCheckVertexRoot( pClub, pSpecial ) ) {
        
        for ( i = 0; i < sarray_n(pClub->pRoots); ++i ) {
            
            pV = sarray_fetch( Cb_Vertex_t *, pClub->pRoots, i );
            if ( Cb_VertexIsGraphRootFanin( pV ) )  /* PO */
                return FALSE;
        }
    }
    
    /* if new node is a PO, check remainess of current roots */
    if ( Cb_VertexIsGraphRootFanin( pSpecial ) ) {
        
        if ( Cb_ClubCheckRootsRemain( pClub, pSpecial ) )
            return FALSE;
    }
    
    return TRUE;
}


/**Function*************************************************************
  Synopsis    []
  Description [insert a vertex into a club; update its roots and leaves;
  if fAdjustBound flag is TRUE, and also check if the roots(leaves) are
  real.]
  
  SideEffects []
  SeeAlso     []
***********************************************************************/
void
Cb_ClubInclude( Cb_Graph_t *pClub, Cb_Vertex_t *pV, bool fAdjustBound ) 
{
    Cb_ClubAddVertexToTail( pClub, pV );
    
    if ( Cb_ClubCheckVertexRoot( pClub, pV ) )
        Cb_GraphAddRoot( pClub, pV );
    
    if ( Cb_ClubCheckVertexLeaf( pClub, pV ) )
        Cb_GraphAddLeaf( pClub, pV );
    
    /* old roots/leaves may no longer be roots/leaves */
    if ( fAdjustBound )
        Cb_ClubImposeBoundary( pClub );
    
    //assert( !Cb_ClubCheckGraphRootMerged( pClub ) );
    
    return;
}


/**Function*************************************************************
  Synopsis    []
  Description [remove a vertex from a club; update its roots and leaves;
  if fAdjustBound flag is TRUE, and also check if other vertices migh
  be exposed as boundaries.]
  
  SideEffects []
  SeeAlso     []
***********************************************************************/
void
Cb_ClubExclude( Cb_Graph_t *pClub, Cb_Vertex_t *pV, bool fAdjustBound ) 
{
    int  i;
    Cb_Vertex_t *pSpec;
    
    /* remove the vertex from club list */
    Cb_ClubRemoveVertexFromList( pClub, pV );
    
    /* remove from the root list */
    sarrayForEachItem( Cb_Vertex_t *, pClub->pRoots, i, pSpec ) {
        
        if ( pSpec == pV ) {
            sarray_insert( Cb_Vertex_t *, pClub->pRoots, i, NULL );
            sarray_compact( pClub->pRoots );
            break;
        }
    }
    
    /* remove from the leaf list */
    sarrayForEachItem( Cb_Vertex_t *, pClub->pLeaves, i, pSpec ) {
        
        if ( pSpec == pV ) {
            sarray_insert( Cb_Vertex_t *, pClub->pLeaves, i, NULL );
            sarray_compact( pClub->pLeaves );
            break;
        }
    }
    
    /* removed roots/leaves may expose new roots/leaves */
    if ( fAdjustBound )
        Cb_ClubExposeBoundary( pClub );
    
    return;
}


/**Function*************************************************************
  Synopsis    [adjust the roots and leaves of a club]
  Description [assume all roots(leaves) are present in the roots(leaves)
  array, and possibly others. iterates through the arrays and remove
  the ones that do not qualify. ]
  
  SideEffects []
  SeeAlso     []
***********************************************************************/
void
Cb_ClubImposeBoundary( Cb_Graph_t *pClub ) 
{
    int i, k;
    Cb_Vertex_t  *pV;
    
    /* first mark all vertices inside */
    Cb_GraphForEachVertexClub( pClub, pV ) {
        
        Cb_VertexSetFlag1( pV );
    }
    
    /* remove fake roots */
    for ( i = 0; i < sarray_n( pClub->pRoots ); ++i ) {
        
        pV = sarray_fetch( Cb_Vertex_t *, pClub->pRoots, i );
        for ( k = 0; k < pV->nOut; ++k ) {
            
            if ( !Cb_VertexTestFlag1( pV->pOut[k] ) )
                break;
        }
        /* check if all fanouts are inside */
        if ( k == pV->nOut ) {
            
            sarray_insert( Cb_Vertex_t *, pClub->pRoots, i, NULL );
        }
    }
    sarray_compact( pClub->pRoots );
    
    /* remove fake leaves */
    for ( i = 0; i < sarray_n( pClub->pLeaves ); ++i ) {
        
        pV = sarray_fetch( Cb_Vertex_t *, pClub->pLeaves, i );
        for ( k = 0; k < pV->nIn; ++k ) {
            
            if ( !Cb_VertexTestFlag1( pV->pIn[k] ) )
                break;
        }
        /* check if all fanouts are inside */
        if ( k == pV->nIn ) {
            
            sarray_insert( Cb_Vertex_t *, pClub->pLeaves, i, NULL );
        }
    }
    sarray_compact( pClub->pLeaves );
    
    
    /* remove marks */
    Cb_GraphForEachVertexClub( pClub, pV ) {
        Cb_VertexResetFlag1( pV );
    }
    
    return;
}


/**Function*************************************************************
  Synopsis    [adjust the roots and leaves of a club]
  Description [assume all roots(leaves) are present in the roots(leaves)
  array and no more. iterate through all vertices, and if it happen to
  be a boundary node but not present in the root/leaf array, then expose
  it in the boundary.]
  
  SideEffects []
  SeeAlso     []
***********************************************************************/
void
Cb_ClubExposeBoundary( Cb_Graph_t *pClub ) 
{
    int i, k;
    Cb_Vertex_t  *pV;
    
    /* first mark all vertices inside */
    Cb_GraphForEachVertexClub( pClub, pV ) {
        Cb_VertexSetFlag1( pV );
    }
    
    /* mark roots */
    sarrayForEachItem( Cb_Vertex_t *, pClub->pRoots, i, pV ) {
        Cb_VertexSetFlag2( pV );
    }
    /* add hiden roots */
    Cb_GraphForEachVertexClub( pClub, pV ) {
        
        /* this is already a root */
        if ( Cb_VertexTestFlag2( pV ) )
            continue;
        
        for ( k = 0; k < pV->nOut; ++k ) {
            if ( !Cb_VertexTestFlag1( pV->pOut[k] ) )
                break;
        }
        /* check if all fanouts are inside */
        if ( k < pV->nOut ) {
            sarray_insert_last_safe( Cb_Vertex_t *, pClub->pRoots, pV );
        }
    }
    /* remove root marks */
    sarrayForEachItem( Cb_Vertex_t *, pClub->pRoots, i, pV ) {
        Cb_VertexResetFlag2( pV );
    }
    
    
    /* mark leaves */
    sarrayForEachItem( Cb_Vertex_t *, pClub->pLeaves, i, pV ) {
        Cb_VertexSetFlag2( pV );
    }
    /* add hiden leaves */
    Cb_GraphForEachVertexClub( pClub, pV ) {
        
        /* this is already a leaf */
        if ( Cb_VertexTestFlag2( pV ) )
            continue;
        
        for ( k = 0; k < pV->nIn; ++k ) {
            if ( !Cb_VertexTestFlag1( pV->pIn[k] ) )
                break;
        }
        /* check if all fanins are inside */
        if ( k < pV->nIn ) {
            sarray_insert_last_safe( Cb_Vertex_t *, pClub->pLeaves, pV );
        }
    }