cbclub.c

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

    /* remove leaf marks */
    sarrayForEachItem( Cb_Vertex_t *, pClub->pLeaves, i, pV ) {
        Cb_VertexResetFlag2( pV );
    }
    
    
    /* remove marks */
    Cb_GraphForEachVertexClub( pClub, pV ) {
        Cb_VertexResetFlag1( pV );
    }
    
    return;
}


/**Function*************************************************************
  Synopsis    []
  
  Description [expand a club towards fanout direction; the newly included node
  should not have outside fanins whose level is larger than the current one.
  The expanded node (to be included) should not have a level that is greater
  than the current one by 2; otherwise a cycle is likely to result.]
  
  SideEffects []
  SeeAlso     []
***********************************************************************/
void
Cb_ClubExpandFanout( Cb_Option_t *pOpt, Cb_Graph_t *pG,
                     Cb_Graph_t *pClub, int iLevel )
{
    int i, k, iRoot, nInside;
    Cb_Vertex_t *pV, *pRoot, *pFanout;
    sarray_t    *listCand;
    
    if ( pClub->nVertices == 0 )
        return;
    
    /* first mark all vertices inside */
    Cb_GraphForEachVertexClub( pClub, pV ) {
        Cb_VertexSetFlag1( pV );
    }
    
    listCand = sarray_alloc( Cb_Vertex_t *, Cb_GraphReadRootsNum(pClub) );
    
    /* visit fanout's of roots (with marking) */
    sarrayForEachItem( Cb_Vertex_t *, pClub->pRoots, iRoot, pRoot ) {
        
        /* do not expand graph roots */
        if ( Cb_VertexIsGraphRootFanin( pRoot ) )
            continue;
        
        for ( i=0; i < pRoot->nOut; ++i ) {
            
            /* either inside the club or have been considered */
            if ( Cb_VertexTestFlag1( pRoot->pOut[i] ) ||
                 Cb_VertexTestFlag2( pRoot->pOut[i] ))
                continue;
            
            /* do not consider special CO vertex */
            if ( pRoot->pOut[i]->iTravs == pG->iTravs ||
                 pRoot->pOut[i]->nOut == 0 )
                continue;
            
            pFanout = pRoot->pOut[i];
            Cb_VertexSetFlag2( pFanout );
            
            /* find benefitial ones */
            nInside = 0;
            for ( k=0; k < pFanout->nIn; ++k ) {
                
                /* accross too many levels, no good */
                if ( pFanout->pIn[k]->iLevel > iLevel ) {
                    nInside = -2;
                    break;
                }
                /* if ( pFanout->pIn[k]->iTravs == pG->iTravs ) */
                if ( Cb_VertexTestFlag1( pFanout->pIn[k] ) )
                    nInside++;
            }
            /* all fanins should fall inside (conservative) */
            if ( (pFanout->nIn - nInside) < 1 ) {
                
                /* insert into candidate list */
                sarray_insert_last_safe( Cb_Vertex_t *, listCand, pFanout );
            }
        }
    }
    
    /* remove all marks */
    sarrayForEachItem( Cb_Vertex_t *, pClub->pRoots, iRoot, pRoot ) {
        for ( i=0; i < pRoot->nOut; ++i ) {
            Cb_VertexResetFlag2( pRoot->pOut[i] );
        }
    }
    Cb_GraphForEachVertexClub( pClub, pV ) {
        Cb_VertexResetFlag1( pV );
    }
    
    /* after marks have been removed, check inclusion of candidates
       (TODO) the order of the candidates is important; should alway try
       the best one first! (create a heap with its sharing amount)
     */
    sarrayForEachItem( Cb_Vertex_t *, listCand, i, pFanout ) {
        
        if ( Cb_ClubCheckInclusion( pOpt, pClub, pFanout ) ) {
            
            Cb_ClubInclude( pClub, pFanout, 1 );
            pFanout->iTravs = pG->iTravs;
        }
    }
    
    sarray_free( listCand );
}

/**Function*************************************************************
  Synopsis    []
  Description [return true if one of pSpecial's fanout is not in club]
  SideEffects [clear the flags of pSpecial's fanouts]
  SeeAlso     []
***********************************************************************/
bool
Cb_ClubCheckVertexRoot( Cb_Graph_t *pClub, Cb_Vertex_t *pSpecial )
{
    int          i, nFound;
    Cb_Vertex_t *pV;
    
    if ( pSpecial->nOut == 0 )
        return TRUE;
    
    /* marked the fanouts of pSpecial */
    for ( i=0; i < pSpecial->nOut; ++i ) {
        Cb_VertexSetFlag1( pSpecial->pOut[i] );
    }
    
    /* the number of found fanout's */
    nFound = 0;
    Cb_GraphForEachVertexClub( pClub, pV ) {
        if ( Cb_VertexTestFlag1( pV ) ) {
            nFound++;
        }
    }
    
    /* remove marking */
    for ( i=0; i < pSpecial->nOut; ++i ) {
        Cb_VertexResetFlag1( pSpecial->pOut[i] );
    }
    
    return ( nFound != pSpecial->nOut );
}

/**Function*************************************************************
  Synopsis    []
  Description [return true if one of pSpecial's fanin is not in club]
  SideEffects [clear the flags of pSpecial's fanins]
  SeeAlso     []
***********************************************************************/
bool
Cb_ClubCheckVertexLeaf( Cb_Graph_t *pClub, Cb_Vertex_t *pSpecial )
{
    int          i, nFound;
    Cb_Vertex_t *pV;
    
    if ( pSpecial->nIn == 0 )
        return TRUE;
        
    /* marked the fanouts of pSpecial */
    for ( i=0; i < pSpecial->nIn; ++i ) {
        Cb_VertexSetFlag1( pSpecial->pIn[i] );
    }
    
    /* the number of found fanin's */
    nFound = 0;
    Cb_GraphForEachVertexClub( pClub, pV ) {
        if ( Cb_VertexTestFlag1( pV ) ) {
            nFound++;
        }
    }
    
    /* remove marking */
    for ( i=0; i < pSpecial->nIn; ++i ) {
        Cb_VertexResetFlag1( pSpecial->pIn[i] );
    }
    
    return ( nFound != pSpecial->nIn );
}

/**Function*************************************************************
  Synopsis    []
  Description []
  SideEffects []
  SeeAlso     []
***********************************************************************/
bool
Cb_ClubCheckVertexCyclic( Cb_Graph_t *pClub, Cb_Vertex_t *pSpecial )
{
    /* can be skipped since we expand with limit on the level */
    return FALSE;
}

/**Function*************************************************************
  Synopsis    []
  Description [return 1 if club has multiple roots including a PO fanin.
  This will result the PO fanin be merged with other nodes, which is
  undesirable.]
  
  SideEffects []
  SeeAlso     []
***********************************************************************/
bool
Cb_ClubCheckGraphRootMerged( Cb_Graph_t *pClub ) 
{
    int i;
    Cb_Vertex_t * pV;
    
    /* single root club has no problem */
    if ( sarray_n( pClub->pRoots ) == 1 )
        return FALSE;
    
    /* check if roots contain a PO */
    sarrayForEachItem( Cb_Vertex_t *, pClub->pRoots, i, pV ) {
        
        if ( Cb_VertexIsGraphRootFanin( pV ) ||
             Cb_VertexIsGraphRoot( pV )) {
            return TRUE;
        }
    }
    
    return FALSE;
}


/**Function*************************************************************
  Synopsis    []
  Description []
  SideEffects []
  SeeAlso     []
***********************************************************************/
void
Cb_ClubListFree( sarray_t *listClubs )
{
    int i;
    Cb_Graph_t *pClub;
    sarrayForEachItem( Cb_Graph_t *, listClubs, i, pClub ) {
        Cb_GraphFree( pClub );
    }
    sarray_free( listClubs );
    return;
}

/**Function*************************************************************
  Synopsis    []
  Description []
  SideEffects []
  SeeAlso     []
***********************************************************************/
void
Cb_ClubListPrint( sarray_t *listClubs )
{
    int i;
    Cb_Graph_t *pClub;
    Cb_Vertex_t *pV;
    
    sarrayForEachItem( Cb_Graph_t *, listClubs, i, pClub ) {
        
        printf( "club[%3d]: ", i );
        Cb_GraphForEachVertexClub( pClub, pV ) {
            printf( "%s(l:%d) ", Ntk_NodeGetNamePrintable( pV->pData1 ),
                    pV->iLevel);
        }
        printf( "\n" );
    }
    return;
}

/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Definition of static functions                                            */
/*---------------------------------------------------------------------------*/


/**Function*************************************************************
  Synopsis    []
  Description []
  SideEffects []
  SeeAlso     []
***********************************************************************/
long
Cb_GraphGetRootWeight( Cb_Graph_t *pClub )
{
    int  i;
    long nWeight;
    Cb_Vertex_t *pV;
    
    nWeight = 1;
    sarrayForEachItem( Cb_Vertex_t *, pClub->pRoots, i, pV ) {
        
        if ( pV->nWeigh > 0 ) {
            
            nWeight *= pV->nWeigh;
        }
    }
    return nWeight;
}


/**Function*************************************************************
  Synopsis    []
  Description []
  SideEffects []
  SeeAlso     []
***********************************************************************/
long
Cb_GraphGetLeafWeight( Cb_Graph_t *pClub )
{
    int  i;
    long nWeight;
    Cb_Vertex_t *pV;
    
    nWeight = 1;
    sarrayForEachItem( Cb_Vertex_t *, pClub->pLeaves, i, pV ) {
        
        if ( pV->nWeigh > 0 ) {
            
            nWeight *= pV->nWeigh;
        }
    }
    return nWeight;
}

/**Function*************************************************************
  Synopsis    []
  Description [check whether the inclusion of an external node will
  invalidate all the current roots.]
  SideEffects []
  SeeAlso     []
***********************************************************************/
bool
Cb_ClubCheckRootsRemain( Cb_Graph_t *pClub, Cb_Vertex_t *pSpecial ) 
{
    bool          fRemain;
    int           i, k;
    Cb_Vertex_t  *pV;
    
    /* first mark all root vertices inside */
    sarrayForEachItem( Cb_Vertex_t *, pClub->pRoots, i, pV ) {
        
        Cb_VertexSetFlag1( pV );
    }
    
    /* check validity of current roots */
    fRemain = FALSE;
    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 ) {
            
            /* fanout to external territory */
            if ( pV->pOut[k] != pSpecial &&
                 !Cb_VertexTestFlag1( pV->pOut[k] ) ) {
                fRemain = TRUE;
                break;
            }
        }
        if ( fRemain )
            break;
    }
    
    /* remove marks */
    sarrayForEachItem( Cb_Vertex_t *, pClub->pRoots, i, pV ) {
        
        Cb_VertexResetFlag1( pV );
    }
    
    return fRemain;
}

////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////