dsd.h File Reference

Go to the source code of this file.

Macros
#define	Dsd_IsComplement(p)   (((int)((ABC_PTRUINT_T) (p) & 01)))
	MACRO DEFINITIONS ///. More...
#define	Dsd_Regular(p)   ((Dsd_Node_t *)((ABC_PTRUINT_T)(p) & ~01))
#define	Dsd_Not(p)   ((Dsd_Node_t *)((ABC_PTRUINT_T)(p) ^ 01))
#define	Dsd_NotCond(p, c)   ((Dsd_Node_t *)((ABC_PTRUINT_T)(p) ^ (c)))
#define	Dsd_NodeForEachChild(Node, Index, Child)
	ITERATORS ///. More...

Typedefs
typedef struct Dsd_Manager_t_	Dsd_Manager_t
	TYPEDEF DEFINITIONS ///. More...
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 ///. More...
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)
int	Dsd_NodeReadMark (Dsd_Node_t *p)
void	Dsd_NodeSetMark (Dsd_Node_t *p, int 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 ///. More...
void	Dsd_ManagerStop (Dsd_Manager_t *dMan)
void	Dsd_Decompose (Dsd_Manager_t *dMan, DdNode **pbFuncs, int nFuncs)
	DECOMPOSITION FUNCTIONS ///. More...
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)
void	Dsd_TreePrint2 (FILE *pFile, Dsd_Manager_t *dMan, char *pInputNames[], char *pOutputNames[], int Output)
void	Dsd_NodePrint (FILE *pFile, Dsd_Node_t *pNode)
DdNode *	Dsd_TreeGetPrimeFunction (DdManager *dd, Dsd_Node_t *pNode)
	FUNCTION DEFINITIONS ///. More...

Macro Definition Documentation

#define Dsd_IsComplement

(

p

)

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

MACRO DEFINITIONS ///.

Definition at line 68 of file dsd.h.

#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_Not

(

p

)

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

Definition at line 70 of file dsd.h.

#define Dsd_NotCond	(		p,
			c
	)		((Dsd_Node_t *)((ABC_PTRUINT_T)(p) ^ (c)))

Definition at line 71 of file dsd.h.

#define Dsd_Regular

(

p

)

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

Definition at line 69 of file dsd.h.

Typedef Documentation

typedef struct Dsd_Manager_t_ Dsd_Manager_t

TYPEDEF DEFINITIONS ///.

Definition at line 59 of file dsd.h.

typedef struct Dsd_Node_t_ Dsd_Node_t

Definition at line 60 of file dsd.h.

typedef enum Dsd_Type_t_ Dsd_Type_t

Definition at line 61 of file dsd.h.

Enumeration Type Documentation

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

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

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 );
*/
}

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

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

Synopsis [Performs decomposition for one function.]

Description []

SideEffects []

SeeAlso []

Definition at line 230 of file dsdProc.c.

{
    return dsdKernelDecompose_rec( pDsdMan, bFunc );
}

Dsd_Node_t* Dsd_ManagerReadConst1

(

Dsd_Manager_t *

pMan

)

Definition at line 95 of file dsdApi.c.

{ return pMan->pConst1;    } 

DdManager* Dsd_ManagerReadDd

(

Dsd_Manager_t *

pMan

)

Definition at line 96 of file dsdApi.c.

{ return pMan->dd;         } 

Dsd_Node_t* Dsd_ManagerReadInput	(	Dsd_Manager_t *	pMan,
		int	i
	)

Definition at line 94 of file dsdApi.c.

{ return pMan->pInputs[i]; } 

Dsd_Node_t* Dsd_ManagerReadRoot	(	Dsd_Manager_t *	pMan,
		int	i
	)

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.

{ return pMan->pRoots[i];  } 

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

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;
}

void Dsd_ManagerStop

(

Dsd_Manager_t *

dMan

)

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();
}

void Dsd_NodePrint	(	FILE *	pFile,
		Dsd_Node_t *	pNode
	)

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

Synopsis [Prints the decompostion tree into file.]

Description []

SideEffects []

SeeAlso []

Definition at line 949 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_Node_t* Dsd_NodeReadDec	(	Dsd_Node_t *	p,
		int	i
	)

Definition at line 57 of file dsdApi.c.

{ return p->pDecs[i]; } 

Dsd_Node_t** Dsd_NodeReadDecs

(

Dsd_Node_t *

p

)

Definition at line 56 of file dsdApi.c.

{ return p->pDecs;    } 

int Dsd_NodeReadDecsNum

(

Dsd_Node_t *

p

)

Definition at line 58 of file dsdApi.c.

{ return p->nDecs;    } 

DdNode* Dsd_NodeReadFunc

(

Dsd_Node_t *

p

)

Definition at line 54 of file dsdApi.c.

{ return p->G;        } 

int Dsd_NodeReadMark

(

Dsd_Node_t *

p

)

Definition at line 59 of file dsdApi.c.

{ return p->Mark;     } 

DdNode* Dsd_NodeReadSupp

(

Dsd_Node_t *

p

)

Definition at line 55 of file dsdApi.c.

{ return p->S;        } 

Dsd_Type_t Dsd_NodeReadType

(

Dsd_Node_t *

p

)

FUNCTION DEFINITIONS ///.

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.

{ return p->Type;     } 

void Dsd_NodeSetMark	(	Dsd_Node_t *	p,
		int	Mark
	)

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.

{ p->Mark = Mark;     } 

int Dsd_TreeCollectDecomposableVars	(	Dsd_Manager_t *	pDsdMan,
		int *	pVars
	)

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_Node_t** Dsd_TreeCollectNodesDfs	(	Dsd_Manager_t *	pDsdMan,
		int *	pnNodes
	)

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;
}

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

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;
}

int Dsd_TreeCountNonTerminalNodes

(

Dsd_Manager_t *

pDsdMan

)

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;
}

int Dsd_TreeCountNonTerminalNodesOne

(

Dsd_Node_t *

pRoot

)

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;
}

int Dsd_TreeCountPrimeNodes

(

Dsd_Manager_t *

pDsdMan

)

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;
}

int Dsd_TreeCountPrimeNodesOne

(

Dsd_Node_t *

pRoot

)

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;
}

int Dsd_TreeGetAigCost

(

Dsd_Node_t *

pNode

)

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) );
}

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

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;
}

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

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;
}

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

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;
}

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

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

Synopsis [Prints the decompostion tree into file.]

Description []

SideEffects []

SeeAlso []

Definition at line 641 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], 0, &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], 0, &SigCounter, fShortNames );
    }
}

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

Definition at line 917 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" );
    }
}