rwt.h File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "misc/vec/vec.h"
#include "misc/extra/extra.h"
#include "misc/mem/mem.h"

Go to the source code of this file.

Data Structures
struct	Rwt_Man_t_
struct	Rwt_Node_t_

Macros
#define	RWT_LIMIT   1048576/4
	INCLUDES ///. More...
#define	RWT_MIN(a, b)   (((a) < (b))? (a) : (b))
#define	RWT_MAX(a, b)   (((a) > (b))? (a) : (b))

Typedefs
typedef struct Rwt_Man_t_	Rwt_Man_t
typedef struct Rwt_Node_t_	Rwt_Node_t

Functions
static int	Rwt_IsComplement (Rwt_Node_t *p)
static Rwt_Node_t *	Rwt_Regular (Rwt_Node_t *p)
static Rwt_Node_t *	Rwt_Not (Rwt_Node_t *p)
static Rwt_Node_t *	Rwt_NotCond (Rwt_Node_t *p, int c)
void	Rwt_ManPreprocess (Rwt_Man_t *p)
	MACRO DEFINITIONS ///. More...
Rwt_Man_t *	Rwt_ManStart (int fPrecompute)
void	Rwt_ManStop (Rwt_Man_t *p)
void	Rwt_ManPrintStats (Rwt_Man_t *p)
void	Rwt_ManPrintStatsFile (Rwt_Man_t *p)
void *	Rwt_ManReadDecs (Rwt_Man_t *p)
Vec_Ptr_t *	Rwt_ManReadLeaves (Rwt_Man_t *p)
int	Rwt_ManReadCompl (Rwt_Man_t *p)
void	Rwt_ManAddTimeCuts (Rwt_Man_t *p, abctime Time)
void	Rwt_ManAddTimeUpdate (Rwt_Man_t *p, abctime Time)
void	Rwt_ManAddTimeTotal (Rwt_Man_t *p, abctime Time)
void	Rwt_ManLoadFromArray (Rwt_Man_t *p, int fVerbose)
char *	Rwt_ManGetPractical (Rwt_Man_t *p)
Rwt_Node_t *	Rwt_ManAddVar (Rwt_Man_t *p, unsigned uTruth, int fPrecompute)
void	Rwt_ManIncTravId (Rwt_Man_t *p)

Macro Definition Documentation

#define RWT_LIMIT   1048576/4

INCLUDES ///.

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

FileName [rwt.h]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [DAG-aware AIG rewriting package.]

Synopsis [External declarations.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id:

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

]PARAMETERS ///BASIC TYPES ///

Definition at line 51 of file rwt.h.

#define RWT_MAX	(		a,
			b
	)		(((a) > (b))? (a) : (b))

Definition at line 53 of file rwt.h.

#define RWT_MIN	(		a,
			b
	)		(((a) < (b))? (a) : (b))

Definition at line 52 of file rwt.h.

Typedef Documentation

typedef struct Rwt_Man_t_ Rwt_Man_t

Definition at line 55 of file rwt.h.

typedef struct Rwt_Node_t_ Rwt_Node_t

Definition at line 56 of file rwt.h.

Function Documentation

static int Rwt_IsComplement ( Rwt_Node_t *  p )

inlinestatic

Definition at line 122 of file rwt.h.

{ return (int)(((ABC_PTRUINT_T)p) & 01);            }

void Rwt_ManAddTimeCuts	(	Rwt_Man_t *	p,
		abctime	Time
	)

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

Synopsis [Stops the resynthesis manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 301 of file rwtMan.c.

{
    p->timeCut += Time;
}

void Rwt_ManAddTimeTotal	(	Rwt_Man_t *	p,
		abctime	Time
	)

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

Synopsis [Stops the resynthesis manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 333 of file rwtMan.c.

{
    p->timeTotal += Time;
}

void Rwt_ManAddTimeUpdate	(	Rwt_Man_t *	p,
		abctime	Time
	)

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

Synopsis [Stops the resynthesis manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 317 of file rwtMan.c.

{
    p->timeUpdate += Time;
}

Rwt_Node_t* Rwt_ManAddVar	(	Rwt_Man_t *	p,
		unsigned	uTruth,
		int	fPrecompute
	)

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

Synopsis [Adds one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 446 of file rwtUtil.c.

{
    Rwt_Node_t * pNew;
    pNew = (Rwt_Node_t *)Mem_FixedEntryFetch( p->pMmNode );
    pNew->Id     = p->vForest->nSize;
    pNew->TravId = 0;
    pNew->uTruth = uTruth;
    pNew->Level  = 0;
    pNew->Volume = 0;
    pNew->fUsed  = 1;
    pNew->fExor  = 0;
    pNew->p0     = NULL;
    pNew->p1     = NULL;
    pNew->pNext  = NULL;
    Vec_PtrPush( p->vForest, pNew );
    if ( fPrecompute )
        Rwt_ListAddToTail( p->pTable + uTruth, pNew );
    return pNew;
}

char* Rwt_ManGetPractical

(

Rwt_Man_t *

p

)

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

Synopsis [Create practical classes.]

Description []

SideEffects []

SeeAlso []

Definition at line 640 of file rwtUtil.c.

{
    char * pPractical;
    int i;
    pPractical = ABC_ALLOC( char, p->nFuncs );
    memset( pPractical, 0, sizeof(char) * p->nFuncs );
    pPractical[0] = 1;
    for ( i = 1; ; i++ )
    {
        if ( s_RwtPracticalClasses[i] == 0 )
            break;
        pPractical[ s_RwtPracticalClasses[i] ] = 1;
    }
    return pPractical;
}

void Rwt_ManIncTravId

(

Rwt_Man_t *

p

)

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

Synopsis [Adds one node.]

Description []

SideEffects []

SeeAlso []

Definition at line 547 of file rwtUtil.c.

{
    Rwt_Node_t * pNode;
    int i;
    if ( p->nTravIds++ < 0x8FFFFFFF )
        return;
    Vec_PtrForEachEntry( Rwt_Node_t *, p->vForest, pNode, i )
        pNode->TravId = 0;
    p->nTravIds = 1;
}

void Rwt_ManLoadFromArray	(	Rwt_Man_t *	p,
		int	fVerbose
	)

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

Synopsis [Loads data.]

Description []

SideEffects []

SeeAlso []

Definition at line 589 of file rwtUtil.c.

{
    unsigned short * pArray = s_RwtAigSubgraphs;
    Rwt_Node_t * p0, * p1;
    unsigned Entry0, Entry1;
    int Level, Volume, nEntries, fExor;
    int i;
    abctime clk = Abc_Clock();

    // reconstruct the forest
    for ( i = 0; ; i++ )
    {
        Entry0 = pArray[2*i + 0];
        Entry1 = pArray[2*i + 1];
        if ( Entry0 == 0 && Entry1 == 0 )
            break;
        // get EXOR flag
        fExor = (Entry0 & 1);
        Entry0 >>= 1;
        // get the nodes
        p0 = (Rwt_Node_t *)p->vForest->pArray[Entry0 >> 1];
        p1 = (Rwt_Node_t *)p->vForest->pArray[Entry1 >> 1];
        // compute the level and volume of the new nodes
        Level  = 1 + RWT_MAX( p0->Level, p1->Level );
        Volume = 1 + Rwt_ManNodeVolume( p, p0, p1 );
        // set the complemented attributes
        p0 = Rwt_NotCond( p0, (Entry0 & 1) );
        p1 = Rwt_NotCond( p1, (Entry1 & 1) );
        // add the node
//        Rwt_ManTryNode( p, p0, p1, Level, Volume );
        Rwt_ManAddNode( p, p0, p1, fExor, Level, Volume + fExor );
    }
    nEntries = i - 1;
    if ( fVerbose )
    {
        printf( "The number of classes = %d. Canonical nodes = %d.\n", p->nClasses, p->nAdded );
        printf( "The number of nodes loaded = %d.  ", nEntries );  ABC_PRT( "Loading", Abc_Clock() - clk );
    }
}

void Rwt_ManPreprocess

(

Rwt_Man_t *

p

)

MACRO DEFINITIONS ///.

FUNCTION DECLARATIONS ///

MACRO DEFINITIONS ///.

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

Synopsis [Preprocesses computed library of subgraphs.]

Description []

SideEffects []

SeeAlso []

Definition at line 49 of file rwtDec.c.

{
    Dec_Graph_t * pGraph;
    Rwt_Node_t * pNode;
    int i, k;
    // put the nodes into the structure
    p->pMapInv  = ABC_ALLOC( unsigned short, 222 );
    memset( p->pMapInv, 0, sizeof(unsigned short) * 222 );
    p->vClasses = Vec_VecStart( 222 );
    for ( i = 0; i < p->nFuncs; i++ )
    {
        if ( p->pTable[i] == NULL )
            continue;
        // consider all implementations of this function
        for ( pNode = p->pTable[i]; pNode; pNode = pNode->pNext )
        {
            assert( pNode->uTruth == p->pTable[i]->uTruth );
            assert( p->pMap[pNode->uTruth] < 222 ); // Always >= 0 b/c unsigned.
            Vec_VecPush( p->vClasses, p->pMap[pNode->uTruth], pNode );
            p->pMapInv[ p->pMap[pNode->uTruth] ] = p->puCanons[pNode->uTruth];
        }
    }
    // compute decomposition forms for each node and verify them
    Vec_VecForEachEntry( Rwt_Node_t *, p->vClasses, pNode, i, k )
    {
        pGraph = Rwt_NodePreprocess( p, pNode );
        pNode->pNext = (Rwt_Node_t *)pGraph;
//        assert( pNode->uTruth == (Dec_GraphDeriveTruth(pGraph) & 0xFFFF) );
    }
}

void Rwt_ManPrintStats

(

Rwt_Man_t *

p

)

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

Synopsis [Stops the resynthesis manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 183 of file rwtMan.c.

{
    int i, Counter = 0;
    for ( i = 0; i < 222; i++ )
        Counter += (p->nScores[i] > 0);

    printf( "Rewriting statistics:\n" );
    printf( "Total cuts tries  = %8d.\n", p->nCutsGood );
    printf( "Bad cuts found    = %8d.\n", p->nCutsBad );
    printf( "Total subgraphs   = %8d.\n", p->nSubgraphs );
    printf( "Used NPN classes  = %8d.\n", Counter );
    printf( "Nodes considered  = %8d.\n", p->nNodesConsidered );
    printf( "Nodes rewritten   = %8d.\n", p->nNodesRewritten );
    printf( "Calculated gain   = %8d.\n", p->nNodesGained     );
    ABC_PRT( "Start       ", p->timeStart );
    ABC_PRT( "Cuts        ", p->timeCut );
    ABC_PRT( "Truth       ", p->timeTruth );
    ABC_PRT( "Resynthesis ", p->timeRes );
    ABC_PRT( "    Mffc    ", p->timeMffc );
    ABC_PRT( "    Eval    ", p->timeEval );
    ABC_PRT( "Update      ", p->timeUpdate );
    ABC_PRT( "TOTAL       ", p->timeTotal );

/*
    printf( "The scores are:\n" );
    for ( i = 0; i < 222; i++ )
        if ( p->nScores[i] > 0 )
        {
            extern void Ivy_TruthDsdComputePrint( unsigned uTruth );
            printf( "%3d = %8d  canon = %5d  ", i, p->nScores[i], p->pMapInv[i] );
            Ivy_TruthDsdComputePrint( (unsigned)p->pMapInv[i] | ((unsigned)p->pMapInv[i] << 16) );
        }
    printf( "\n" );
*/
}

void Rwt_ManPrintStatsFile

(

Rwt_Man_t *

p

)

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

Synopsis [Stops the resynthesis manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 230 of file rwtMan.c.

{
    FILE * pTable;
    pTable = fopen( "stats.txt", "a+" );
    fprintf( pTable, "%d ", p->nCutsGood );
    fprintf( pTable, "%d ", p->nSubgraphs );
    fprintf( pTable, "%d ", p->nNodesRewritten );
    fprintf( pTable, "%d", p->nNodesGained );
    fprintf( pTable, "\n" );
    fclose( pTable );
}

int Rwt_ManReadCompl

(

Rwt_Man_t *

p

)

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

Synopsis [Stops the resynthesis manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 285 of file rwtMan.c.

{
    return p->fCompl;
}

void* Rwt_ManReadDecs

(

Rwt_Man_t *

p

)

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

Synopsis [Stops the resynthesis manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 253 of file rwtMan.c.

{
    return p->pGraph;
}

Vec_Ptr_t* Rwt_ManReadLeaves

(

Rwt_Man_t *

p

)

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

Synopsis [Stops the resynthesis manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 269 of file rwtMan.c.

{
    return p->vFanins;
}

Rwt_Man_t* Rwt_ManStart

(

int

fPrecompute

)

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

Synopsis [Starts rewriting manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 87 of file rwtMan.c.

{
    Rwt_Man_t * p;
    abctime clk = Abc_Clock();
clk = Abc_Clock();
    p = ABC_ALLOC( Rwt_Man_t, 1 );
    memset( p, 0, sizeof(Rwt_Man_t) );
    p->nFuncs = (1<<16);
    // copy the global tables
    Rwt_ManGlobalStart();
    p->puCanons = s_puCanons; 
    p->pPhases  = s_pPhases; 
    p->pPerms   = s_pPerms; 
    p->pMap     = s_pMap; 
    // initialize practical NPN classes
    p->pPractical  = Rwt_ManGetPractical( p );
    // create the table
    p->pTable = ABC_ALLOC( Rwt_Node_t *, p->nFuncs );
    memset( p->pTable, 0, sizeof(Rwt_Node_t *) * p->nFuncs );
    // create the elementary nodes
    p->pMmNode  = Mem_FixedStart( sizeof(Rwt_Node_t) );
    p->vForest  = Vec_PtrAlloc( 100 );
    Rwt_ManAddVar( p, 0x0000, fPrecompute ); // constant 0
    Rwt_ManAddVar( p, 0xAAAA, fPrecompute ); // var A
    Rwt_ManAddVar( p, 0xCCCC, fPrecompute ); // var B
    Rwt_ManAddVar( p, 0xF0F0, fPrecompute ); // var C
    Rwt_ManAddVar( p, 0xFF00, fPrecompute ); // var D
    p->nClasses = 5;
    // other stuff
    p->nTravIds   = 1;
    p->pPerms4    = Extra_Permutations( 4 );
    p->vLevNums   = Vec_IntAlloc( 50 );
    p->vFanins    = Vec_PtrAlloc( 50 );
    p->vFaninsCur = Vec_PtrAlloc( 50 );
    p->vNodesTemp = Vec_PtrAlloc( 50 );
    if ( fPrecompute )
    {   // precompute subgraphs
//        Rwt_ManPrecompute( p );
//        Rwt_ManPrint( p );
//        Rwt_ManWriteToArray( p );
    }
    else
    {   // load saved subgraphs
        Rwt_ManLoadFromArray( p, 0 );
//        Rwt_ManPrint( p );
        Rwt_ManPreprocess( p );
    }
p->timeStart = Abc_Clock() - clk;
    return p;
}

void Rwt_ManStop

(

Rwt_Man_t *

p

)

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

Synopsis [Stops rewriting manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 149 of file rwtMan.c.

{
    if ( p->vClasses )
    {
        Rwt_Node_t * pNode;
        int i, k;
        Vec_VecForEachEntry( Rwt_Node_t *, p->vClasses, pNode, i, k )
            Dec_GraphFree( (Dec_Graph_t *)pNode->pNext );
    }
    if ( p->vClasses )  Vec_VecFree( p->vClasses );
    Vec_PtrFree( p->vNodesTemp );
    Vec_PtrFree( p->vForest );
    Vec_IntFree( p->vLevNums );
    Vec_PtrFree( p->vFanins );
    Vec_PtrFree( p->vFaninsCur );
    Mem_FixedStop( p->pMmNode, 0 );
    ABC_FREE( p->pMapInv );
    ABC_FREE( p->pTable );
    ABC_FREE( p->pPractical );
    ABC_FREE( p->pPerms4 );
    ABC_FREE( p );
}

static Rwt_Node_t* Rwt_Not ( Rwt_Node_t *  p )

inlinestatic

Definition at line 124 of file rwt.h.

{ return (Rwt_Node_t *)((ABC_PTRUINT_T)(p) ^  01);  }

static Rwt_Node_t* Rwt_NotCond ( Rwt_Node_t *  p, int  c  )

inlinestatic

Definition at line 125 of file rwt.h.

{ return (Rwt_Node_t *)((ABC_PTRUINT_T)(p) ^ (c));  }

static Rwt_Node_t* Rwt_Regular ( Rwt_Node_t *  p )

inlinestatic

Definition at line 123 of file rwt.h.

{ return (Rwt_Node_t *)((ABC_PTRUINT_T)(p) & ~01);  }