⟦75280ce4f⟧

TextFile

/*
 * Module: nodes.c
 *
 * Author: J. Reuter
 *
 * This module contains the functions to manage nodes, perform
 * generic node manipulation, and debug graphs and trees of nodes.
 */

#include "defs.h"
#include "nodes.h"
#include "setjmp.h"

extern jmp_buf badbranch;

struct node head_node;		/* head of node chain--used to create nodes */
struct node *last_node = &head_node; /* pointer to last node of chain */
int node_count;			/* number of nodes */
int node_max;			/* amount of node space in node_array */
struct node **node_array;	/* used for dyn. alloc. node array */

struct node_info node_info[MAX_TYPES] = {
    0, "N_UNREACH",
    0, "N_FLOW",
    2, "N_BRANCH",
    0, "N_CASE",
    0, "N_END",
    2, "N_IF",
    1, "N_LOOP",
    1, "N_ITER",
    2, "N_ANDIF",
    2, "N_ORIF",
    1, "N_SWITCH",
    0, "N_GOTO",
    0, "N_BREAK",
    0, "N_CONTINUE",
    0, "N_CASELAB",
    1, "N_WHILE",
    1, "N_UNTIL",
};

/*
 * get_node allocates a node and puts it at the end of the node chain.
 * The chain will be converted into an array (node_array) when we are
 * finished creating nodes and know how many exist.
 */
struct node *
get_node( arc_count )
int arc_count;			/* number of node exit 'arcs' */
{
    register struct node *node;

    /* allocate the node space */
    node = (struct node *) malloc( sizeof( struct node ) );
    if ( node == NULL ) {
	fprintf( stderr, "Out of memory\n" );
	exit(1);
    }
    node->node_pscratch = NULL;
    node->arcs = NULL;

    if ( arc_count > 0 ) {
	node->arcs = (address *) malloc( arc_count * sizeof( address ) );
	if ( node->arcs == NULL ) {
	    fprintf( stderr, "Out of memory\n" );
	    exit(1);
	}
    }

    node_count += 1;
    /* now put the node at the end of the chain */
    last_node -> node_pscratch = node;
    last_node = node;
    return node;
}

array_nodes()
{
    register struct node *n;
    register int i, j;

    if ( node_count <= 0 ) {
	fprintf( stderr, "Bad node_count in array_nodes()\n" );
	longjmp( badbranch, 1 );
    }

    node_max = node_count * 4;
    node_array = (struct node **) malloc( node_max * sizeof( struct node * ) );
    if ( node_array == NULL ) {
	fprintf( stderr, "Out of memory\n" );
	exit( 1 );
    }

    /*
     * using the node_pscratch chain, put the nodes into node_array
     * in the order that they are chained together
     */
    for ( i = 0, n = head_node.node_pscratch; n != NULL;
	 i++, n = n->node_pscratch )
	node_array[i] = n;

    /* now convert all the arcs from `addresses' to array indices */
    for ( i = 0; i < node_count; i++ ) {
	n = node_array[i];
	for ( j = 0; j < n->num_arcs; j++ ) {

	    /* binary search for start_address == n->arcs[j] */

	    register int lower, upper, k;

	    lower = 0;
	    upper = node_count - 1;

	    while ( upper >= lower ) {
		k = ( lower + upper ) / 2;

		if ( n->arcs[j] < node_array[k]->start_address )
		    upper = k - 1;
		else if ( n->arcs[j] > node_array[k]->start_address )
		    lower = k + 1;
		else {
		    n->arcs[j] = k;
		    goto found;
		}
	    }
	    fprintf( stderr, "Can't find arc target by start_address\n" );
	    longjmp( badbranch, 1 );
	found: ;
	}
    }
}

node_grow()
{
    fprintf( stderr, "Grow nodes!\n" );
}

free_nodes()
{
    register int i;

    for ( i = 0; i < node_count; i++ ) {

	if ( node_array[i]->arcs != NULL )
	    free( node_array[i]->arcs );

	free( node_array[i] );
    }

    free( node_array );

    node_array = NULL;
    node_count = 0;
    node_max = 0;
    head_node.node_pscratch = NULL;
    last_node = &head_node;
}

dump_nodes()
{
    register int i, j;
    register struct node *n;

    fprintf( stderr, "Head node link: %d\n", head_node.node_scratch );

    if ( node_array != NULL ) {

	fprintf( stderr, "%d nodes\n", node_count );

	for ( i = 0; i < node_count; i++ ) {
	    fprintf( stderr, "Node %d: type %d  start %d end %d\n", i,
		    node_array[i]->node_type, node_array[i]->start_address,
		    node_array[i]->end_address );
	    fprintf( stderr, "      scratch %d  num_arcs %d\n",
		    node_array[i]->node_scratch, node_array[i]->num_arcs );

	    if ( node_array[i]->arcs != NULL )
		for ( j = 0; j < node_array[i]->num_arcs; j++ )
		    fprintf(stderr, "      arc: %d\n", node_array[i]->arcs[j]);
	}
    } else {
	i = 0;
	n = head_node.node_pscratch;

	while ( n != NULL ) {
	    fprintf( stderr, "Node %d: type %d  start %d end %d\n", i,
		    n->node_type, n->start_address,
		    n->end_address );
	    fprintf( stderr, "      scratch %d  num_arcs %d\n",
		    n->node_scratch, n->num_arcs );

	    if ( n->arcs != NULL )
		for ( j = 0; j < n->num_arcs; j++ )
		    fprintf(stderr, "      arc: %d\n", n->arcs[j]);

	    i++;
	    n = n->node_pscratch;
	}
    }
    fflush( stdout );
}

prgraph()
{
    int v;
    int i;

    for ( v = 0; v < node_count; v++ ) {
	fprintf( stderr, "%d %s:", v,
		node_info[node_array[v]->node_type].name );

	for ( i = 0; i < node_array[v]->num_arcs; i++ )
	    fprintf( stderr, "%d ", node_array[v]->arcs[i] );

	fprintf( stderr, "\n" );
    }
    fprintf( stderr, "\n\n" );
}

prtree()
{
    pr_tree( 0, 1 );
}

static
pr_tree( v, tabstop )
int v;
int tabstop;
{
    int i;

    tabover( tabstop );
    fprintf( stderr, "%d %s:", v, node_info[node_array[v]->node_type].name );
    for ( i = 0; i < node_array[v]->num_arcs; i++ )
	fprintf( stderr, " %d", node_array[v]->arcs[i] );

    fprintf( stderr, "\n" );
    for ( i = 0; i < node_info[node_array[v]->node_type].num_children; i++ ) {
	tabover( tabstop + 1 );
	fprintf( stderr, "{\n" );

	if ( DEFINED( node_array[v]->child[i] ) )
	    pr_tree( node_array[v]->child[i], tabstop + 1 );

	tabover( tabstop + 1 );
	fprintf( stderr, "}\n" );
    }

    if ( DEFINED( node_array[v]->right_sibling ) )
	pr_tree( node_array[v]->right_sibling, tabstop );
}

static
tabover( n )
int n;
{
    int i;

    for ( i = 0; i < n; i++ )
	putc( '\t', stderr );
}
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦75280ce4f⟧ TextFile

Derivation

TextFile
