llb1Group.c File Reference

#include "llbInt.h"

Go to the source code of this file.

Functions
ABC_NAMESPACE_IMPL_START Llb_Grp_t *	Llb_ManGroupAlloc (Llb_Man_t *pMan)
	DECLARATIONS ///. More...
void	Llb_ManGroupStop (Llb_Grp_t *p)
void	Llb_ManGroupCollect_rec (Aig_Man_t *pAig, Aig_Obj_t *pObj, Vec_Ptr_t *vNodes)
Vec_Ptr_t *	Llb_ManGroupCollect (Llb_Grp_t *pGroup)
void	Llb_ManGroupCreate_rec (Aig_Man_t *pAig, Aig_Obj_t *pObj, Vec_Ptr_t *vSupp)
Llb_Grp_t *	Llb_ManGroupCreate (Llb_Man_t *pMan, Aig_Obj_t *pObj)
Llb_Grp_t *	Llb_ManGroupCreateFirst (Llb_Man_t *pMan)
Llb_Grp_t *	Llb_ManGroupCreateLast (Llb_Man_t *pMan)
Llb_Grp_t *	Llb_ManGroupsCombine (Llb_Grp_t *p1, Llb_Grp_t *p2)
void	Llb_ManGroupMarkNodes_rec (Aig_Man_t *p, Aig_Obj_t *pObj)
Llb_Grp_t *	Llb_ManGroupCreateFromCuts (Llb_Man_t *pMan, Vec_Int_t *vCut1, Vec_Int_t *vCut2)
void	Llb_ManPrepareGroups (Llb_Man_t *pMan)
void	Llb_ManPrintSpan (Llb_Man_t *p)
int	Llb_ManGroupHasVar (Llb_Man_t *p, int iGroup, int iVar)
void	Llb_ManPrintHisto (Llb_Man_t *p)

Function Documentation

ABC_NAMESPACE_IMPL_START Llb_Grp_t* Llb_ManGroupAlloc

(

Llb_Man_t *

pMan

)

DECLARATIONS ///.

CFile****************************************************************

FileName [llb1Group.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [BDD based reachability.]

Synopsis [Initial partition computation.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id:

llb1Group.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

]FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file llb1Group.c.

{
    Llb_Grp_t * p;
    p = ABC_CALLOC( Llb_Grp_t, 1 );
    p->pMan   = pMan;
    p->vIns   = Vec_PtrAlloc( 8 );
    p->vOuts  = Vec_PtrAlloc( 8 );
    p->Id     = Vec_PtrSize( pMan->vGroups );
    Vec_PtrPush( pMan->vGroups, p );
    return p;
}

Vec_Ptr_t* Llb_ManGroupCollect

(

Llb_Grp_t *

pGroup

)

Function*************************************************************

Synopsis [Collects the support of MFFC.]

Description [Returns the number of internal nodes in the MFFC.]

SideEffects []

SeeAlso []

Definition at line 120 of file llb1Group.c.

{
    Vec_Ptr_t * vNodes;
    Aig_Obj_t * pObj;
    int i;
    vNodes = Vec_PtrAlloc( 100 );
    Aig_ManIncrementTravId( pGroup->pMan->pAig );
    Vec_PtrForEachEntry( Aig_Obj_t *, pGroup->vIns, pObj, i )
        Aig_ObjSetTravIdCurrent( pGroup->pMan->pAig, pObj );
    Vec_PtrForEachEntry( Aig_Obj_t *, pGroup->vOuts, pObj, i )
        Aig_ObjSetTravIdPrevious( pGroup->pMan->pAig, pObj );
    Vec_PtrForEachEntry( Aig_Obj_t *, pGroup->vOuts, pObj, i )
        Llb_ManGroupCollect_rec( pGroup->pMan->pAig, pObj, vNodes );
    return vNodes;
}

void Llb_ManGroupCollect_rec	(	Aig_Man_t *	pAig,
		Aig_Obj_t *	pObj,
		Vec_Ptr_t *	vNodes
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 91 of file llb1Group.c.

{
    if ( Aig_ObjIsTravIdCurrent(pAig, pObj) )
        return;
    Aig_ObjSetTravIdCurrent(pAig, pObj);
    if ( Aig_ObjIsConst1(pObj) )
        return;
    if ( Aig_ObjIsCo(pObj) )
    {
        Llb_ManGroupCollect_rec( pAig, Aig_ObjFanin0(pObj), vNodes );
        return;
    }
    assert( Aig_ObjIsAnd(pObj) );
    Llb_ManGroupCollect_rec( pAig, Aig_ObjFanin0(pObj), vNodes );
    Llb_ManGroupCollect_rec( pAig, Aig_ObjFanin1(pObj), vNodes );
    Vec_PtrPush( vNodes, pObj );
}

Llb_Grp_t* Llb_ManGroupCreate	(	Llb_Man_t *	pMan,
		Aig_Obj_t *	pObj
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 175 of file llb1Group.c.

{
    Llb_Grp_t * p;
    assert( pObj->fMarkA == 1 );
    // derive group
    p = Llb_ManGroupAlloc( pMan );
    Vec_PtrPush( p->vOuts, pObj );
    Aig_ManIncrementTravId( pMan->pAig );
    if ( Aig_ObjIsCo(pObj) )
        Llb_ManGroupCreate_rec( pMan->pAig, Aig_ObjFanin0(pObj), p->vIns );
    else
    {
        Llb_ManGroupCreate_rec( pMan->pAig, Aig_ObjFanin0(pObj), p->vIns );
        Llb_ManGroupCreate_rec( pMan->pAig, Aig_ObjFanin1(pObj), p->vIns );
    }
    // derive internal objects
    assert( p->vNodes == NULL );
    p->vNodes = Llb_ManGroupCollect( p );
    return p;
}

void Llb_ManGroupCreate_rec	(	Aig_Man_t *	pAig,
		Aig_Obj_t *	pObj,
		Vec_Ptr_t *	vSupp
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 147 of file llb1Group.c.

{ 
    if ( Aig_ObjIsTravIdCurrent(pAig, pObj) )
        return;
    Aig_ObjSetTravIdCurrent(pAig, pObj);
    if ( Aig_ObjIsConst1(pObj) )
        return;
    if ( pObj->fMarkA )
    {
        Vec_PtrPush( vSupp, pObj );
        return;
    }
    assert( Aig_ObjIsAnd(pObj) );
    Llb_ManGroupCreate_rec( pAig, Aig_ObjFanin0(pObj), vSupp );
    Llb_ManGroupCreate_rec( pAig, Aig_ObjFanin1(pObj), vSupp );
}

Llb_Grp_t* Llb_ManGroupCreateFirst

(

Llb_Man_t *

pMan

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 207 of file llb1Group.c.

{
    Llb_Grp_t * p;
    Aig_Obj_t * pObj;
    int i;
    p = Llb_ManGroupAlloc( pMan );
    Saig_ManForEachLo( pMan->pAig, pObj, i )
        Vec_PtrPush( p->vOuts, pObj );
    return p;
}

Llb_Grp_t* Llb_ManGroupCreateFromCuts	(	Llb_Man_t *	pMan,
		Vec_Int_t *	vCut1,
		Vec_Int_t *	vCut2
	)

Function*************************************************************

Synopsis [Creates group from two cuts derived by the flow computation.]

Description []

SideEffects []

SeeAlso []

Definition at line 312 of file llb1Group.c.

{
    Llb_Grp_t * p;
    Aig_Obj_t * pObj;
    int i;
    p = Llb_ManGroupAlloc( pMan );

    // mark Cut1
    Aig_ManIncrementTravId( pMan->pAig );
    Aig_ManForEachObjVec( vCut1, pMan->pAig, pObj, i )
        Aig_ObjSetTravIdCurrent( pMan->pAig, pObj );
    // collect unmarked Cut2
    Aig_ManForEachObjVec( vCut2, pMan->pAig, pObj, i )
        if ( !Aig_ObjIsTravIdCurrent( pMan->pAig, pObj ) )
            Vec_PtrPush( p->vOuts, pObj );

    // mark nodes reachable from Cut2
    Aig_ManIncrementTravId( pMan->pAig );
    Aig_ManForEachObjVec( vCut2, pMan->pAig, pObj, i )
        Llb_ManGroupMarkNodes_rec( pMan->pAig, pObj );
    // collect marked Cut1
    Aig_ManForEachObjVec( vCut1, pMan->pAig, pObj, i )
        if ( Aig_ObjIsTravIdCurrent( pMan->pAig, pObj ) )
            Vec_PtrPush( p->vIns, pObj );

    // derive internal objects
    assert( p->vNodes == NULL );
    p->vNodes = Llb_ManGroupCollect( p );
    return p;
}

Llb_Grp_t* Llb_ManGroupCreateLast

(

Llb_Man_t *

pMan

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 229 of file llb1Group.c.

{
    Llb_Grp_t * p;
    Aig_Obj_t * pObj;
    int i;
    p = Llb_ManGroupAlloc( pMan );
    Saig_ManForEachLi( pMan->pAig, pObj, i )
        Vec_PtrPush( p->vIns, pObj );
    return p;
}

int Llb_ManGroupHasVar	(	Llb_Man_t *	p,
		int	iGroup,
		int	iVar
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 426 of file llb1Group.c.

{
    Llb_Grp_t * pGroup = (Llb_Grp_t *)Vec_PtrEntry( p->vGroups, iGroup );
    Aig_Obj_t * pObj;
    int i;
    Vec_PtrForEachEntry( Aig_Obj_t *, pGroup->vIns, pObj, i )
        if ( pObj->Id == iVar )
            return 1;
    Vec_PtrForEachEntry( Aig_Obj_t *, pGroup->vOuts, pObj, i )
        if ( pObj->Id == iVar )
            return 1;
    return 0;
}

void Llb_ManGroupMarkNodes_rec	(	Aig_Man_t *	p,
		Aig_Obj_t *	pObj
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 286 of file llb1Group.c.

{
    if ( Aig_ObjIsTravIdCurrent(p, pObj) )
        return;
    if ( Aig_ObjIsTravIdPrevious(p, pObj) )
    {
        Aig_ObjSetTravIdCurrent(p, pObj);
        return;
    }
    Aig_ObjSetTravIdCurrent(p, pObj);
    assert( Aig_ObjIsNode(pObj) );
    Llb_ManGroupMarkNodes_rec( p, Aig_ObjFanin0(pObj) );
    Llb_ManGroupMarkNodes_rec( p, Aig_ObjFanin1(pObj) );
}

Llb_Grp_t* Llb_ManGroupsCombine	(	Llb_Grp_t *	p1,
		Llb_Grp_t *	p2
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 251 of file llb1Group.c.

{
    Llb_Grp_t * p;
    Aig_Obj_t * pObj;
    int i;
    p = Llb_ManGroupAlloc( p1->pMan );
    // create inputs
    Vec_PtrForEachEntry( Aig_Obj_t *, p1->vIns, pObj, i )
        Vec_PtrPush( p->vIns, pObj );
    Vec_PtrForEachEntry( Aig_Obj_t *, p2->vIns, pObj, i )
        Vec_PtrPushUnique( p->vIns, pObj );
    // create outputs
    Vec_PtrForEachEntry( Aig_Obj_t *, p1->vOuts, pObj, i )
        Vec_PtrPush( p->vOuts, pObj );
    Vec_PtrForEachEntry( Aig_Obj_t *, p2->vOuts, pObj, i )
        Vec_PtrPushUnique( p->vOuts, pObj );

    // derive internal objects
    assert( p->vNodes == NULL );
    p->vNodes = Llb_ManGroupCollect( p );
    return p;
}

void Llb_ManGroupStop

(

Llb_Grp_t *

p

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 68 of file llb1Group.c.

{
    if ( p == NULL )
        return;
    Vec_PtrWriteEntry( p->pMan->vGroups, p->Id, NULL );
    Vec_PtrFreeP( &p->vIns );
    Vec_PtrFreeP( &p->vOuts );
    Vec_PtrFreeP( &p->vNodes );
    ABC_FREE( p );
}

void Llb_ManPrepareGroups

(

Llb_Man_t *

pMan

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 356 of file llb1Group.c.

{
    Aig_Obj_t * pObj;
    int i;
    assert( pMan->vGroups == NULL );
    pMan->vGroups = Vec_PtrAlloc( 1000 );
    Llb_ManGroupCreateFirst( pMan );
    Aig_ManForEachNode( pMan->pAig, pObj, i )
    {
        if ( pObj->fMarkA )
            Llb_ManGroupCreate( pMan, pObj );
    }
    Saig_ManForEachLi( pMan->pAig, pObj, i )
    {
        if ( pObj->fMarkA )
            Llb_ManGroupCreate( pMan, pObj );
    }
    Llb_ManGroupCreateLast( pMan );
}

void Llb_ManPrintHisto

(

Llb_Man_t *

p

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 451 of file llb1Group.c.

{
    Aig_Obj_t * pObj;
    int i, k;
    Aig_ManForEachObj( p->pAig, pObj, i )
    {
        if ( Vec_IntEntry(p->vObj2Var, i) < 0 )
            continue;
        printf( "%3d :", i );
        for ( k = 0; k < Vec_IntEntry(p->vVarBegs, i); k++ )
            printf( " " );
        for (      ; k <= Vec_IntEntry(p->vVarEnds, i); k++ )
            printf( "%c", Llb_ManGroupHasVar(p, k, i)? '*':'-' );
        printf( "\n" );
    }
}

void Llb_ManPrintSpan

(

Llb_Man_t *

p

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 387 of file llb1Group.c.

{
    Llb_Grp_t * pGroup;
    Aig_Obj_t * pVar;
    int i, k, Span = 0, SpanMax = 0;
    Vec_PtrForEachEntry( Llb_Grp_t *, p->vGroups, pGroup, i )
    {
        Vec_PtrForEachEntry( Aig_Obj_t *, pGroup->vIns, pVar, k )
            if ( Vec_IntEntry(p->vVarBegs, pVar->Id) == i )
                Span++;
        Vec_PtrForEachEntry( Aig_Obj_t *, pGroup->vOuts, pVar, k )
            if ( Vec_IntEntry(p->vVarBegs, pVar->Id) == i )
                Span++;

        SpanMax = Abc_MaxInt( SpanMax, Span );
printf( "%d ", Span );

        Vec_PtrForEachEntry( Aig_Obj_t *, pGroup->vIns, pVar, k )
            if ( Vec_IntEntry(p->vVarEnds, pVar->Id) == i )
                Span--;
        Vec_PtrForEachEntry( Aig_Obj_t *, pGroup->vOuts, pVar, k )
            if ( Vec_IntEntry(p->vVarEnds, pVar->Id) == i )
                Span--;
    }
printf( "\n" );
printf( "Max = %d\n", SpanMax );
}