This graph shows which files directly or indirectly include this file:

Macros
#define	Dsd_IsComplement(p)
	MACRO DEFINITIONS ///.

#define	Dsd_Regular(p)

#define	Dsd_Not(p)

#define	Dsd_NotCond(p, c)

#define	Dsd_NodeForEachChild(Node, Index, Child)
	ITERATORS ///.

Typedefs
typedef struct Dsd_Manager_t_	Dsd_Manager_t
	TYPEDEF DEFINITIONS ///.

typedef struct Dsd_Node_t_	Dsd_Node_t

typedef enum Dsd_Type_t_	Dsd_Type_t

Enumerations
enum	Dsd_Type_t_ { DSD_NODE_NONE = 0 , DSD_NODE_CONST1 = 1 , DSD_NODE_BUF = 2 , DSD_NODE_OR = 3 , DSD_NODE_EXOR = 4 , DSD_NODE_PRIME = 5 }
	STRUCTURE DEFINITIONS ///. More...

Functions
Dsd_Type_t	Dsd_NodeReadType (Dsd_Node_t *p)
	FUNCTION DEFINITIONS ///.

DdNode *	Dsd_NodeReadFunc (Dsd_Node_t *p)

DdNode *	Dsd_NodeReadSupp (Dsd_Node_t *p)

Dsd_Node_t **	Dsd_NodeReadDecs (Dsd_Node_t *p)

Dsd_Node_t *	Dsd_NodeReadDec (Dsd_Node_t *p, int i)

int	Dsd_NodeReadDecsNum (Dsd_Node_t *p)

word	Dsd_NodeReadMark (Dsd_Node_t *p)

void	Dsd_NodeSetMark (Dsd_Node_t *p, word Mark)

DdManager *	Dsd_ManagerReadDd (Dsd_Manager_t *pMan)

Dsd_Node_t *	Dsd_ManagerReadRoot (Dsd_Manager_t *pMan, int i)

Dsd_Node_t *	Dsd_ManagerReadInput (Dsd_Manager_t *pMan, int i)

Dsd_Node_t *	Dsd_ManagerReadConst1 (Dsd_Manager_t *pMan)

Dsd_Manager_t *	Dsd_ManagerStart (DdManager *dd, int nSuppMax, int fVerbose)
	FUNCTION DECLARATIONS ///.

void	Dsd_ManagerStop (Dsd_Manager_t *dMan)

void	Dsd_Decompose (Dsd_Manager_t dMan, DdNode *pbFuncs, int nFuncs)
	DECOMPOSITION FUNCTIONS ///.

Dsd_Node_t *	Dsd_DecomposeOne (Dsd_Manager_t pDsdMan, DdNode bFunc)

void	Dsd_TreeNodeGetInfo (Dsd_Manager_t dMan, int DepthMax, int *GateSizeMax)

void	Dsd_TreeNodeGetInfoOne (Dsd_Node_t pNode, int DepthMax, int *GateSizeMax)

int	Dsd_TreeGetAigCost (Dsd_Node_t *pNode)

int	Dsd_TreeCountNonTerminalNodes (Dsd_Manager_t *dMan)

int	Dsd_TreeCountNonTerminalNodesOne (Dsd_Node_t *pRoot)

int	Dsd_TreeCountPrimeNodes (Dsd_Manager_t *pDsdMan)

int	Dsd_TreeCountPrimeNodesOne (Dsd_Node_t *pRoot)

int	Dsd_TreeCollectDecomposableVars (Dsd_Manager_t dMan, int pVars)

Dsd_Node_t **	Dsd_TreeCollectNodesDfs (Dsd_Manager_t dMan, int pnNodes)

Dsd_Node_t **	Dsd_TreeCollectNodesDfsOne (Dsd_Manager_t pDsdMan, Dsd_Node_t pNode, int *pnNodes)

void	Dsd_TreePrint (FILE pFile, Dsd_Manager_t dMan, char pInputNames[], char pOutputNames[], int fShortNames, int Output, int OffSet)

void	Dsd_TreePrint2 (FILE pFile, Dsd_Manager_t dMan, char pInputNames[], char pOutputNames[], int Output)

void	Dsd_TreePrint3 (void pStr, Dsd_Manager_t pDsdMan, int Output)

void	Dsd_TreePrint4 (void pStr, Dsd_Manager_t pDsdMan, int Output)

void	Dsd_NodePrint (FILE pFile, Dsd_Node_t pNode)

int	Dsd_TreeNonDsdMax (Dsd_Manager_t *pDsdMan, int Output)

int	Dsd_TreeSuppSize (Dsd_Manager_t *pDsdMan, int Output)

DdNode *	Dsd_TreeGetPrimeFunction (DdManager dd, Dsd_Node_t pNode)
	FUNCTION DEFINITIONS ///.

Macro Definition Documentation

◆ Dsd_IsComplement

#define Dsd_IsComplement ( p )

Value:

(((int)((ABC_PTRUINT_T) (p) & 01)))

p

Cube * p

Definition exorList.c:222

MACRO DEFINITIONS ///.

Definition at line 68 of file dsd.h.

◆ Dsd_NodeForEachChild

#define Dsd_NodeForEachChild	(	Node,
		Index,
		Child )

Value:

    for ( Index = 0;                                      \
          Index < Dsd_NodeReadDecsNum(Node) &&            \
             ((Child = Dsd_NodeReadDec(Node,Index))!=0);  \
          Index++ )

ITERATORS ///.

Definition at line 78 of file dsd.h.

#define Dsd_NodeForEachChild( Node, Index, Child )        \
    for ( Index = 0;                                      \
          Index < Dsd_NodeReadDecsNum(Node) &&            \
             ((Child = Dsd_NodeReadDec(Node,Index))!=0);  \
          Index++ )

◆ Dsd_Not

#define Dsd_Not ( p )

Value:

((Dsd_Node_t *)((ABC_PTRUINT_T)(p) ^ 01))

Dsd_Node_t

struct Dsd_Node_t_ Dsd_Node_t

Definition dsd.h:60

Definition at line 70 of file dsd.h.

◆ Dsd_NotCond

#define Dsd_NotCond	(		p,
			c )

Value:

((Dsd_Node_t *)((ABC_PTRUINT_T)(p) ^ (c)))

Definition at line 71 of file dsd.h.

◆ Dsd_Regular

#define Dsd_Regular ( p )

Value:

((Dsd_Node_t *)((ABC_PTRUINT_T)(p) & ~01))

Definition at line 69 of file dsd.h.

Typedef Documentation

◆ Dsd_Manager_t

typedef struct Dsd_Manager_t_ Dsd_Manager_t

TYPEDEF DEFINITIONS ///.

Definition at line 59 of file dsd.h.

◆ Dsd_Node_t

typedef struct Dsd_Node_t_ Dsd_Node_t

Definition at line 60 of file dsd.h.

◆ Dsd_Type_t

typedef enum Dsd_Type_t_ Dsd_Type_t

Definition at line 61 of file dsd.h.

Enumeration Type Documentation

◆ Dsd_Type_t_

enum Dsd_Type_t_

STRUCTURE DEFINITIONS ///.

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

FileName [dsd.h]

PackageName [DSD: Disjoint-support decomposition package.]

Synopsis [External declarations of the package. This fast BDD-based recursive algorithm for simple (single-output) DSD is based on the following papers: (1) V. Bertacco and M. Damiani, "Disjunctive decomposition of logic functions," Proc. ICCAD '97, pp. 78-82. (2) Y. Matsunaga, "An exact and efficient algorithm for disjunctive decomposition", Proc. SASIMI '98, pp. 44-50. The scope of detected decompositions is the same as in the paper: T. Sasao and M. Matsuura, "DECOMPOS: An integrated system for functional decomposition," Proc. IWLS '98, pp. 471-477.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 8.0. Started - September 22, 2003.]

Revision [

Id: dsd.h,v 1.0 2002/22/09 00:00:00 alanmi Exp

] PARAMETERS ///

Enumerator
DSD_NODE_NONE
DSD_NODE_CONST1
DSD_NODE_BUF
DSD_NODE_OR
DSD_NODE_EXOR
DSD_NODE_PRIME

Definition at line 46 of file dsd.h.

                 { 
    DSD_NODE_NONE   = 0,
    DSD_NODE_CONST1 = 1,
    DSD_NODE_BUF    = 2,
    DSD_NODE_OR     = 3,
    DSD_NODE_EXOR   = 4,
    DSD_NODE_PRIME  = 5,
};

Function Documentation

◆ Dsd_Decompose()

void Dsd_Decompose	(	Dsd_Manager_t *	pDsdMan,
		DdNode **	pbFuncs,
		int	nFuncs )

extern

DECOMPOSITION FUNCTIONS ///.

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

Synopsis [Performs DSD for the array of functions represented by BDDs.]

Description [This function takes the DSD manager, which should be previously allocated by the call to Dsd_ManagerStart(). The resulting DSD tree is stored in the DSD manager (pDsdMan->pRoots, pDsdMan->nRoots). Access to the tree is through the APIs of the manager. The resulting tree is a shared DSD DAG for the functions given in the array. For one function the resulting DAG is always a tree. The root node pointers can be complemented, as discussed in the literature referred to in "dsd.h". This procedure can be called repeatedly for different functions. There is no need to remove the decomposition tree after it is returned, because the next call to the DSD manager will "recycle" the tree. The user should not modify or dereference any data associated with the nodes of the DSD trees (the user can only change the contents of a temporary mark associated with each node by the calling to Dsd_NodeSetMark()). All the decomposition trees and intermediate nodes will be removed when the DSD manager is deallocated at the end by calling Dsd_ManagerStop().]

SideEffects []

SeeAlso []

Definition at line 113 of file dsdProc.c.

{
    DdManager * dd = pDsdMan->dd;
    int i;
    abctime clk;
    Dsd_Node_t * pTemp;
    int SumMaxGateSize = 0;
    int nDecOutputs = 0;
    int nCBFOutputs = 0;
/*
s_Loops1 = 0;
s_Loops2 = 0;
s_Loops3 = 0;
s_Case4Calls = 0;
s_Case4CallsSpecial = 0;
s_Case5 = 0;
s_Loops2Useless = 0;
*/
    // resize the number of roots in the manager
    if ( pDsdMan->nRootsAlloc < nFuncs )
    {
        if ( pDsdMan->nRootsAlloc > 0 )
            ABC_FREE( pDsdMan->pRoots );
        pDsdMan->nRootsAlloc = nFuncs;
        pDsdMan->pRoots = (Dsd_Node_t **) ABC_ALLOC( char, pDsdMan->nRootsAlloc * sizeof(Dsd_Node_t *) );
    }
 
    if ( pDsdMan->fVerbose )
        printf( "\nDecomposability statistics for individual outputs:\n" );
 
    // set the counter of decomposition nodes
    s_nDecBlocks = 0;
 
    // perform decomposition for all outputs
    clk = Abc_Clock();
    pDsdMan->nRoots = 0;
    s_nCascades = 0;
    for ( i = 0; i < nFuncs; i++ )
    {
        int nLiteralsPrev;
        int nDecBlocksPrev;
        int nExorGatesPrev;
        int nReusedBlocksPres;
        int nCascades;
        int MaxBlock;
        int nPrimeBlocks;
        abctime clk;
 
        clk = Abc_Clock();
        nLiteralsPrev     = s_nLiterals;
        nDecBlocksPrev    = s_nDecBlocks;
        nExorGatesPrev    = s_nExorGates;
        nReusedBlocksPres = s_nReusedBlocks;
        nPrimeBlocks      = s_nPrimeBlocks;
 
        pDsdMan->pRoots[ pDsdMan->nRoots++ ] = dsdKernelDecompose_rec( pDsdMan, pbFuncs[i] );
 
        Dsd_TreeNodeGetInfoOne( pDsdMan->pRoots[i], &nCascades, &MaxBlock );
        s_nCascades = ddMax( s_nCascades, nCascades );
        pTemp = Dsd_Regular(pDsdMan->pRoots[i]);
        if ( pTemp->Type != DSD_NODE_PRIME || pTemp->nDecs != Extra_bddSuppSize(dd,pTemp->S) )
            nDecOutputs++;
        if ( MaxBlock < 3 )
            nCBFOutputs++;
        SumMaxGateSize += MaxBlock;
 
        if ( pDsdMan->fVerbose )
        {
            printf("#%02d: ", i );                              
            printf("Ins=%2d. ", Cudd_SupportSize(dd,pbFuncs[i]) );                  
            printf("Gts=%3d. ", Dsd_TreeCountNonTerminalNodesOne( pDsdMan->pRoots[i] ) ); 
            printf("Pri=%3d. ", Dsd_TreeCountPrimeNodesOne( pDsdMan->pRoots[i] ) ); 
            printf("Max=%3d. ", MaxBlock ); 
            printf("Reuse=%2d. ", s_nReusedBlocks-nReusedBlocksPres ); 
            printf("Csc=%2d. ", nCascades ); 
            printf("T= %.2f s. ", (float)(Abc_Clock()-clk)/(float)(CLOCKS_PER_SEC) ) ;
            printf("Bdd=%2d. ", Cudd_DagSize(pbFuncs[i]) ); 
            printf("\n");
            fflush( stdout );
        }
    }
    assert( pDsdMan->nRoots == nFuncs );
 
    if ( pDsdMan->fVerbose )
    {
        printf( "\n" );
        printf( "The cumulative decomposability statistics:\n" );
        printf( "  Total outputs                             = %5d\n", nFuncs );
        printf( "  Decomposable outputs                      = %5d\n", nDecOutputs );
        printf( "  Completely decomposable outputs           = %5d\n", nCBFOutputs );
        printf( "  The sum of max gate sizes                 = %5d\n", SumMaxGateSize );
        printf( "  Shared BDD size                           = %5d\n", Cudd_SharingSize( pbFuncs, nFuncs ) );
        printf( "  Decomposition entries                     = %5d\n", st__count( pDsdMan->Table ) );
        printf( "  Pure decomposition time                   =  %.2f sec\n", (float)(Abc_Clock() - clk)/(float)(CLOCKS_PER_SEC) );
    }
/*
    printf( "s_Loops1 = %d.\n", s_Loops1 );
    printf( "s_Loops2 = %d.\n", s_Loops2 );
    printf( "s_Loops3 = %d.\n", s_Loops3 );
    printf( "s_Case4Calls = %d.\n", s_Case4Calls );
    printf( "s_Case4CallsSpecial = %d.\n", s_Case4CallsSpecial );
    printf( "s_Case5 = %d.\n", s_Case5 );
    printf( "s_Loops2Useless = %d.\n", s_Loops2Useless );
*/
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Dsd_DecomposeOne()

Dsd_Node_t * Dsd_DecomposeOne	(	Dsd_Manager_t *	pDsdMan,
		DdNode *	bFunc )

extern

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

Synopsis [Performs decomposition for one function.]

Description []

SideEffects []

SeeAlso []

Definition at line 230 of file dsdProc.c.

{
    return dsdKernelDecompose_rec( pDsdMan, bFunc );
}

◆ Dsd_ManagerReadConst1()

Dsd_Node_t * Dsd_ManagerReadConst1 ( Dsd_Manager_t * pMan )

extern

Definition at line 95 of file dsdApi.c.

95{ return pMan->pConst1; }

Dsd_Manager_t_::pConst1

Dsd_Node_t * pConst1

Definition dsdInt.h:49

◆ Dsd_ManagerReadDd()

DdManager * Dsd_ManagerReadDd ( Dsd_Manager_t * pMan )

extern

Definition at line 96 of file dsdApi.c.

96{ return pMan->dd; }

◆ Dsd_ManagerReadInput()

Dsd_Node_t * Dsd_ManagerReadInput	(	Dsd_Manager_t *	pMan,
		int	i )

extern

Definition at line 94 of file dsdApi.c.

94{ return pMan->pInputs[i]; }

Dsd_Manager_t_::pInputs

Dsd_Node_t ** pInputs

Definition dsdInt.h:47

◆ Dsd_ManagerReadRoot()

Dsd_Node_t * Dsd_ManagerReadRoot	(	Dsd_Manager_t *	pMan,
		int	i )

extern

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

Synopsis [APIs of the DSD manager.]

Description [Allows the use to get hold of an individual leave of the DSD tree (Dsd_ManagerReadInput) or an individual root of the decomposition tree (Dsd_ManagerReadRoot). The root may have the complemented attribute.]

SideEffects []

SeeAlso []

Definition at line 93 of file dsdApi.c.

93{ return pMan->pRoots[i]; }

◆ Dsd_ManagerStart()

Dsd_Manager_t * Dsd_ManagerStart	(	DdManager *	dd,
		int	nSuppMax,
		int	fVerbose )

extern

FUNCTION DECLARATIONS ///.

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

FileName [dsdMan.c]

PackageName [DSD: Disjoint-support decomposition package.]

Synopsis [APIs of the DSD manager.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 8.0. Started - September 22, 2003.]

Revision [

Id: dsdMan.c,v 1.0 2002/22/09 00:00:00 alanmi Exp

] API OF DSD MANAGER /// Function*************************************************************

Synopsis [Starts the DSD manager.]

Description [Takes the started BDD manager and the maximum support size of the function to be DSD-decomposed. The manager should have at least as many variables as there are variables in the support. The functions should be expressed using the first nSuppSizeMax variables in the manager (these may be ordered not necessarily on top of the manager).]

SideEffects []

SeeAlso []

Definition at line 47 of file dsdMan.c.

{
    Dsd_Manager_t * dMan;
    Dsd_Node_t * pNode;
    int i;
 
    assert( nSuppMax <= dd->size );
 
    dMan = ABC_ALLOC( Dsd_Manager_t, 1 );
    memset( dMan, 0, sizeof(Dsd_Manager_t) );
    dMan->dd          = dd;
    dMan->nInputs     = nSuppMax;
    dMan->fVerbose    = fVerbose;
    dMan->nRoots      = 0;
    dMan->nRootsAlloc = 50;
    dMan->pRoots      = (Dsd_Node_t **) ABC_ALLOC( char, dMan->nRootsAlloc * sizeof(Dsd_Node_t *) );
    dMan->pInputs     = (Dsd_Node_t **) ABC_ALLOC( char, dMan->nInputs     * sizeof(Dsd_Node_t *) );
 
    // create the primary inputs and insert them into the table
    dMan->Table       = st__init_table( st__ptrcmp, st__ptrhash);
    for ( i = 0; i < dMan->nInputs; i++ )
    {
        pNode = Dsd_TreeNodeCreate( DSD_NODE_BUF, 1, 0 );
        pNode->G = dd->vars[i];  Cudd_Ref( pNode->G );
        pNode->S = dd->vars[i];  Cudd_Ref( pNode->S );
        st__insert( dMan->Table, (char*)dd->vars[i], (char*)pNode );
        dMan->pInputs[i] = pNode;
    }
    pNode = Dsd_TreeNodeCreate( DSD_NODE_CONST1, 0, 0 );
    pNode->G = b1;  Cudd_Ref( pNode->G );
    pNode->S = b1;  Cudd_Ref( pNode->S );
    st__insert( dMan->Table, (char*)b1, (char*)pNode );
    dMan->pConst1 = pNode;
 
    Dsd_CheckCacheAllocate( 5000 );
    return dMan;
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Dsd_ManagerStop()

void Dsd_ManagerStop ( Dsd_Manager_t * dMan )

extern

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

Synopsis [Stops the DSD manager.]

Description [Stopping the DSD manager automatically derefereces and deallocates all the DSD nodes that were created during the life time of the DSD manager. As a result, the user does not need to deref or deallocate any DSD nodes or trees that are derived and placed in the manager while it exists.]

SideEffects []

SeeAlso []

Definition at line 100 of file dsdMan.c.

{
    st__generator * gen;
    Dsd_Node_t * pNode;
    DdNode * bFunc;
    // delete the nodes
    st__foreach_item( dMan->Table, gen, (const char**)&bFunc, (char**)&pNode )
        Dsd_TreeNodeDelete( dMan->dd, Dsd_Regular(pNode) );
    st__free_table(dMan->Table);
    ABC_FREE( dMan->pInputs );
    ABC_FREE( dMan->pRoots );
    ABC_FREE( dMan );
    Dsd_CheckCacheDeallocate();
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Dsd_NodePrint()

void Dsd_NodePrint	(	FILE *	pFile,
		Dsd_Node_t *	pNode )

extern

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

Synopsis [Prints the decompostion tree into file.]

Description []

SideEffects []

SeeAlso []

Definition at line 1138 of file dsdTree.c.

{
    Dsd_Node_t * pNodeR;
    int SigCounter = 1;
    pNodeR = Dsd_Regular(pNode);
    Dsd_NodePrint_rec( pFile, pNodeR, pNodeR != pNode, "F", 0, &SigCounter );
}

◆ Dsd_NodeReadDec()

Dsd_Node_t * Dsd_NodeReadDec	(	Dsd_Node_t *	p,
		int	i )

extern

Definition at line 57 of file dsdApi.c.

57{ return p->pDecs[i]; }

◆ Dsd_NodeReadDecs()

Dsd_Node_t ** Dsd_NodeReadDecs ( Dsd_Node_t * p )

extern

Definition at line 56 of file dsdApi.c.

56{ return p->pDecs; }

◆ Dsd_NodeReadDecsNum()

int Dsd_NodeReadDecsNum ( Dsd_Node_t * p )

extern

Definition at line 58 of file dsdApi.c.

58{ return p->nDecs; }

◆ Dsd_NodeReadFunc()

DdNode * Dsd_NodeReadFunc ( Dsd_Node_t * p )

extern

Definition at line 54 of file dsdApi.c.

54{ return p->G; }

◆ Dsd_NodeReadMark()

word Dsd_NodeReadMark ( Dsd_Node_t * p )

extern

Definition at line 59 of file dsdApi.c.

59{ return p->Mark; }

◆ Dsd_NodeReadSupp()

DdNode * Dsd_NodeReadSupp ( Dsd_Node_t * p )

extern

Definition at line 55 of file dsdApi.c.

55{ return p->S; }

◆ Dsd_NodeReadType()

Dsd_Type_t Dsd_NodeReadType ( Dsd_Node_t * p )

extern

FUNCTION DEFINITIONS ///.

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

FileName [dsdApi.c]

PackageName [DSD: Disjoint-support decomposition package.]

Synopsis [Implementation of API functions.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 8.0. Started - September 22, 2003.]

Revision [

Id: dsdApi.c,v 1.0 2002/22/09 00:00:00 alanmi Exp

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

Synopsis [APIs of the DSD node.]

Description [The node's type can be retrieved by calling Dsd_NodeReadType(). The type is one of the following: constant 1 node, the buffer (or the elementary variable), OR gate, EXOR gate, or PRIME function (a non-DSD-decomposable function with more than two inputs). The return value of Dsd_NodeReadFunc() is the global function of the DSD node. The return value of Dsd_NodeReadSupp() is the support of the global function of the DSD node. The array of DSD nodes returned by Dsd_NodeReadDecs() is the array of decomposition nodes for the formal inputs of the given node. The number of decomposition entries returned by Dsd_NodeReadDecsNum() is the number of formal inputs. The mark is explained below.]

SideEffects []

SeeAlso []

Definition at line 53 of file dsdApi.c.

53{ return p->Type; }

◆ Dsd_NodeSetMark()

void Dsd_NodeSetMark	(	Dsd_Node_t *	p,
		word	Mark )

extern

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

Synopsis [APIs of the DSD node.]

Description [This API allows the user to set the integer mark in the given DSD node. The mark is guaranteed to persist as long as the calls to the decomposition are not performed. In any case, the mark is useful to associate the node with some temporary information, such as its number in the DFS ordered list of the DSD nodes or its number in the BLIF file that it being written.]

SideEffects []

SeeAlso []

Definition at line 77 of file dsdApi.c.

77{ p->Mark = Mark; }

◆ Dsd_TreeCollectDecomposableVars()

int Dsd_TreeCollectDecomposableVars	(	Dsd_Manager_t *	pDsdMan,
		int *	pVars )

extern

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

Synopsis [Collects the decomposable vars on the PI side.]

Description []

SideEffects []

SeeAlso []

Definition at line 470 of file dsdTree.c.

{
    int nVars;
 
    // set the vars collected to 0
    nVars = 0;
    Dsd_TreeCollectDecomposableVars_rec( pDsdMan->dd, Dsd_Regular(pDsdMan->pRoots[0]), pVars, &nVars );
    // return the number of collected vars
    return nVars;
}

◆ Dsd_TreeCollectNodesDfs()

Dsd_Node_t ** Dsd_TreeCollectNodesDfs	(	Dsd_Manager_t *	pDsdMan,
		int *	pnNodes )

extern

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

Synopsis [Creates the DFS ordered array of DSD nodes in the tree.]

Description [The collected nodes do not include the terminal nodes and the constant 1 node. The array of nodes is returned. The number of entries in the array is returned in the variale pnNodes.]

SideEffects []

SeeAlso []

Definition at line 555 of file dsdTree.c.

{
    Dsd_Node_t ** ppNodes;
    int nNodes, nNodesAlloc;
    int i;
 
    nNodesAlloc = Dsd_TreeCountNonTerminalNodes(pDsdMan);
    nNodes  = 0;
    ppNodes = ABC_ALLOC( Dsd_Node_t *, nNodesAlloc );
    for ( i = 0; i < pDsdMan->nRoots; i++ )
        Dsd_TreeCollectNodesDfs_rec( Dsd_Regular(pDsdMan->pRoots[i]), ppNodes, &nNodes );
    Dsd_TreeUnmark( pDsdMan );
    assert( nNodesAlloc == nNodes );
    *pnNodes = nNodes;
    return ppNodes;
}

Here is the call graph for this function:

◆ Dsd_TreeCollectNodesDfsOne()

Dsd_Node_t ** Dsd_TreeCollectNodesDfsOne	(	Dsd_Manager_t *	pDsdMan,
		Dsd_Node_t *	pNode,
		int *	pnNodes )

extern

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

Synopsis [Creates the DFS ordered array of DSD nodes in the tree.]

Description [The collected nodes do not include the terminal nodes and the constant 1 node. The array of nodes is returned. The number of entries in the array is returned in the variale pnNodes.]

SideEffects []

SeeAlso []

Definition at line 585 of file dsdTree.c.

{
    Dsd_Node_t ** ppNodes;
    int nNodes, nNodesAlloc;
    nNodesAlloc = Dsd_TreeCountNonTerminalNodesOne(pNode);
    nNodes  = 0;
    ppNodes = ABC_ALLOC( Dsd_Node_t *, nNodesAlloc );
    Dsd_TreeCollectNodesDfs_rec( Dsd_Regular(pNode), ppNodes, &nNodes );
    Dsd_TreeUnmark_rec(Dsd_Regular(pNode));
    assert( nNodesAlloc == nNodes );
    *pnNodes = nNodes;
    return ppNodes;
}

Here is the call graph for this function:

◆ Dsd_TreeCountNonTerminalNodes()

int Dsd_TreeCountNonTerminalNodes ( Dsd_Manager_t * pDsdMan )

extern

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

Synopsis [Counts non-terminal nodes of the DSD tree.]

Description [Nonterminal nodes include all the nodes with the support more than 1. These are OR, EXOR, and PRIME nodes. They do not include the elementary variable nodes and the constant 1 node.]

SideEffects []

SeeAlso []

Definition at line 310 of file dsdTree.c.

{
    int Counter, i;
    Counter = 0;
    for ( i = 0; i < pDsdMan->nRoots; i++ )
        Counter += Dsd_TreeCountNonTerminalNodes_rec( Dsd_Regular( pDsdMan->pRoots[i] ) );
    Dsd_TreeUnmark( pDsdMan );
    return Counter;
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Dsd_TreeCountNonTerminalNodesOne()

int Dsd_TreeCountNonTerminalNodesOne ( Dsd_Node_t * pRoot )

extern

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 331 of file dsdTree.c.

{
    int Counter = 0;
 
    // go through the list of successors and call recursively 
    Counter = Dsd_TreeCountNonTerminalNodes_rec( Dsd_Regular(pRoot) );
 
    Dsd_TreeUnmark_rec( Dsd_Regular(pRoot) );
    return Counter;
}

Here is the caller graph for this function:

◆ Dsd_TreeCountPrimeNodes()

int Dsd_TreeCountPrimeNodes ( Dsd_Manager_t * pDsdMan )

extern

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

Synopsis [Counts prime nodes of the DSD tree.]

Description [Prime nodes are nodes with the support more than 2, that is not an OR or EXOR gate.]

SideEffects []

SeeAlso []

Definition at line 389 of file dsdTree.c.

{
    int Counter, i;
    Counter = 0;
    for ( i = 0; i < pDsdMan->nRoots; i++ )
        Counter += Dsd_TreeCountPrimeNodes_rec( Dsd_Regular( pDsdMan->pRoots[i] ) );
    Dsd_TreeUnmark( pDsdMan );
    return Counter;
}

Here is the call graph for this function:

◆ Dsd_TreeCountPrimeNodesOne()

int Dsd_TreeCountPrimeNodesOne ( Dsd_Node_t * pRoot )

extern

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

Synopsis [Counts prime nodes for one root.]

Description []

SideEffects []

SeeAlso []

Definition at line 410 of file dsdTree.c.

{
    int Counter = 0;
 
    // go through the list of successors and call recursively 
    Counter = Dsd_TreeCountPrimeNodes_rec( Dsd_Regular(pRoot) );
 
    Dsd_TreeUnmark_rec( Dsd_Regular(pRoot) );
    return Counter;
}

Here is the caller graph for this function:

◆ Dsd_TreeGetAigCost()

int Dsd_TreeGetAigCost ( Dsd_Node_t * pNode )

extern

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

Synopsis [Counts AIG nodes needed to implement this node.]

Description [Assumes that the only primes of the DSD tree are MUXes.]

SideEffects []

SeeAlso []

Definition at line 291 of file dsdTree.c.

{
    return Dsd_TreeGetAigCost_rec( Dsd_Regular(pNode) );
}

Here is the call graph for this function:

◆ Dsd_TreeGetPrimeFunction()

DdNode * Dsd_TreeGetPrimeFunction	(	DdManager *	dd,
		Dsd_Node_t *	pNode )

extern

FUNCTION DEFINITIONS ///.

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

Synopsis [Returns the local function of the DSD node. ]

Description [The local function is computed using the global function of the node and the global functions of the formal inputs. The resulting local function is mapped using the topmost N variables of the manager. The number of variables N is equal to the number of formal inputs.]

SideEffects []

SeeAlso []

Definition at line 54 of file dsdLocal.c.

{
    int * pForm2Var;   // the mapping of each formal input into its first var
    int * pVar2Form;   // the mapping of each var into its formal inputs
    int i, iVar, iLev, * pPermute;
    DdNode ** pbCube0, ** pbCube1;
    DdNode * bFunc, * bRes, * bTemp;
    st__table * pCache;
    
    pPermute  = ABC_ALLOC( int, dd->size );
    pVar2Form = ABC_ALLOC( int, dd->size );
    pForm2Var = ABC_ALLOC( int, dd->size );
 
    pbCube0 = ABC_ALLOC( DdNode *, dd->size );
    pbCube1 = ABC_ALLOC( DdNode *, dd->size );
 
    // remap the global function in such a way that
    // the support variables of each formal input are adjacent
    iLev = 0;
    for ( i = 0; i < pNode->nDecs; i++ )
    {
        pForm2Var[i] = dd->invperm[i];
        for ( bTemp = pNode->pDecs[i]->S; bTemp != b1; bTemp = cuddT(bTemp) )
        {
            iVar = dd->invperm[iLev];
            pPermute[bTemp->index] = iVar;
            pVar2Form[iVar] = i;
            iLev++;
        }
 
        // collect the cubes representing each assignment
        pbCube0[i] = Extra_bddGetOneCube( dd, Cudd_Not(pNode->pDecs[i]->G) );
        Cudd_Ref( pbCube0[i] );
        pbCube1[i] = Extra_bddGetOneCube( dd, pNode->pDecs[i]->G );
        Cudd_Ref( pbCube1[i] );
    }
 
    // remap the function
    bFunc = Cudd_bddPermute( dd, pNode->G, pPermute ); Cudd_Ref( bFunc );
    // remap the cube
    for ( i = 0; i < pNode->nDecs; i++ )
    {
        pbCube0[i] = Cudd_bddPermute( dd, bTemp = pbCube0[i], pPermute ); Cudd_Ref( pbCube0[i] );
        Cudd_RecursiveDeref( dd, bTemp );
        pbCube1[i] = Cudd_bddPermute( dd, bTemp = pbCube1[i], pPermute ); Cudd_Ref( pbCube1[i] );
        Cudd_RecursiveDeref( dd, bTemp );
    }
 
    // remap the function
    pCache = st__init_table( st__ptrcmp, st__ptrhash);;
    bRes = Extra_dsdRemap( dd, bFunc, pCache, pVar2Form, pForm2Var, pbCube0, pbCube1 );  Cudd_Ref( bRes );
    st__free_table( pCache );
 
    Cudd_RecursiveDeref( dd, bFunc );
    for ( i = 0; i < pNode->nDecs; i++ )
    {
        Cudd_RecursiveDeref( dd, pbCube0[i] );
        Cudd_RecursiveDeref( dd, pbCube1[i] );
    }
/*
    // permute the function once again
    // in such a way that i-th var stood for i-th formal input
    for ( i = 0; i < dd->size; i++ )
        pPermute[i] = -1;
    for ( i = 0; i < pNode->nDecs; i++ )
        pPermute[dd->invperm[i]] = i;
    bRes = Cudd_bddPermute( dd, bTemp = bRes, pPermute ); Cudd_Ref( bRes );
    Cudd_RecursiveDeref( dd, bTemp );
*/
    ABC_FREE(pPermute);
    ABC_FREE(pVar2Form);
    ABC_FREE(pForm2Var);
    ABC_FREE(pbCube0);
    ABC_FREE(pbCube1);
 
    Cudd_Deref( bRes );
    return bRes;
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Dsd_TreeNodeGetInfo()

void Dsd_TreeNodeGetInfo	(	Dsd_Manager_t *	pDsdMan,
		int *	DepthMax,
		int *	GateSizeMax )

extern

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

Synopsis [Getting information about the node.]

Description [This function computes the max depth and the max gate size of the tree rooted at the node.]

SideEffects []

SeeAlso []

Definition at line 156 of file dsdTree.c.

{
    int i;
    s_DepthMax    = 0;
    s_GateSizeMax = 0;
 
    for ( i = 0; i < pDsdMan->nRoots; i++ )
        Dsd_TreeGetInfo_rec( Dsd_Regular( pDsdMan->pRoots[i] ), 0 );
 
    if ( DepthMax ) 
        *DepthMax     = s_DepthMax;
    if ( GateSizeMax ) 
        *GateSizeMax  = s_GateSizeMax;
}

◆ Dsd_TreeNodeGetInfoOne()

void Dsd_TreeNodeGetInfoOne	(	Dsd_Node_t *	pNode,
		int *	DepthMax,
		int *	GateSizeMax )

extern

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

Synopsis [Getting information about the node.]

Description [This function computes the max depth and the max gate size of the tree rooted at the node.]

SideEffects []

SeeAlso []

Definition at line 183 of file dsdTree.c.

{
    s_DepthMax    = 0;
    s_GateSizeMax = 0;
 
    Dsd_TreeGetInfo_rec( Dsd_Regular(pNode), 0 );
 
    if ( DepthMax ) 
        *DepthMax     = s_DepthMax;
    if ( GateSizeMax ) 
        *GateSizeMax  = s_GateSizeMax;
}

Here is the caller graph for this function:

◆ Dsd_TreeNonDsdMax()

int Dsd_TreeNonDsdMax	(	Dsd_Manager_t *	pDsdMan,
		int	Output )

extern

Definition at line 655 of file dsdTree.c.

{
    if ( Output == -1 ) 
    {
        int i, Res = 0;
        for ( i = 0; i < pDsdMan->nRoots; i++ )
            Res = Abc_MaxInt( Res, Dsd_TreeNonDsdMax_rec( Dsd_Regular( pDsdMan->pRoots[i] ) ) );
        return Res;
    }
    else 
    {
        assert( Output >= 0 && Output < pDsdMan->nRoots );
        return Dsd_TreeNonDsdMax_rec( Dsd_Regular( pDsdMan->pRoots[Output] ) );
    }
}

Here is the call graph for this function:

◆ Dsd_TreePrint()

void Dsd_TreePrint	(	FILE *	pFile,
		Dsd_Manager_t *	pDsdMan,
		char *	pInputNames[],
		char *	pOutputNames[],
		int	fShortNames,
		int	Output,
		int	OffSet )

extern

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

Synopsis [Prints the decompostion tree into file.]

Description []

SideEffects []

SeeAlso []

Definition at line 830 of file dsdTree.c.

{
    Dsd_Node_t * pNode;
    int SigCounter;
    int i;
    SigCounter = 1;
 
    if ( Output == -1 )
    {
        for ( i = 0; i < pDsdMan->nRoots; i++ )
        {
            pNode = Dsd_Regular( pDsdMan->pRoots[i] );
            Dsd_TreePrint_rec( pFile, pNode, (pNode != pDsdMan->pRoots[i]), pInputNames, pOutputNames[i], OffSet, &SigCounter, fShortNames );
        }
    }
    else
    {
        assert( Output >= 0 && Output < pDsdMan->nRoots );
        pNode = Dsd_Regular( pDsdMan->pRoots[Output] );
        Dsd_TreePrint_rec( pFile, pNode, (pNode != pDsdMan->pRoots[Output]), pInputNames, pOutputNames[Output], OffSet, &SigCounter, fShortNames );
    }
}

Here is the caller graph for this function:

◆ Dsd_TreePrint2()

void Dsd_TreePrint2	(	FILE *	pFile,
		Dsd_Manager_t *	dMan,
		char *	pInputNames[],
		char *	pOutputNames[],
		int	Output )

extern

Definition at line 1106 of file dsdTree.c.

{
    if ( Output == -1 )
    {
        int i;
        for ( i = 0; i < pDsdMan->nRoots; i++ )
        {
            fprintf( pFile, "%8s = ", pOutputNames[i] );
            Dsd_TreePrint2_rec( pFile, pDsdMan->dd, Dsd_Regular(pDsdMan->pRoots[i]), Dsd_IsComplement(pDsdMan->pRoots[i]), pInputNames );
            fprintf( pFile, "\n" );
        }
    }
    else
    {
        assert( Output >= 0 && Output < pDsdMan->nRoots );
        fprintf( pFile, "%8s = ", pOutputNames[Output] );
        Dsd_TreePrint2_rec( pFile, pDsdMan->dd, Dsd_Regular(pDsdMan->pRoots[Output]), Dsd_IsComplement(pDsdMan->pRoots[Output]), pInputNames );
        fprintf( pFile, "\n" );
    }
}

Here is the call graph for this function:

◆ Dsd_TreePrint3()

void Dsd_TreePrint3	(	void *	pStr,
		Dsd_Manager_t *	pDsdMan,
		int	Output )

extern

Definition at line 748 of file dsdTree.c.

{
    Vec_Str_t * p = (Vec_Str_t *)pStr;
    assert( Output >= 0 && Output < pDsdMan->nRoots );
    Dsd_Node_t * pNode = Dsd_Regular( pDsdMan->pRoots[Output] );
    int fCompl = pNode != pDsdMan->pRoots[Output];
    if ( pNode->Type == DSD_NODE_CONST1 ) 
        Vec_StrPush( p, fCompl ? '0' : '1' );
    else {
        if ( fCompl )
            Vec_StrPush( p, '~' );
        Dsd_TreePrint3_rec( p, pNode );
    }    
    Vec_StrPush( p, '\0' );
}

Here is the call graph for this function:

◆ Dsd_TreePrint4()

void Dsd_TreePrint4	(	void *	pStr,
		Dsd_Manager_t *	pDsdMan,
		int	Output )

extern

Definition at line 803 of file dsdTree.c.

{
    Vec_Str_t * p = (Vec_Str_t *)pStr;
    assert( Output >= 0 && Output < pDsdMan->nRoots );
    Dsd_Node_t * pNode = Dsd_Regular( pDsdMan->pRoots[Output] );
    int fCompl = pNode != pDsdMan->pRoots[Output];
    if ( pNode->Type == DSD_NODE_CONST1 ) 
        Vec_StrPush( p, fCompl ? '0' : '1' );
    else {
        if ( fCompl ^ (pNode->Type == DSD_NODE_OR) )
            Vec_StrPush( p, '~' );
        Dsd_TreePrint4_rec( p, pNode );
    }    
    Vec_StrPush( p, '\0' );
}

Here is the call graph for this function:

◆ Dsd_TreeSuppSize()

int Dsd_TreeSuppSize	(	Dsd_Manager_t *	pDsdMan,
		int	Output )

extern

Definition at line 693 of file dsdTree.c.

{
    if ( Output == -1 ) 
    {
        int i, Res = 0;
        for ( i = 0; i < pDsdMan->nRoots; i++ )
            Res += Dsd_TreeSuppSize_rec( Dsd_Regular( pDsdMan->pRoots[i] ) );
        return Res;
    }
    else 
    {
        assert( Output >= 0 && Output < pDsdMan->nRoots );
        return Dsd_TreeSuppSize_rec( Dsd_Regular( pDsdMan->pRoots[Output] ) );
    }
}

Here is the call graph for this function:

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ Dsd_IsComplement

◆ Dsd_NodeForEachChild

◆ Dsd_Not

◆ Dsd_NotCond

◆ Dsd_Regular

Typedef Documentation

◆ Dsd_Manager_t

◆ Dsd_Node_t

◆ Dsd_Type_t

Enumeration Type Documentation

◆ Dsd_Type_t_

Function Documentation

◆ Dsd_Decompose()

◆ Dsd_DecomposeOne()

◆ Dsd_ManagerReadConst1()

◆ Dsd_ManagerReadDd()

◆ Dsd_ManagerReadInput()

◆ Dsd_ManagerReadRoot()

◆ Dsd_ManagerStart()

◆ Dsd_ManagerStop()

◆ Dsd_NodePrint()

◆ Dsd_NodeReadDec()

◆ Dsd_NodeReadDecs()

◆ Dsd_NodeReadDecsNum()

◆ Dsd_NodeReadFunc()

◆ Dsd_NodeReadMark()

◆ Dsd_NodeReadSupp()

◆ Dsd_NodeReadType()

◆ Dsd_NodeSetMark()

◆ Dsd_TreeCollectDecomposableVars()

◆ Dsd_TreeCollectNodesDfs()

◆ Dsd_TreeCollectNodesDfsOne()

◆ Dsd_TreeCountNonTerminalNodes()

◆ Dsd_TreeCountNonTerminalNodesOne()

◆ Dsd_TreeCountPrimeNodes()

◆ Dsd_TreeCountPrimeNodesOne()

◆ Dsd_TreeGetAigCost()

◆ Dsd_TreeGetPrimeFunction()

◆ Dsd_TreeNodeGetInfo()

◆ Dsd_TreeNodeGetInfoOne()

◆ Dsd_TreeNonDsdMax()

◆ Dsd_TreePrint()

◆ Dsd_TreePrint2()

◆ Dsd_TreePrint3()

◆ Dsd_TreePrint4()

◆ Dsd_TreeSuppSize()