cut.h File Reference

Go to the source code of this file.

Data Structures
struct	Cut_ParamsStruct_t_
struct	Cut_CutStruct_t_

Macros
#define	CUT_SIZE_MIN   3
	INCLUDES ///. More...
#define	CUT_SIZE_MAX   12
#define	CUT_SHIFT   8
#define	CUT_MASK   0xFF

Typedefs
typedef struct Cut_ManStruct_t_	Cut_Man_t
	BASIC TYPES ///. More...
typedef struct Cut_OracleStruct_t_	Cut_Oracle_t
typedef struct Cut_CutStruct_t_	Cut_Cut_t
typedef struct Cut_ParamsStruct_t_	Cut_Params_t

Functions
static int	Cut_CutReadLeaveNum (Cut_Cut_t *p)
static int *	Cut_CutReadLeaves (Cut_Cut_t *p)
static unsigned *	Cut_CutReadTruth (Cut_Cut_t *p)
static void	Cut_CutWriteTruth (Cut_Cut_t *p, unsigned *puTruth)
Cut_Cut_t *	Cut_NodeReadCutsNew (Cut_Man_t *p, int Node)
	MACRO DEFINITIONS ///. More...
Cut_Cut_t *	Cut_NodeReadCutsOld (Cut_Man_t *p, int Node)
Cut_Cut_t *	Cut_NodeReadCutsTemp (Cut_Man_t *p, int Node)
void	Cut_NodeWriteCutsNew (Cut_Man_t *p, int Node, Cut_Cut_t *pList)
void	Cut_NodeWriteCutsOld (Cut_Man_t *p, int Node, Cut_Cut_t *pList)
void	Cut_NodeWriteCutsTemp (Cut_Man_t *p, int Node, Cut_Cut_t *pList)
void	Cut_NodeSetTriv (Cut_Man_t *p, int Node)
void	Cut_NodeTryDroppingCuts (Cut_Man_t *p, int Node)
void	Cut_NodeFreeCuts (Cut_Man_t *p, int Node)
void	Cut_CutPrint (Cut_Cut_t *pCut, int fSeq)
void	Cut_CutPrintList (Cut_Cut_t *pList, int fSeq)
int	Cut_CutCountList (Cut_Cut_t *pList)
Cut_Man_t *	Cut_ManStart (Cut_Params_t *pParams)
	FUNCTION DEFINITIONS ///. More...
void	Cut_ManStop (Cut_Man_t *p)
void	Cut_ManPrintStats (Cut_Man_t *p)
void	Cut_ManPrintStatsToFile (Cut_Man_t *p, char *pFileName, abctime TimeTotal)
void	Cut_ManSetFanoutCounts (Cut_Man_t *p, Vec_Int_t *vFanCounts)
void	Cut_ManSetNodeAttrs (Cut_Man_t *p, Vec_Int_t *vFanCounts)
int	Cut_ManReadVarsMax (Cut_Man_t *p)
Cut_Params_t *	Cut_ManReadParams (Cut_Man_t *p)
Vec_Int_t *	Cut_ManReadNodeAttrs (Cut_Man_t *p)
void	Cut_ManIncrementDagNodes (Cut_Man_t *p)
Cut_Cut_t *	Cut_NodeComputeCuts (Cut_Man_t *p, int Node, int Node0, int Node1, int fCompl0, int fCompl1, int fTriv, int TreeCode)
Cut_Cut_t *	Cut_NodeUnionCuts (Cut_Man_t *p, Vec_Int_t *vNodes)
Cut_Cut_t *	Cut_NodeUnionCutsSeq (Cut_Man_t *p, Vec_Int_t *vNodes, int CutSetNum, int fFirst)
int	Cut_ManMappingArea_rec (Cut_Man_t *p, int Node)
void	Cut_NodeComputeCutsSeq (Cut_Man_t *p, int Node, int Node0, int Node1, int fCompl0, int fCompl1, int nLat0, int nLat1, int fTriv, int CutSetNum)
void	Cut_NodeNewMergeWithOld (Cut_Man_t *p, int Node)
int	Cut_NodeTempTransferToNew (Cut_Man_t *p, int Node, int CutSetNum)
void	Cut_NodeOldTransferToNew (Cut_Man_t *p, int Node)
Cut_Oracle_t *	Cut_OracleStart (Cut_Man_t *pMan)
	FUNCTION DEFINITIONS ///. More...
void	Cut_OracleStop (Cut_Oracle_t *p)
void	Cut_OracleSetFanoutCounts (Cut_Oracle_t *p, Vec_Int_t *vFanCounts)
int	Cut_OracleReadDrop (Cut_Oracle_t *p)
void	Cut_OracleNodeSetTriv (Cut_Oracle_t *p, int Node)
Cut_Cut_t *	Cut_OracleComputeCuts (Cut_Oracle_t *p, int Node, int Node0, int Node1, int fCompl0, int fCompl1)
void	Cut_OracleTryDroppingCuts (Cut_Oracle_t *p, int Node)
void	Cut_TruthNCanonicize (Cut_Cut_t *pCut)
void	Cut_CellPrecompute ()
void	Cut_CellLoad ()
	FUNCTION DEFINITIONS ///. More...
int	Cut_CellIsRunning ()
void	Cut_CellDumpToFile ()
int	Cut_CellTruthLookup (unsigned *pTruth, int nVars)

Macro Definition Documentation

#define CUT_MASK   0xFF

Definition at line 42 of file cut.h.

#define CUT_SHIFT   8

Definition at line 41 of file cut.h.

#define CUT_SIZE_MAX   12

Definition at line 39 of file cut.h.

#define CUT_SIZE_MIN   3

INCLUDES ///.

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

FileName [cut.h]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [K-feasible cut computation package.]

Synopsis [External declarations.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id:

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

]PARAMETERS ///

Definition at line 38 of file cut.h.

Typedef Documentation

typedef struct Cut_CutStruct_t_ Cut_Cut_t

Definition at line 50 of file cut.h.

typedef struct Cut_ManStruct_t_ Cut_Man_t

BASIC TYPES ///.

Definition at line 48 of file cut.h.

typedef struct Cut_OracleStruct_t_ Cut_Oracle_t

Definition at line 49 of file cut.h.

typedef struct Cut_ParamsStruct_t_ Cut_Params_t

Definition at line 51 of file cut.h.

Function Documentation

void Cut_CellDumpToFile

(

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 835 of file cutPre22.c.

{
    FILE * pFile;
    Cut_CMan_t * p = s_pCMan;
    Cut_Cell_t * pTemp;
    char * pFileName = "celllib22.txt";
    int NumUsed[10][5] = {{0}};
    int BoxUsed[22][5] = {{0}};
    int i, k, Counter;
    abctime clk = Abc_Clock();

    if ( p == NULL )
    {
        printf( "Cut_CellDumpToFile: Cell manager is not defined.\n" );
        return;
    }

    // count the number of cells used
    for ( k = CUT_CELL_MVAR; k >= 0; k-- )
    {
        for ( pTemp = p->pSameVar[k]; pTemp; pTemp = pTemp->pNextVar )
        {
            if ( pTemp->nUsed == 0 )
                NumUsed[k][0]++;
            else if ( pTemp->nUsed < 10 )
                NumUsed[k][1]++;
            else if ( pTemp->nUsed < 100 )
                NumUsed[k][2]++;
            else if ( pTemp->nUsed < 1000 )
                NumUsed[k][3]++;
            else 
                NumUsed[k][4]++;

            for ( i = 0; i < 4; i++ )
                if ( pTemp->nUsed == 0 )
                    BoxUsed[ (int)pTemp->Box[i] ][0]++;
                else if ( pTemp->nUsed < 10 )
                    BoxUsed[ (int)pTemp->Box[i] ][1]++;
                else if ( pTemp->nUsed < 100 )
                    BoxUsed[ (int)pTemp->Box[i] ][2]++;
                else if ( pTemp->nUsed < 1000 )
                    BoxUsed[ (int)pTemp->Box[i] ][3]++;
                else 
                    BoxUsed[ (int)pTemp->Box[i] ][4]++;
        }
    }

    printf( "Functions found = %10d.  Functions not found = %10d.\n", p->nCellFound, p->nCellNotFound );
    for ( k = 0; k <= CUT_CELL_MVAR; k++ )
    {
        printf( "%3d  : ", k );
        for ( i = 0; i < 5; i++ ) 
            printf( "%8d ", NumUsed[k][i] );
        printf( "\n" );
    }
    printf( "Box usage:\n" );
    for ( k = 0; k < 22; k++ )
    {
        printf( "%3d  : ", k );
        for ( i = 0; i < 5; i++ ) 
            printf( "%8d ", BoxUsed[k][i] );
        printf( "  %s", s_NP3Names[k] );
        printf( "\n" );
    }

    pFile = fopen( pFileName, "w" );
    if ( pFile == NULL )
    {
        printf( "Cut_CellDumpToFile: Cannout open output file.\n" );
        return;
    }

    Counter = 0;
    for ( k = 0; k <= CUT_CELL_MVAR; k++ )
    {
        for ( pTemp = p->pSameVar[k]; pTemp; pTemp = pTemp->pNextVar )
            if ( pTemp->nUsed > 0 )
            {
                Extra_PrintHexadecimal( pFile, pTemp->uTruth, (k <= 5? 5 : k) );
                fprintf( pFile, "\n" );
                Counter++;
            }
        fprintf( pFile, "\n" );
    }
    fclose( pFile );

    printf( "Library composed of %d functions is written into file \"%s\".  ", Counter, pFileName );

    ABC_PRT( "Time", Abc_Clock() - clk );
}

int Cut_CellIsRunning

(

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 819 of file cutPre22.c.

{
    return s_pCMan != NULL;
}

void Cut_CellLoad

(

)

FUNCTION DEFINITIONS ///.

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

Synopsis [Start the precomputation manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 169 of file cutPre22.c.

{
    FILE * pFile;
    char * pFileName = "cells22_daomap_iwls.txt";
    char pString[1000];
    Cut_CMan_t * p;
    Cut_Cell_t * pCell;
    int Length; //, i;
    pFile = fopen( pFileName, "r" );
    if ( pFile == NULL )
    {
        printf( "Cannot open file \"%s\".\n", pFileName );
        return;
    }
   // start the manager
    p = Cut_CManStart();
    // load truth tables
    while ( fgets(pString, 1000, pFile) )
    {
        Length = strlen(pString);
        pString[Length--] = 0;
        if ( Length == 0 )
            continue;
        // derive the cell
        pCell = (Cut_Cell_t *)Extra_MmFixedEntryFetch( p->pMem );
        memset( pCell, 0, sizeof(Cut_Cell_t) );
        pCell->nVars = Abc_Base2Log(Length*4);
        pCell->nUsed = 1;
//        Extra_TruthCopy( pCell->uTruth, pTruth, nVars );
        Extra_ReadHexadecimal( pCell->uTruth, pString, pCell->nVars );
        Cut_CellSuppMin( pCell );
/*
        // set the elementary permutation
        for ( i = 0; i < (int)pCell->nVars; i++ )
            pCell->CanonPerm[i] = i;
        // canonicize
        pCell->CanonPhase = Extra_TruthSemiCanonicize( pCell->uTruth, p->puAux, pCell->nVars, pCell->CanonPerm, pCell->Store );
*/
        // add to the table
        p->nTotal++;

//        Extra_PrintHexadecimal( stdout, pCell->uTruth, pCell->nVars ); printf( "\n" );
//        if ( p->nTotal == 500 )
//            break;

        if ( !Cut_CellTableLookup( p, pCell ) ) // new cell
            p->nGood++;
    }
    printf( "Read %d cells from file \"%s\". Added %d cells to the table.\n", p->nTotal, pFileName, p->nGood );
    fclose( pFile );
//    return p;
}

void Cut_CellPrecompute

(

)

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

Synopsis [Precomputes truth tables for the 2x2 macro cell.]

Description []

SideEffects []

SeeAlso []

Definition at line 233 of file cutPre22.c.

{
    Cut_CMan_t * p;
    Cut_Cell_t * pCell, * pTemp;
    int i1, i2, i3, i, j, k, c;
    abctime clk = Abc_Clock(); //, clk2 = Abc_Clock();

    p = Cut_CManStart();

    // precompute truth tables
    for ( i = 0; i < 22; i++ )
        Cut_CellTruthElem( p->uInputs[0], p->uInputs[1], p->uInputs[2], p->uTemp1[i], 9, i );
    for ( i = 0; i < 22; i++ )
        Cut_CellTruthElem( p->uInputs[3], p->uInputs[4], p->uInputs[5], p->uTemp2[i], 9, i );
    for ( i = 0; i < 22; i++ )
        Cut_CellTruthElem( p->uInputs[6], p->uInputs[7], p->uInputs[8], p->uTemp3[i], 9, i );
/*
        if ( k == 8 && ((i1 == 6 && i2 == 14 && i3 == 20) || (i1 == 20 && i2 == 6 && i3 == 14)) )
        {
            Extra_PrintBinary( stdout, &pCell->CanonPhase, pCell->nVars+1 ); printf( " : " );
            for ( i = 0; i < pCell->nVars; i++ )
                printf( "%d=%d/%d  ", pCell->CanonPerm[i], pCell->Store[2*i], pCell->Store[2*i+1] );
            Extra_PrintHexadecimal( stdout, pCell->uTruth, pCell->nVars );
            printf( "\n" );
        }
*/
/*
    // go through symmetric roots
    for ( k = 0; k < 5; k++ )
    for ( i1 =  0; i1 < 22; i1++ )
    for ( i2 = i1; i2 < 22; i2++ )
    for ( i3 = i2; i3 < 22; i3++ )
    {
        // derive the cell
        pCell = (Cut_Cell_t *)Extra_MmFixedEntryFetch( p->pMem );
        memset( pCell, 0, sizeof(Cut_Cell_t) );
        pCell->nVars  = 9;
        pCell->Box[0] = s_NPNe3s[k];
        pCell->Box[1] = i1;
        pCell->Box[2] = i2;
        pCell->Box[3] = i3;
        // fill in the truth table
        Cut_CellTruthElem( p->uTemp1[i1], p->uTemp2[i2], p->uTemp3[i3], pCell->uTruth, 9, s_NPNe3s[k] );
        // canonicize
        Cut_CellCanonicize( pCell );

        // add to the table
        p->nTotal++;
        if ( Cut_CellTableLookup( p, pCell ) ) // already exists
            Extra_MmFixedEntryRecycle( p->pMem, (char *)pCell );
        else
            p->nGood++;
    }

    // go through partially symmetric roots
    for ( k = 0; k < 4; k++ )
    for ( i1 = 0;  i1 < 22; i1++ )
    for ( i2 = 0;  i2 < 22; i2++ )
    for ( i3 = i2; i3 < 22; i3++ )
    {
        // derive the cell
        pCell = (Cut_Cell_t *)Extra_MmFixedEntryFetch( p->pMem );
        memset( pCell, 0, sizeof(Cut_Cell_t) );
        pCell->nVars  = 9;
        pCell->Box[0] = s_NPNe3p[k];
        pCell->Box[1] = i1;
        pCell->Box[2] = i2;
        pCell->Box[3] = i3;
        // fill in the truth table
        Cut_CellTruthElem( p->uTemp1[i1], p->uTemp2[i2], p->uTemp3[i3], pCell->uTruth, 9, s_NPNe3p[k] );
        // canonicize
        Cut_CellCanonicize( pCell );

        // add to the table
        p->nTotal++;
        if ( Cut_CellTableLookup( p, pCell ) ) // already exists
            Extra_MmFixedEntryRecycle( p->pMem, (char *)pCell );
        else
            p->nGood++;
    }

    // go through non-symmetric functions
    for ( i1 = 0; i1 < 22; i1++ )
    for ( i2 = 0; i2 < 22; i2++ )
    for ( i3 = 0; i3 < 22; i3++ )
    {
        // derive the cell
        pCell = (Cut_Cell_t *)Extra_MmFixedEntryFetch( p->pMem );
        memset( pCell, 0, sizeof(Cut_Cell_t) );
        pCell->nVars  = 9;
        pCell->Box[0] = 17;
        pCell->Box[1] = i1;
        pCell->Box[2] = i2;
        pCell->Box[3] = i3;
        // fill in the truth table
        Cut_CellTruthElem( p->uTemp1[i1], p->uTemp2[i2], p->uTemp3[i3], pCell->uTruth, 9, 17 );
        // canonicize
        Cut_CellCanonicize( pCell );

        // add to the table
        p->nTotal++;
        if ( Cut_CellTableLookup( p, pCell ) ) // already exists
            Extra_MmFixedEntryRecycle( p->pMem, (char *)pCell );
        else
            p->nGood++;
    }
*/

    // go through non-symmetric functions
    for ( k = 0; k < 10; k++ )
    for ( i1 = 0; i1 < 22; i1++ )
    for ( i2 = 0; i2 < 22; i2++ )
    for ( i3 = 0; i3 < 22; i3++ )
    {
        // derive the cell
        pCell = (Cut_Cell_t *)Extra_MmFixedEntryFetch( p->pMem );
        memset( pCell, 0, sizeof(Cut_Cell_t) );
        pCell->nVars  = 9;
        pCell->Box[0] = s_NPNe3[k];
        pCell->Box[1] = i1;
        pCell->Box[2] = i2;
        pCell->Box[3] = i3;
        // set the elementary permutation
        for ( i = 0; i < (int)pCell->nVars; i++ )
            pCell->CanonPerm[i] = i;
        // fill in the truth table
        Cut_CellTruthElem( p->uTemp1[i1], p->uTemp2[i2], p->uTemp3[i3], pCell->uTruth, 9, s_NPNe3[k] );
        // minimize the support
        Cut_CellSuppMin( pCell );

        // canonicize
        pCell->CanonPhase = Extra_TruthSemiCanonicize( pCell->uTruth, p->puAux, pCell->nVars, pCell->CanonPerm, pCell->Store );

        // add to the table
        p->nTotal++;
        if ( Cut_CellTableLookup( p, pCell ) ) // already exists
            Extra_MmFixedEntryRecycle( p->pMem, (char *)pCell );
        else
        {
            p->nGood++;
            p->nVarCounts[pCell->nVars]++;

            if ( pCell->nVars )
            for ( i = 0; i < (int)pCell->nVars-1; i++ )
            {
                if ( pCell->Store[2*i] != pCell->Store[2*(i+1)] ) // i and i+1 cannot be symmetric
                    continue;
                // i and i+1 can be symmetric
                // find the end of this group
                for ( j = i+1; j < (int)pCell->nVars; j++ )
                    if ( pCell->Store[2*i] != pCell->Store[2*j] ) 
                        break;

                if ( pCell->Store[2*i] == pCell->Store[2*i+1] )
                    p->nSymGroupsE[j-i]++;
                else
                    p->nSymGroups[j-i]++;
                i = j - 1;
            }
/*
            if ( pCell->nVars == 3 )
            {
                Extra_PrintBinary( stdout, pCell->uTruth, 32 ); printf( "\n" );
                for ( i = 0; i < (int)pCell->nVars; i++ )
                    printf( "%d=%d/%d  ", pCell->CanonPerm[i], pCell->Store[2*i], pCell->Store[2*i+1] );
                printf( "\n" );
            }
*/
        }
    }

    printf( "BASIC: Total = %d. Good = %d. Entry = %d. ", (int)p->nTotal, (int)p->nGood, (int)sizeof(Cut_Cell_t) );
    ABC_PRT( "Time", Abc_Clock() - clk );
    printf( "Cells:  " );
    for ( i = 0; i <= 9; i++ )
        printf( "%d=%d ", i, p->nVarCounts[i] );
    printf( "\nDiffs:  " );
    for ( i = 0; i <= 9; i++ )
        printf( "%d=%d ", i, p->nSymGroups[i] );
    printf( "\nEquals: " );
    for ( i = 0; i <= 9; i++ )
        printf( "%d=%d ", i, p->nSymGroupsE[i] );
    printf( "\n" );

    // continue adding new cells using support
    for ( k = CUT_CELL_MVAR; k > 3; k-- )
    {
        for ( pTemp = p->pSameVar[k]; pTemp; pTemp = pTemp->pNextVar )
        for ( i1 = 0; i1 < k; i1++ )
        for ( i2 = i1+1; i2 < k; i2++ )
        for ( c = 0; c < 3; c++ )
        {
            // derive the cell
            pCell = (Cut_Cell_t *)Extra_MmFixedEntryFetch( p->pMem );
            memset( pCell, 0, sizeof(Cut_Cell_t) );
            pCell->nVars   = pTemp->nVars;
            pCell->pParent = pTemp;
            // set the elementary permutation
            for ( i = 0; i < (int)pCell->nVars; i++ )
                pCell->CanonPerm[i] = i;
            // fill in the truth table
            Extra_TruthCopy( pCell->uTruth, pTemp->uTruth, pTemp->nVars );
            // create the cross-bar
            pCell->CrossBar0 = i1;
            pCell->CrossBar1 = i2;
            pCell->CrossBarPhase = c;
            Cut_CellCrossBar( pCell );
            // minimize the support
//clk2 = Abc_Clock();
            Cut_CellSuppMin( pCell );
//p->timeSupp += Abc_Clock() - clk2;
            // canonicize
//clk2 = Abc_Clock();
            pCell->CanonPhase = Extra_TruthSemiCanonicize( pCell->uTruth, p->puAux, pCell->nVars, pCell->CanonPerm, pCell->Store );
//p->timeCanon += Abc_Clock() - clk2;

            // add to the table
//clk2 = Abc_Clock();
            p->nTotal++;
            if ( Cut_CellTableLookup( p, pCell ) ) // already exists
                Extra_MmFixedEntryRecycle( p->pMem, (char *)pCell );
            else
            {
                p->nGood++;
                p->nVarCounts[pCell->nVars]++;

                for ( i = 0; i < (int)pCell->nVars-1; i++ )
                {
                    if ( pCell->Store[2*i] != pCell->Store[2*(i+1)] ) // i and i+1 cannot be symmetric
                        continue;
                    // i and i+1 can be symmetric
                    // find the end of this group
                    for ( j = i+1; j < (int)pCell->nVars; j++ )
                        if ( pCell->Store[2*i] != pCell->Store[2*j] ) 
                            break;

                    if ( pCell->Store[2*i] == pCell->Store[2*i+1] )
                        p->nSymGroupsE[j-i]++;
                    else
                        p->nSymGroups[j-i]++;
                    i = j - 1;
                }
/*
                if ( pCell->nVars == 3 )
                {
                    Extra_PrintBinary( stdout, pCell->uTruth, 32 ); printf( "\n" );
                    for ( i = 0; i < (int)pCell->nVars; i++ )
                        printf( "%d=%d/%d  ", pCell->CanonPerm[i], pCell->Store[2*i], pCell->Store[2*i+1] );
                    printf( "\n" );
                }
*/
            }
//p->timeTable += Abc_Clock() - clk2;
        }

        printf( "VAR %d: Total = %d. Good = %d. Entry = %d. ", k, p->nTotal, p->nGood, (int)sizeof(Cut_Cell_t) );
        ABC_PRT( "Time", Abc_Clock() - clk );
        printf( "Cells:  " );
        for ( i = 0; i <= 9; i++ )
            printf( "%d=%d ", i, p->nVarCounts[i] );
        printf( "\nDiffs:  " );
        for ( i = 0; i <= 9; i++ )
            printf( "%d=%d ", i, p->nSymGroups[i] );
        printf( "\nEquals: " );
        for ( i = 0; i <= 9; i++ )
            printf( "%d=%d ", i, p->nSymGroupsE[i] );
        printf( "\n" );
    }
//    printf( "\n" );
    ABC_PRT( "Supp ", p->timeSupp );
    ABC_PRT( "Canon", p->timeCanon );
    ABC_PRT( "Table", p->timeTable );
//    Cut_CManStop( p );
}

int Cut_CellTruthLookup	(	unsigned *	pTruth,
		int	nVars
	)

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

Synopsis [Looks up if the given function exists in the hash table.]

Description [If the function exists, returns 1, meaning that it can be implemented using two levels of 3-input LUTs. If the function does not exist, return 0.]

SideEffects []

SeeAlso []

Definition at line 940 of file cutPre22.c.

{
    Cut_CMan_t * p = s_pCMan;
    Cut_Cell_t * pTemp;
    Cut_Cell_t Cell, * pCell = &Cell;
    unsigned Hash;
    int i;

    // cell manager is not defined
    if ( p == NULL )
    {
        printf( "Cut_CellTruthLookup: Cell manager is not defined.\n" );
        return 0;
    }

    // canonicize
    memset( pCell, 0, sizeof(Cut_Cell_t) );
    pCell->nVars = nVars;
    Extra_TruthCopy( pCell->uTruth, pTruth, nVars );
    Cut_CellSuppMin( pCell );
    // set the elementary permutation
    for ( i = 0; i < (int)pCell->nVars; i++ )
        pCell->CanonPerm[i] = i;
    // canonicize
    pCell->CanonPhase = Extra_TruthSemiCanonicize( pCell->uTruth, p->puAux, pCell->nVars, pCell->CanonPerm, pCell->Store );


    // check if the cell exists
    Hash = Extra_TruthHash( pCell->uTruth, Extra_TruthWordNum(pCell->nVars) );
    if ( st__lookup( p->tTable, (char *)(ABC_PTRUINT_T)Hash, (char **)&pTemp ) )
    {
        for ( ; pTemp; pTemp = pTemp->pNext )
        {
            if ( pTemp->nVars != pCell->nVars )
                continue;
            if ( Extra_TruthIsEqual(pTemp->uTruth, pCell->uTruth, pCell->nVars) )
            {
                pTemp->nUsed++;
                p->nCellFound++;
                return 1;
            }
        }
    }
    p->nCellNotFound++;
    return 0;
}

int Cut_CutCountList

(

Cut_Cut_t *

pList

)

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

Synopsis [Counts the number of cuts in the list.]

Description []

SideEffects []

SeeAlso []

Definition at line 166 of file cutCut.c.

{
    int Counter = 0;
    Cut_ListForEachCut( pList, pList )
        Counter++;
    return Counter;
}

void Cut_CutPrint	(	Cut_Cut_t *	pCut,
		int	fSeq
	)

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

Synopsis [Print the cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 276 of file cutCut.c.

{
    int i;
    assert( pCut->nLeaves > 0 );
    printf( "%d : {", pCut->nLeaves );
    for ( i = 0; i < (int)pCut->nLeaves; i++ )
    {
        if ( fSeq )
        {
            printf( " %d", pCut->pLeaves[i] >> CUT_SHIFT );
            if ( pCut->pLeaves[i] & CUT_MASK )
                printf( "(%d)", pCut->pLeaves[i] & CUT_MASK );
        }
        else
            printf( " %d", pCut->pLeaves[i] );
    }
    printf( " }" );
//    printf( "\nSign = " );
//    Extra_PrintBinary( stdout, &pCut->uSign, 32 );
}

void Cut_CutPrintList	(	Cut_Cut_t *	pList,
		int	fSeq
	)

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

Synopsis [Print the cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 308 of file cutCut.c.

{
    Cut_Cut_t * pCut;
    for ( pCut = pList; pCut; pCut = pCut->pNext )
        Cut_CutPrint( pCut, fSeq ), printf( "\n" );
}

static int Cut_CutReadLeaveNum ( Cut_Cut_t *  p )

inlinestatic

Definition at line 92 of file cut.h.

{  return p->nLeaves;   }

static int* Cut_CutReadLeaves ( Cut_Cut_t *  p )

inlinestatic

Definition at line 93 of file cut.h.

{  return p->pLeaves;   }

static unsigned* Cut_CutReadTruth ( Cut_Cut_t *  p )

inlinestatic

Definition at line 94 of file cut.h.

{  return (unsigned *)(p->pLeaves + p->nVarsMax); }

static void Cut_CutWriteTruth ( Cut_Cut_t *  p, unsigned *  puTruth  )

inlinestatic

Definition at line 95 of file cut.h.

                                                                                 { 
    int i;
    for ( i = (p->nVarsMax <= 5) ? 0 : ((1 << (p->nVarsMax - 5)) - 1); i >= 0; i-- )
        p->pLeaves[p->nVarsMax + i] = (int)puTruth[i];
}

void Cut_ManIncrementDagNodes

(

Cut_Man_t *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 309 of file cutMan.c.

{
    p->nNodesDag++;
}

int Cut_ManMappingArea_rec	(	Cut_Man_t *	p,
		int	Node
	)

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

Synopsis [Computes area after mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 544 of file cutNode.c.

{
    Cut_Cut_t * pCut;
    int i, Counter;
    if ( p->vCutsMax == NULL )
        return 0;
    pCut = (Cut_Cut_t *)Vec_PtrEntry( p->vCutsMax, Node );
    if ( pCut == NULL || pCut->nLeaves == 1 )
        return 0;
    Counter = 0;
    for ( i = 0; i < (int)pCut->nLeaves; i++ )
        Counter += Cut_ManMappingArea_rec( p, pCut->pLeaves[i] );
    Vec_PtrWriteEntry( p->vCutsMax, Node, NULL );
    return 1 + Counter;
}

void Cut_ManPrintStats

(

Cut_Man_t *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 155 of file cutMan.c.

{
    if ( p->pReady )
    {
        Cut_CutRecycle( p, p->pReady );
        p->pReady = NULL;
    }
    printf( "Cut computation statistics:\n" );
    printf( "Current cuts      = %8d. (Trivial = %d.)\n", p->nCutsCur-p->nCutsTriv, p->nCutsTriv );
    printf( "Peak cuts         = %8d.\n", p->nCutsPeak );
    printf( "Total allocated   = %8d.\n", p->nCutsAlloc );
    printf( "Total deallocated = %8d.\n", p->nCutsDealloc );
    printf( "Cuts filtered     = %8d.\n", p->nCutsFilter );
    printf( "Nodes saturated   = %8d. (Max cuts = %d.)\n", p->nCutsLimit, p->pParams->nKeepMax );
    printf( "Cuts per node     = %8.1f\n", ((float)(p->nCutsCur-p->nCutsTriv))/p->nNodes );
    printf( "The cut size      = %8d bytes.\n", p->EntrySize );
    printf( "Peak memory       = %8.2f MB.\n", (float)p->nCutsPeak * p->EntrySize / (1<<20) );
    printf( "Total nodes       = %8d.\n", p->nNodes );
    if ( p->pParams->fDag || p->pParams->fTree )
    {
    printf( "DAG nodes         = %8d.\n", p->nNodesDag );
    printf( "Tree nodes        = %8d.\n", p->nNodes - p->nNodesDag );
    }
    printf( "Nodes w/o cuts    = %8d.\n", p->nNodesNoCuts );
    if ( p->pParams->fMap && !p->pParams->fSeq )
    printf( "Mapping delay     = %8d.\n", p->nDelayMin );

    ABC_PRT( "Merge ", p->timeMerge );
    ABC_PRT( "Union ", p->timeUnion );
    ABC_PRT( "Filter", p->timeFilter );
    ABC_PRT( "Truth ", p->timeTruth );
    ABC_PRT( "Map   ", p->timeMap );
//    printf( "Nodes = %d. Multi = %d.  Cuts = %d. Multi = %d.\n", 
//        p->nNodes, p->nNodesMulti, p->nCutsCur-p->nCutsTriv, p->nCutsMulti );
//    printf( "Count0 = %d. Count1 = %d. Count2 = %d.\n\n", p->Count0, p->Count1, p->Count2 );
}

void Cut_ManPrintStatsToFile	(	Cut_Man_t *	p,
		char *	pFileName,
		abctime	TimeTotal
	)

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

Synopsis [Prints some interesting stats.]

Description []

SideEffects []

SeeAlso []

Definition at line 204 of file cutMan.c.

{
    FILE * pTable;
    pTable = fopen( "cut_stats.txt", "a+" );
    fprintf( pTable, "%-20s ", pFileName );
    fprintf( pTable, "%8d ", p->nNodes );
    fprintf( pTable, "%6.1f ", ((float)(p->nCutsCur))/p->nNodes );
    fprintf( pTable, "%6.2f ", ((float)(100.0 * p->nCutsLimit))/p->nNodes );
    fprintf( pTable, "%6.2f ", (float)p->nCutsPeak * p->EntrySize / (1<<20) );
    fprintf( pTable, "%6.2f ", (float)(TimeTotal)/(float)(CLOCKS_PER_SEC) );
    fprintf( pTable, "\n" );
    fclose( pTable );
}

Vec_Int_t* Cut_ManReadNodeAttrs

(

Cut_Man_t *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 293 of file cutMan.c.

{
    return p->vNodeAttrs;
}

Cut_Params_t* Cut_ManReadParams

(

Cut_Man_t *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 277 of file cutMan.c.

{
    return p->pParams;
}

int Cut_ManReadVarsMax

(

Cut_Man_t *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 261 of file cutMan.c.

{
    return p->pParams->nVarsMax;
}

void Cut_ManSetFanoutCounts	(	Cut_Man_t *	p,
		Vec_Int_t *	vFanCounts
	)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 229 of file cutMan.c.

{
    p->vFanCounts = vFanCounts;
}

void Cut_ManSetNodeAttrs	(	Cut_Man_t *	p,
		Vec_Int_t *	vNodeAttrs
	)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 245 of file cutMan.c.

{
    p->vNodeAttrs = vNodeAttrs;
}

Cut_Man_t* Cut_ManStart

(

Cut_Params_t *

pParams

)

FUNCTION DEFINITIONS ///.

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

Synopsis [Starts the cut manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 47 of file cutMan.c.

{
    Cut_Man_t * p;
//    extern int nTruthDsd;
//    nTruthDsd = 0;
    assert( pParams->nVarsMax >= 3 && pParams->nVarsMax <= CUT_SIZE_MAX );
    p = ABC_ALLOC( Cut_Man_t, 1 );
    memset( p, 0, sizeof(Cut_Man_t) );
    // set and correct parameters
    p->pParams = pParams;
    // prepare storage for cuts
    p->vCutsNew = Vec_PtrAlloc( pParams->nIdsMax );
    Vec_PtrFill( p->vCutsNew, pParams->nIdsMax, NULL );
    // prepare storage for sequential cuts
    if ( pParams->fSeq )
    {
        p->pParams->fFilter = 1;
        p->vCutsOld = Vec_PtrAlloc( pParams->nIdsMax );
        Vec_PtrFill( p->vCutsOld, pParams->nIdsMax, NULL );
        p->vCutsTemp = Vec_PtrAlloc( pParams->nCutSet );
        Vec_PtrFill( p->vCutsTemp, pParams->nCutSet, NULL );
        if ( pParams->fTruth && pParams->nVarsMax > 5 )
        {
            pParams->fTruth = 0;
            printf( "Skipping computation of truth tables for sequential cuts with more than 5 inputs.\n" );
        }
    }
    // entry size
    p->EntrySize = sizeof(Cut_Cut_t) + pParams->nVarsMax * sizeof(int);
    if ( pParams->fTruth )
    {
        if ( pParams->nVarsMax > 14 )
        {
            pParams->fTruth = 0;
            printf( "Skipping computation of truth table for more than %d inputs.\n", 14 );
        }
        else
        {
            p->nTruthWords = Cut_TruthWords( pParams->nVarsMax );
            p->EntrySize += p->nTruthWords * sizeof(unsigned);
        }
        p->puTemp[0] = ABC_ALLOC( unsigned, 4 * p->nTruthWords );
        p->puTemp[1] = p->puTemp[0] + p->nTruthWords;
        p->puTemp[2] = p->puTemp[1] + p->nTruthWords;
        p->puTemp[3] = p->puTemp[2] + p->nTruthWords;
    }
    // enable cut computation recording
    if ( pParams->fRecord )
    {
        p->vNodeCuts   = Vec_IntStart( pParams->nIdsMax );
        p->vNodeStarts = Vec_IntStart( pParams->nIdsMax );
        p->vCutPairs   = Vec_IntAlloc( 0 );
    }
    // allocate storage for delays
    if ( pParams->fMap && !p->pParams->fSeq )
    {
        p->vDelays = Vec_IntStart( pParams->nIdsMax );
        p->vDelays2 = Vec_IntStart( pParams->nIdsMax );
        p->vCutsMax = Vec_PtrStart( pParams->nIdsMax );
    }
    // memory for cuts
    p->pMmCuts = Extra_MmFixedStart( p->EntrySize );
    p->vTemp = Vec_PtrAlloc( 100 );
    return p;
}

void Cut_ManStop

(

Cut_Man_t *

p

)

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

Synopsis [Stops the cut manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 124 of file cutMan.c.

{
    if ( p->vCutsNew )    Vec_PtrFree( p->vCutsNew );
    if ( p->vCutsOld )    Vec_PtrFree( p->vCutsOld );
    if ( p->vCutsTemp )   Vec_PtrFree( p->vCutsTemp );
    if ( p->vFanCounts )  Vec_IntFree( p->vFanCounts );
    if ( p->vTemp )       Vec_PtrFree( p->vTemp );

    if ( p->vCutsMax )    Vec_PtrFree( p->vCutsMax );
    if ( p->vDelays )     Vec_IntFree( p->vDelays );
    if ( p->vDelays2 )    Vec_IntFree( p->vDelays2 );
    if ( p->vNodeCuts )   Vec_IntFree( p->vNodeCuts );
    if ( p->vNodeStarts ) Vec_IntFree( p->vNodeStarts );
    if ( p->vCutPairs )   Vec_IntFree( p->vCutPairs );
    if ( p->puTemp[0] )   ABC_FREE( p->puTemp[0] );

    Extra_MmFixedStop( p->pMmCuts );
    ABC_FREE( p );
}

Cut_Cut_t* Cut_NodeComputeCuts	(	Cut_Man_t *	p,
		int	Node,
		int	Node0,
		int	Node1,
		int	fCompl0,
		int	fCompl1,
		int	fTriv,
		int	TreeCode
	)

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

Synopsis [Computes the cuts by merging cuts at two nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 369 of file cutNode.c.

{
    Cut_List_t Super, * pSuper = &Super;
    Cut_Cut_t * pList, * pCut;
    abctime clk;
    // start the number of cuts at the node
    p->nNodes++;
    p->nNodeCuts = 0;
    // prepare information for recording
    if ( p->pParams->fRecord )
    {
        Cut_CutNumberList( Cut_NodeReadCutsNew(p, Node0) );
        Cut_CutNumberList( Cut_NodeReadCutsNew(p, Node1) );
    }
    // compute the cuts
clk = Abc_Clock();
    Cut_ListStart( pSuper );
    Cut_NodeDoComputeCuts( p, pSuper, Node, fCompl0, fCompl1, Cut_NodeReadCutsNew(p, Node0), Cut_NodeReadCutsNew(p, Node1), fTriv, TreeCode );
    pList = Cut_ListFinish( pSuper );
p->timeMerge += Abc_Clock() - clk;
    // verify the result of cut computation
//    Cut_CutListVerify( pList );
    // performing the recording
    if ( p->pParams->fRecord )
    {
        Vec_IntWriteEntry( p->vNodeStarts, Node, Vec_IntSize(p->vCutPairs) );
        Cut_ListForEachCut( pList, pCut )
            Vec_IntPush( p->vCutPairs, ((pCut->Num1 << 16) | pCut->Num0) );
        Vec_IntWriteEntry( p->vNodeCuts, Node, Vec_IntSize(p->vCutPairs) - Vec_IntEntry(p->vNodeStarts, Node) );
    }
    if ( p->pParams->fRecordAig )
    {
        extern void Aig_RManRecord( unsigned * pTruth, int nVarsInit );
        Cut_ListForEachCut( pList, pCut )
            if ( Cut_CutReadLeaveNum(pCut) > 4 )
                Aig_RManRecord( Cut_CutReadTruth(pCut), Cut_CutReadLeaveNum(pCut) );
    }
    // check if the node is over the list
    if ( p->nNodeCuts == p->pParams->nKeepMax )
        p->nCutsLimit++;
    // set the list at the node
    Vec_PtrFillExtra( p->vCutsNew, Node + 1, NULL );
    assert( Cut_NodeReadCutsNew(p, Node) == NULL );
    /////
//    pList->pNext = NULL;
    /////
    Cut_NodeWriteCutsNew( p, Node, pList );
    // filter the cuts
//clk = Abc_Clock();
//    if ( p->pParams->fFilter )
//        Cut_CutFilter( p, pList0 );
//p->timeFilter += Abc_Clock() - clk;
    // perform mapping of this node with these cuts
clk = Abc_Clock();
    if ( p->pParams->fMap && !p->pParams->fSeq )
    {
//        int Delay1, Delay2;
//        Delay1 = Cut_NodeMapping( p, pList, Node, Node0, Node1 );    
//        Delay2 = Cut_NodeMapping2( p, pList, Node, Node0, Node1 );   
//        assert( Delay1 >= Delay2 );
        Cut_NodeMapping( p, pList, Node, Node0, Node1 );
    }
p->timeMap += Abc_Clock() - clk;
    return pList;
}

void Cut_NodeComputeCutsSeq	(	Cut_Man_t *	p,
		int	Node,
		int	Node0,
		int	Node1,
		int	fCompl0,
		int	fCompl1,
		int	nLat0,
		int	nLat1,
		int	fTriv,
		int	CutSetNum
	)

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

Synopsis [Computes sequential cuts for the node from its fanins.]

Description []

SideEffects []

SeeAlso []

Definition at line 72 of file cutSeq.c.

{
    Cut_List_t Super, * pSuper = &Super;
    Cut_Cut_t * pListNew;
    abctime clk;
    
    // get the number of cuts at the node
    p->nNodeCuts = Cut_CutCountList( Cut_NodeReadCutsOld(p, Node) );
    if ( p->nNodeCuts >= p->pParams->nKeepMax )
        return;

    // count only the first visit
    if ( p->nNodeCuts == 0 )
        p->nNodes++;

    // store the fanin lists
    p->pStore0[0] = Cut_NodeReadCutsOld( p, Node0 );
    p->pStore0[1] = Cut_NodeReadCutsNew( p, Node0 );
    p->pStore1[0] = Cut_NodeReadCutsOld( p, Node1 );
    p->pStore1[1] = Cut_NodeReadCutsNew( p, Node1 );

    // duplicate the cut lists if fanin nodes are non-standard
    if ( Node == Node0 || Node == Node1 || Node0 == Node1 )
    {
        p->pStore0[0] = Cut_CutDupList( p, p->pStore0[0] );
        p->pStore0[1] = Cut_CutDupList( p, p->pStore0[1] );
        p->pStore1[0] = Cut_CutDupList( p, p->pStore1[0] );
        p->pStore1[1] = Cut_CutDupList( p, p->pStore1[1] );
    }

    // shift the cuts by as many latches and recompute signatures
    if ( nLat0 ) Cut_NodeShiftCutLeaves( p->pStore0[0], nLat0 );
    if ( nLat0 ) Cut_NodeShiftCutLeaves( p->pStore0[1], nLat0 );
    if ( nLat1 ) Cut_NodeShiftCutLeaves( p->pStore1[0], nLat1 );
    if ( nLat1 ) Cut_NodeShiftCutLeaves( p->pStore1[1], nLat1 );

    // store the original lists for comparison
    p->pCompareOld = Cut_NodeReadCutsOld( p, Node );
    p->pCompareNew = Cut_NodeReadCutsNew( p, Node );

    // merge the old and the new
clk = Abc_Clock();
    Cut_ListStart( pSuper );
    Cut_NodeDoComputeCuts( p, pSuper, Node, fCompl0, fCompl1, p->pStore0[0], p->pStore1[1], 0, 0 );
    Cut_NodeDoComputeCuts( p, pSuper, Node, fCompl0, fCompl1, p->pStore0[1], p->pStore1[0], 0, 0 );
    Cut_NodeDoComputeCuts( p, pSuper, Node, fCompl0, fCompl1, p->pStore0[1], p->pStore1[1], fTriv, 0 );
    pListNew = Cut_ListFinish( pSuper );
p->timeMerge += Abc_Clock() - clk;

    // shift the cuts by as many latches and recompute signatures
    if ( Node == Node0 || Node == Node1 || Node0 == Node1 )
    {
        Cut_CutRecycleList( p, p->pStore0[0] );
        Cut_CutRecycleList( p, p->pStore0[1] );
        Cut_CutRecycleList( p, p->pStore1[0] );
        Cut_CutRecycleList( p, p->pStore1[1] );
    }
    else
    {
        if ( nLat0 ) Cut_NodeShiftCutLeaves( p->pStore0[0], -nLat0 );
        if ( nLat0 ) Cut_NodeShiftCutLeaves( p->pStore0[1], -nLat0 );
        if ( nLat1 ) Cut_NodeShiftCutLeaves( p->pStore1[0], -nLat1 );
        if ( nLat1 ) Cut_NodeShiftCutLeaves( p->pStore1[1], -nLat1 );
    }

    // set the lists at the node
    if ( CutSetNum >= 0 )
    {
        assert( Cut_NodeReadCutsTemp(p, CutSetNum) == NULL );
        Cut_NodeWriteCutsTemp( p, CutSetNum, pListNew );
    }
    else
    {
        assert( Cut_NodeReadCutsNew(p, Node) == NULL );
        Cut_NodeWriteCutsNew( p, Node, pListNew );
    }

    // mark the node if we exceeded the number of cuts
    if ( p->nNodeCuts >= p->pParams->nKeepMax )
        p->nCutsLimit++;
}

void Cut_NodeFreeCuts	(	Cut_Man_t *	p,
		int	Node
	)

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

Synopsis [Deallocates the cuts at the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 184 of file cutApi.c.

{
    Cut_Cut_t * pList, * pCut, * pCut2;
    pList = Cut_NodeReadCutsNew( p, Node );
    if ( pList == NULL )
        return;
    Cut_ListForEachCutSafe( pList, pCut, pCut2 )
        Cut_CutRecycle( p, pCut );
    Cut_NodeWriteCutsNew( p, Node, NULL );
}

void Cut_NodeNewMergeWithOld	(	Cut_Man_t *	p,
		int	Node
	)

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

Synopsis [Merges the new cuts with the old cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 165 of file cutSeq.c.

{
    Cut_Cut_t * pListOld, * pListNew, * pList;
    // get the new cuts
    pListNew = Cut_NodeReadCutsNew( p, Node );
    if ( pListNew == NULL )
        return;
    Cut_NodeWriteCutsNew( p, Node, NULL );
    // get the old cuts
    pListOld = Cut_NodeReadCutsOld( p, Node );
    if ( pListOld == NULL )
    {
        Cut_NodeWriteCutsOld( p, Node, pListNew );
        return;
    }
    // merge the lists
    pList = Cut_CutMergeLists( pListOld, pListNew );
    Cut_NodeWriteCutsOld( p, Node, pList );
}

void Cut_NodeOldTransferToNew	(	Cut_Man_t *	p,
		int	Node
	)

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

Synopsis [Transfers the old cuts to be the new cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 217 of file cutSeq.c.

{
    Cut_Cut_t * pList;
    pList = Cut_NodeReadCutsOld( p, Node );
    Cut_NodeWriteCutsOld( p, Node, NULL );
    Cut_NodeWriteCutsNew( p, Node, pList );
//    Cut_CutListVerify( pList );
}

Cut_Cut_t* Cut_NodeReadCutsNew	(	Cut_Man_t *	p,
		int	Node
	)

MACRO DEFINITIONS ///.

FUNCTION DECLARATIONS ///

MACRO DEFINITIONS ///.

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

FileName [cutNode.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [K-feasible cut computation package.]

Synopsis [Procedures to compute cuts for a node.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id:

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

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

Synopsis [Returns the pointer to the linked list of cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file cutApi.c.

{
    if ( Node >= p->vCutsNew->nSize )
        return NULL;
    return (Cut_Cut_t *)Vec_PtrEntry( p->vCutsNew, Node );
}

Cut_Cut_t* Cut_NodeReadCutsOld	(	Cut_Man_t *	p,
		int	Node
	)

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

Synopsis [Returns the pointer to the linked list of cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 63 of file cutApi.c.

{
    assert( Node < p->vCutsOld->nSize );
    return (Cut_Cut_t *)Vec_PtrEntry( p->vCutsOld, Node );
}

Cut_Cut_t* Cut_NodeReadCutsTemp	(	Cut_Man_t *	p,
		int	Node
	)

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

Synopsis [Returns the pointer to the linked list of cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 80 of file cutApi.c.

{
    assert( Node < p->vCutsTemp->nSize );
    return (Cut_Cut_t *)Vec_PtrEntry( p->vCutsTemp, Node );
}

void Cut_NodeSetTriv	(	Cut_Man_t *	p,
		int	Node
	)

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

Synopsis [Sets the trivial cut for the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 145 of file cutApi.c.

{
    assert( Cut_NodeReadCutsNew(p, Node) == NULL );
    Cut_NodeWriteCutsNew( p, Node, Cut_CutCreateTriv(p, Node) );
}

int Cut_NodeTempTransferToNew	(	Cut_Man_t *	p,
		int	Node,
		int	CutSetNum
	)

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

Synopsis [Transfers the temporary cuts to be the new cuts.]

Description [Returns 1 if something was transferred.]

SideEffects []

SeeAlso []

Definition at line 197 of file cutSeq.c.

{
    Cut_Cut_t * pList;
    pList = Cut_NodeReadCutsTemp( p, CutSetNum );
    Cut_NodeWriteCutsTemp( p, CutSetNum, NULL );
    Cut_NodeWriteCutsNew( p, Node, pList );
    return pList != NULL;
}

void Cut_NodeTryDroppingCuts	(	Cut_Man_t *	p,
		int	Node
	)

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

Synopsis [Consider dropping cuts if they are useless by now.]

Description []

SideEffects []

SeeAlso []

Definition at line 162 of file cutApi.c.

{
    int nFanouts;
    assert( p->vFanCounts );
    nFanouts = Vec_IntEntry( p->vFanCounts, Node );
    assert( nFanouts > 0 );
    if ( --nFanouts == 0 )
        Cut_NodeFreeCuts( p, Node );
    Vec_IntWriteEntry( p->vFanCounts, Node, nFanouts );
}

Cut_Cut_t* Cut_NodeUnionCuts	(	Cut_Man_t *	p,
		Vec_Int_t *	vNodes
	)

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

Synopsis [Computes the cuts by unioning cuts at a choice node.]

Description []

SideEffects []

SeeAlso []

Definition at line 678 of file cutNode.c.

{
    Cut_List_t Super, * pSuper = &Super;
    Cut_Cut_t * pList, * pListStart, * pCut, * pCut2;
    Cut_Cut_t * pTop = NULL; // Suppress "might be used uninitialized"
    int i, k, Node, Root, Limit = p->pParams->nVarsMax;
    abctime clk = Abc_Clock();

    // start the new list
    Cut_ListStart( pSuper );

    // remember the root node to save the resulting cuts
    Root = Vec_IntEntry( vNodes, 0 );
    p->nNodeCuts = 1;

    // collect small cuts first
    Vec_PtrClear( p->vTemp );
    Vec_IntForEachEntry( vNodes, Node, i )
    {
        // get the cuts of this node
        pList = Cut_NodeReadCutsNew( p, Node );
        Cut_NodeWriteCutsNew( p, Node, NULL );
        assert( pList );
        // remember the starting point
        pListStart = pList->pNext;
        pList->pNext = NULL;
        // save or recycle the elementary cut
        if ( i == 0 )
            Cut_ListAdd( pSuper, pList ), pTop = pList;
        else
            Cut_CutRecycle( p, pList );
        // save all the cuts that are smaller than the limit
        Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
        {
            if ( pCut->nLeaves == (unsigned)Limit )
            {
                Vec_PtrPush( p->vTemp, pCut );
                break;
            }
            // check containment
            if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) )
                continue;
            // set the complemented bit by comparing the first cut with the current cut
            pCut->fCompl = pTop->fSimul ^ pCut->fSimul;
            pListStart = pCut->pNext;
            pCut->pNext = NULL;
            // add to the list
            Cut_ListAdd( pSuper, pCut );
            if ( ++p->nNodeCuts == p->pParams->nKeepMax )
            {
                // recycle the rest of the cuts of this node
                Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
                    Cut_CutRecycle( p, pCut );
                // recycle all cuts of other nodes
                Vec_IntForEachEntryStart( vNodes, Node, k, i+1 )
                    Cut_NodeFreeCuts( p, Node );
                // recycle the saved cuts of other nodes
                Vec_PtrForEachEntry( Cut_Cut_t *, p->vTemp, pList, k )
                    Cut_ListForEachCutSafe( pList, pCut, pCut2 )
                        Cut_CutRecycle( p, pCut );
                goto finish;
            }
        }
    } 
    // collect larger cuts next
    Vec_PtrForEachEntry( Cut_Cut_t *, p->vTemp, pList, i )
    {
        Cut_ListForEachCutSafe( pList, pCut, pCut2 )
        {
            // check containment
            if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) )
                continue;
            // set the complemented bit
            pCut->fCompl = pTop->fSimul ^ pCut->fSimul;
            pListStart = pCut->pNext;
            pCut->pNext = NULL;
            // add to the list
            Cut_ListAdd( pSuper, pCut );
            if ( ++p->nNodeCuts == p->pParams->nKeepMax )
            {
                // recycle the rest of the cuts
                Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
                    Cut_CutRecycle( p, pCut );
                // recycle the saved cuts of other nodes
                Vec_PtrForEachEntryStart( Cut_Cut_t *, p->vTemp, pList, k, i+1 )
                    Cut_ListForEachCutSafe( pList, pCut, pCut2 )
                        Cut_CutRecycle( p, pCut );
                goto finish;
            }
        }
    }
finish :
    // set the cuts at the node
    assert( Cut_NodeReadCutsNew(p, Root) == NULL );
    pList = Cut_ListFinish( pSuper );
    Cut_NodeWriteCutsNew( p, Root, pList );
p->timeUnion += Abc_Clock() - clk;
    // filter the cuts
//clk = Abc_Clock();
//    if ( p->pParams->fFilter )
//        Cut_CutFilter( p, pList );
//p->timeFilter += Abc_Clock() - clk;
    p->nNodes -= vNodes->nSize - 1;
    return pList;
}

Cut_Cut_t* Cut_NodeUnionCutsSeq	(	Cut_Man_t *	p,
		Vec_Int_t *	vNodes,
		int	CutSetNum,
		int	fFirst
	)

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

Synopsis [Computes the cuts by unioning cuts at a choice node.]

Description []

SideEffects []

SeeAlso []

Definition at line 795 of file cutNode.c.

{
    Cut_List_t Super, * pSuper = &Super;
    Cut_Cut_t * pList, * pListStart, * pCut, * pCut2, * pTop;
    int i, k, Node, Root, Limit = p->pParams->nVarsMax;
    abctime clk = Abc_Clock();

    // start the new list
    Cut_ListStart( pSuper );

    // remember the root node to save the resulting cuts
    Root = Vec_IntEntry( vNodes, 0 );
    p->nNodeCuts = 1;

    // store the original lists for comparison
    p->pCompareOld = Cut_NodeReadCutsOld( p, Root );
    p->pCompareNew = (CutSetNum >= 0)? Cut_NodeReadCutsNew( p, Root ) : NULL;

    // get the topmost cut
    pTop = NULL;
    if ( (pTop = Cut_NodeReadCutsOld( p, Root )) == NULL )
        pTop = Cut_NodeReadCutsNew( p, Root );
    assert( pTop != NULL );

    // collect small cuts first
    Vec_PtrClear( p->vTemp );
    Vec_IntForEachEntry( vNodes, Node, i )
    {
        // get the cuts of this node
        if ( i == 0 && CutSetNum >= 0 )
        {
            pList = Cut_NodeReadCutsTemp( p, CutSetNum );
            Cut_NodeWriteCutsTemp( p, CutSetNum, NULL );
        }
        else
        {
            pList = Cut_NodeReadCutsNew( p, Node );
            Cut_NodeWriteCutsNew( p, Node, NULL );
        }
        if ( pList == NULL )
            continue;

        // process the cuts
        if ( fFirst )
        {
            // remember the starting point
            pListStart = pList->pNext;
            pList->pNext = NULL;
            // save or recycle the elementary cut
            if ( i == 0 )
                Cut_ListAdd( pSuper, pList );
            else
                Cut_CutRecycle( p, pList );
        }
        else
            pListStart = pList;

        // save all the cuts that are smaller than the limit
        Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
        {
            if ( pCut->nLeaves == (unsigned)Limit )
            {
                Vec_PtrPush( p->vTemp, pCut );
                break;
            }
            // check containment
//            if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) )
//                continue;
            if ( p->pParams->fFilter )
            {
                if ( Cut_CutFilterOne(p, pSuper, pCut) )
                    continue;
                if ( p->pParams->fSeq )
                {
                    if ( p->pCompareOld && Cut_CutFilterOld(p, p->pCompareOld, pCut) )
                        continue;
                    if ( p->pCompareNew && Cut_CutFilterOld(p, p->pCompareNew, pCut) )
                        continue;
                }
            }

            // set the complemented bit by comparing the first cut with the current cut
            pCut->fCompl = pTop->fSimul ^ pCut->fSimul;
            pListStart = pCut->pNext;
            pCut->pNext = NULL;
            // add to the list
            Cut_ListAdd( pSuper, pCut );
            if ( ++p->nNodeCuts == p->pParams->nKeepMax )
            {
                // recycle the rest of the cuts of this node
                Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
                    Cut_CutRecycle( p, pCut );
                // recycle all cuts of other nodes
                Vec_IntForEachEntryStart( vNodes, Node, k, i+1 )
                    Cut_NodeFreeCuts( p, Node );
                // recycle the saved cuts of other nodes
                Vec_PtrForEachEntry( Cut_Cut_t *, p->vTemp, pList, k )
                    Cut_ListForEachCutSafe( pList, pCut, pCut2 )
                        Cut_CutRecycle( p, pCut );
                goto finish;
            }
        }
    } 
    // collect larger cuts next
    Vec_PtrForEachEntry( Cut_Cut_t *, p->vTemp, pList, i )
    {
        Cut_ListForEachCutSafe( pList, pCut, pCut2 )
        {
            // check containment
//            if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) )
//                continue;
            if ( p->pParams->fFilter )
            {
                if ( Cut_CutFilterOne(p, pSuper, pCut) )
                    continue;
                if ( p->pParams->fSeq )
                {
                    if ( p->pCompareOld && Cut_CutFilterOld(p, p->pCompareOld, pCut) )
                        continue;
                    if ( p->pCompareNew && Cut_CutFilterOld(p, p->pCompareNew, pCut) )
                        continue;
                }
            }

            // set the complemented bit
            pCut->fCompl = pTop->fSimul ^ pCut->fSimul;
            pListStart   = pCut->pNext;
            pCut->pNext  = NULL;
            // add to the list
            Cut_ListAdd( pSuper, pCut );
            if ( ++p->nNodeCuts == p->pParams->nKeepMax )
            {
                // recycle the rest of the cuts
                Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
                    Cut_CutRecycle( p, pCut );
                // recycle the saved cuts of other nodes
                Vec_PtrForEachEntryStart( Cut_Cut_t *, p->vTemp, pList, k, i+1 )
                    Cut_ListForEachCutSafe( pList, pCut, pCut2 )
                        Cut_CutRecycle( p, pCut );
                goto finish;
            }
        }
    }
finish :
    // set the cuts at the node
    pList = Cut_ListFinish( pSuper );

    // set the lists at the node
//    assert( Cut_NodeReadCutsNew(p, Root) == NULL );
//    Cut_NodeWriteCutsNew( p, Root, pList );
    if ( CutSetNum >= 0 )
    {
        assert( Cut_NodeReadCutsTemp(p, CutSetNum) == NULL );
        Cut_NodeWriteCutsTemp( p, CutSetNum, pList );
    }
    else
    {
        assert( Cut_NodeReadCutsNew(p, Root) == NULL );
        Cut_NodeWriteCutsNew( p, Root, pList );
    }

p->timeUnion += Abc_Clock() - clk;
    // filter the cuts
//clk = Abc_Clock();
//    if ( p->pParams->fFilter )
//        Cut_CutFilter( p, pList );
//p->timeFilter += Abc_Clock() - clk;
//    if ( fFirst )
//        p->nNodes -= vNodes->nSize - 1;
    return pList;
}

void Cut_NodeWriteCutsNew	(	Cut_Man_t *	p,
		int	Node,
		Cut_Cut_t *	pList
	)

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

Synopsis [Returns the pointer to the linked list of cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 97 of file cutApi.c.

{
    Vec_PtrWriteEntry( p->vCutsNew, Node, pList );
}

void Cut_NodeWriteCutsOld	(	Cut_Man_t *	p,
		int	Node,
		Cut_Cut_t *	pList
	)

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

Synopsis [Returns the pointer to the linked list of cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 113 of file cutApi.c.

{
    Vec_PtrWriteEntry( p->vCutsOld, Node, pList );
}

void Cut_NodeWriteCutsTemp	(	Cut_Man_t *	p,
		int	Node,
		Cut_Cut_t *	pList
	)

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

Synopsis [Returns the pointer to the linked list of cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 129 of file cutApi.c.

{
    Vec_PtrWriteEntry( p->vCutsTemp, Node, pList );
}

Cut_Cut_t* Cut_OracleComputeCuts	(	Cut_Oracle_t *	p,
		int	Node,
		int	Node0,
		int	Node1,
		int	fCompl0,
		int	fCompl1
	)

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

Synopsis [Reconstruct the cuts of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 320 of file cutOracle.c.

{
    Cut_Cut_t * pList = NULL, ** ppTail = &pList;
    Cut_Cut_t * pCut, * pCut0, * pCut1, * pList0, * pList1;
    int iCutStart, nCuts, i, Entry;
    abctime clk = Abc_Clock();

    // get the cuts of the children
    pList0 = (Cut_Cut_t *)Vec_PtrEntry( p->vCutsNew, Node0 );
    pList1 = (Cut_Cut_t *)Vec_PtrEntry( p->vCutsNew, Node1 );
    assert( pList0 && pList1 );

    // get the complemented attribute of the cut
    p->fSimul = (fCompl0 ^ pList0->fSimul) & (fCompl1 ^ pList1->fSimul);

    // collect the cuts
    Vec_PtrClear( p->vCuts0 );
    Cut_ListForEachCut( pList0, pCut )
        Vec_PtrPush( p->vCuts0, pCut );
    Vec_PtrClear( p->vCuts1 );
    Cut_ListForEachCut( pList1, pCut )
        Vec_PtrPush( p->vCuts1, pCut );

    // get the first and last cuts of this node
    nCuts = Vec_IntEntry(p->vNodeCuts, Node);
    iCutStart = Vec_IntEntry(p->vNodeStarts, Node);

    // create trivial cut
    assert( Vec_IntEntry(p->vCutPairs, iCutStart) == 0 );
    pCut = Cut_CutTriv( p, Node );
    *ppTail = pCut;
    ppTail = &pCut->pNext;
    // create other cuts
    for ( i = 1; i < nCuts; i++ )
    {
        Entry = Vec_IntEntry( p->vCutPairs, iCutStart + i );
        pCut0 = (Cut_Cut_t *)Vec_PtrEntry( p->vCuts0, Entry & 0xFFFF );
        pCut1 = (Cut_Cut_t *)Vec_PtrEntry( p->vCuts1, Entry >> 16 );
        pCut  = Cut_CutMerge( p, pCut0, pCut1 );
        *ppTail = pCut;
        ppTail = &pCut->pNext;
        // compute the truth table
        if ( p->pParams->fTruth )
            Cut_TruthComputeOld( pCut, pCut0, pCut1, fCompl0, fCompl1 );
    }
    *ppTail = NULL;

    // write the new cut
    assert( Vec_PtrEntry( p->vCutsNew, Node ) == NULL );
    Vec_PtrWriteEntry( p->vCutsNew, Node, pList );
p->timeTotal += Abc_Clock() - clk;
    return pList;
}

void Cut_OracleNodeSetTriv	(	Cut_Oracle_t *	p,
		int	Node
	)

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

Synopsis [Sets the trivial cut for the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 192 of file cutOracle.c.

{
    assert( Vec_PtrEntry( p->vCutsNew, Node ) == NULL );
    Vec_PtrWriteEntry( p->vCutsNew, Node, Cut_CutTriv(p, Node) );
}

int Cut_OracleReadDrop

(

Cut_Oracle_t *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 176 of file cutOracle.c.

{
    return p->pParams->fDrop;
}

void Cut_OracleSetFanoutCounts	(	Cut_Oracle_t *	p,
		Vec_Int_t *	vFanCounts
	)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 160 of file cutOracle.c.

{
    p->vFanCounts = vFanCounts;
}

Cut_Oracle_t* Cut_OracleStart

(

Cut_Man_t *

pMan

)

FUNCTION DEFINITIONS ///.

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

Synopsis [Starts the cut oracle.]

Description []

SideEffects []

SeeAlso []

Definition at line 73 of file cutOracle.c.

{
    Cut_Oracle_t * p;

    assert( pMan->pParams->nVarsMax >= 3 && pMan->pParams->nVarsMax <= CUT_SIZE_MAX );
    assert( pMan->pParams->fRecord );

    p = ABC_ALLOC( Cut_Oracle_t, 1 );
    memset( p, 0, sizeof(Cut_Oracle_t) );

    // set and correct parameters
    p->pParams     = pMan->pParams;

    // transfer the recording info
    p->vNodeCuts   = pMan->vNodeCuts;    pMan->vNodeCuts   = NULL;
    p->vNodeStarts = pMan->vNodeStarts;  pMan->vNodeStarts = NULL;
    p->vCutPairs   = pMan->vCutPairs;    pMan->vCutPairs   = NULL;

    // prepare storage for cuts
    p->vCutsNew = Vec_PtrAlloc( p->pParams->nIdsMax );
    Vec_PtrFill( p->vCutsNew, p->pParams->nIdsMax, NULL );
    p->vCuts0 = Vec_PtrAlloc( 100 );
    p->vCuts1 = Vec_PtrAlloc( 100 );

    // entry size
    p->EntrySize = sizeof(Cut_Cut_t) + p->pParams->nVarsMax * sizeof(int);
    if ( p->pParams->fTruth )
    {
        if ( p->pParams->nVarsMax > 8 )
        {
            p->pParams->fTruth = 0;
            printf( "Skipping computation of truth table for more than 8 inputs.\n" );
        }
        else
        {
            p->nTruthWords = Cut_TruthWords( p->pParams->nVarsMax );
            p->EntrySize += p->nTruthWords * sizeof(unsigned);
        }
    }
    // memory for cuts
    p->pMmCuts = Extra_MmFixedStart( p->EntrySize );
    return p;
}

void Cut_OracleStop

(

Cut_Oracle_t *

p

)

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

Synopsis [Stop the cut oracle.]

Description []

SideEffects []

SeeAlso []

Definition at line 127 of file cutOracle.c.

{
//    if ( p->pParams->fVerbose )
    {
        printf( "Cut computation statistics with oracle:\n" );
        printf( "Current cuts      = %8d. (Trivial = %d.)\n", p->nCuts-p->nCutsTriv, p->nCutsTriv );
        ABC_PRT( "Total time ", p->timeTotal );
    }

    if ( p->vCuts0 )      Vec_PtrFree( p->vCuts0 );
    if ( p->vCuts1 )      Vec_PtrFree( p->vCuts1 );
    if ( p->vCutsNew )    Vec_PtrFree( p->vCutsNew );
    if ( p->vFanCounts )  Vec_IntFree( p->vFanCounts );

    if ( p->vNodeCuts )   Vec_IntFree( p->vNodeCuts );
    if ( p->vNodeStarts ) Vec_IntFree( p->vNodeStarts );
    if ( p->vCutPairs )   Vec_IntFree( p->vCutPairs );

    Extra_MmFixedStop( p->pMmCuts );
    ABC_FREE( p ); 
}

void Cut_OracleTryDroppingCuts	(	Cut_Oracle_t *	p,
		int	Node
	)

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

Synopsis [Consider dropping cuts if they are useless by now.]

Description []

SideEffects []

SeeAlso []

Definition at line 407 of file cutOracle.c.

{
    int nFanouts;
    assert( p->vFanCounts );
    nFanouts = Vec_IntEntry( p->vFanCounts, Node );
    assert( nFanouts > 0 );
    if ( --nFanouts == 0 )
        Cut_OracleFreeCuts( p, Node );
    Vec_IntWriteEntry( p->vFanCounts, Node, nFanouts );
}

void Cut_TruthNCanonicize

(

Cut_Cut_t *

pCut

)

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

Synopsis [Performs truth table computation.]

Description [This procedure cannot be used while recording oracle because it will overwrite Num0 and Num1.]

SideEffects []

SeeAlso []

Definition at line 85 of file cutTruth.c.

{
    unsigned uTruth;
    unsigned * uCanon2;
    char * pPhases2;
    assert( pCut->nVarsMax < 6 );

    // get the direct truth table
    uTruth = *Cut_CutReadTruth(pCut);

    // compute the direct truth table
    Extra_TruthCanonFastN( pCut->nVarsMax, pCut->nLeaves, &uTruth, &uCanon2, &pPhases2 );
//    uCanon[0] = uCanon2[0];
//    uCanon[1] = (p->nVarsMax == 6)? uCanon2[1] : uCanon2[0];
//    uPhases[0] = pPhases2[0];
    pCut->uCanon0 = uCanon2[0];
    pCut->Num0    = pPhases2[0];

    // get the complemented truth table
    uTruth = ~*Cut_CutReadTruth(pCut);

    // compute the direct truth table
    Extra_TruthCanonFastN( pCut->nVarsMax, pCut->nLeaves, &uTruth, &uCanon2, &pPhases2 );
//    uCanon[0] = uCanon2[0];
//    uCanon[1] = (p->nVarsMax == 6)? uCanon2[1] : uCanon2[0];
//    uPhases[0] = pPhases2[0];
    pCut->uCanon1 = uCanon2[0];
    pCut->Num1    = pPhases2[0];
}