⟦e44dbe9ea⟧

TextFile

/*
 * Module: hier.c
 *
 * Author: J. Reuter
 *
 * This module converts a directed graph of basic blocks into
 * a tree of generic control constructs.  It is based on the
 * Unix "struct" program (which is poorly commented, so this is
 * too).
 */

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

#define CHILDNUM(v)	(node_info[node_array[v]->node_type].num_children)

struct hierarchy {
    int h_after;		/* node numbers associated with after numbers*/
    int h_ntobef;		/* before numbers associated with nodes */
    int h_ntoaft;		/* after numbers associated with nodes */
    int h_head;
    struct list *h_inarc;
    int h_dom;
};

#define after(n) (h[n].h_after)
#define ntobef(n) (h[n].h_ntobef)
#define ntoaft(n) (h[n].h_ntoaft)
#define head(n) (h[n].h_head)
#define inarc(n) (h[n].h_inarc)
#define dom(n) (h[n].h_dom)

struct hierarchy *h;		/* where we allocate the hierarchy structure */

struct list {
	int element;
	struct list *next_list;
};

struct list *consls();
struct node *get_orif();

int access_count;		/* number of nodes accessible from start */
static int exit_size = 0;	/* threshold for loop inclusion of small
				   exit code */

hier()
{
    register int v;

    /* find back edges, unreachable nodes */
    dfs();

    /* sets head(v) to N_ITER heading smallest loop containing v or NONE */
    gethead();

    /* sets inarc(v) to list of forward arcs entering v */
    getinarc();

    /* sets dom(v) to immediate dominator of v or NONE */
    getdom();

    /* build the tree structure using head, inarc, dom */
    gettree();

    for (v = 0; v < node_count; v++) {
	freelst( inarc(v) );
	inarc(v) = 0;
    }
    free( h );
}

#define UNSEEN 0
#define STACKED 1
#define FINISHED 2

/*
 * depth-first search used to identify back edges, unreachable nodes;
 * each node v entered by back edge replaced by
 * N_LOOP ->N_ITER -> v,
 * so that back edges entering v now enter the N_ITER,
 * and other edges entering v now enter the N_LOOP.
 * Nodes are numbered according to depth-first search:
 *      before numbering- ntobef(v) = i => node numbered v is i'th
 *		node in order of first visit during the search;
 *	after numbering- ntoaft(v) = i => node numbered v is i'th
 *		node visited in order of last visit during the search.
 *		Also, in this case after(i) = v.
 */

static int befcount, aftcount;

/* following defines used to mark back edges and nodes entered by back edges */

#define mark(n)		n->reach = 1; /* mark node n */
#define unmark(n)	n->reach = 0;
#define marked(n)	(n->reach == 1)
#define mark_edge(e)	if ((e)>-1) (e) = -2-(e); /* mark edge e */
#define unmark_edge(e)	if ((e)<-1) (e) = -2-(e);
#define marked_edge(e)	((e) < -1)


static
dfs()		/* depth first search */
{
    register int i;
    register int w;

    for ( w = 0; w < node_count; w++ ) {
	node_array[w]->node_scratch = UNSEEN;
	node_array[w]->reach = 0; /* use reach to count inarcs */
    }

    if_inarcs( 0 );

    for ( w = 0; w < node_count; w++ )
	node_array[w]->node_scratch = UNSEEN;

    compound_if( 0 );

    access_count = 0;
    for ( w = 0; w < node_count; w++ ) {
	node_array[w]->node_scratch = UNSEEN;
	unmark( node_array[w] );
    }

    search( 0 );

    unreach();

    addloop();

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

    for (i = 0; i < access_count; ++i)
	after(i) = NONE;

    for (w = 0; w < node_count; ++w)
	ntobef(w) = ntoaft(w) = NONE;

    befcount = 0;
    aftcount = 0;

    repsearch(0);
}

/*
 * compound_if converts complex branch logic into compound if statements.
 * Only N_ORIFs are generated here.  Boolean logic will later convert
 * negated N_ORIFs into N_ANDIFs.
 * In addition, each N_CASE node is nested within a N_SWITCH node to
 * allow for proper nesting of case bodies and case labels are added.
 */

/* first count inarcs */
static
if_inarcs( v )
register int v;
{
    register struct node *n;
    register int i, adj;

    n = node_array[v];
    n->node_scratch = STACKED;

    for ( i = 0; i < n->num_arcs; i++ ) {
	adj = n->arcs[i];
	node_array[adj]->reach++;
	if ( node_array[adj]->node_scratch == UNSEEN )
	    if_inarcs( adj );
    }
    n->node_scratch = FINISHED;
}

/* now collapse if's */
/* reach contains inarc count for node */
static
compound_if( v )
register int v;
{
    register int i;
    register int adj;
    register struct node *m, *n, *new;

    n = node_array[v];
    n->node_scratch = STACKED;

    for ( i = 0; i < n->num_arcs; i++ ) {
	adj = n->arcs[i];
	if ( node_array[adj]->node_scratch == UNSEEN )
	    compound_if( adj );
    }

    if ( n->node_type == N_IF || n->node_type == N_ORIF ) {

	m = node_array[ n->arcs[THEN_ARC] ];
	if ( ( m->node_type == N_IF || m->node_type == N_ORIF ) &&
	    m->node_scratch == FINISHED && m->reach == 1 )

	    if ( m->arcs[THEN_ARC] == n->arcs[ELSE_ARC] ) {
		new = get_orif( v, TRUE, n->arcs[THEN_ARC], FALSE,
				 n->arcs[ELSE_ARC], m->arcs[ELSE_ARC] );
		i = m->arcs[THEN_ARC];
		new->reach = n->reach;
		m->arcs[THEN_ARC] = NONE;
		m->arcs[ELSE_ARC] = NONE;
		n->arcs[THEN_ARC] = NONE;
		n->arcs[ELSE_ARC] = NONE;
		node_array[v] = new;
		node_array[node_count - 1] = n;
		node_array[i]->reach--;
		compound_if( v );
		goto skip_else;

	    } else if ( m->arcs[ELSE_ARC] == n->arcs[ELSE_ARC] ) {
		new = get_orif( v, TRUE, n->arcs[THEN_ARC], TRUE,
				 n->arcs[ELSE_ARC], m->arcs[THEN_ARC] );
		i = m->arcs[ELSE_ARC];
		new->reach = n->reach;
		m->arcs[THEN_ARC] = NONE;
		m->arcs[ELSE_ARC] = NONE;
		n->arcs[THEN_ARC] = NONE;
		n->arcs[ELSE_ARC] = NONE;
		node_array[v] = new;
		node_array[node_count - 1] = n;
		node_array[i]->reach--;
		compound_if( v );
		goto skip_else;
	    }

	m = node_array[ n->arcs[ELSE_ARC] ];
	if ( ( m->node_type == N_IF || m->node_type == N_ORIF ) &&
	    m->node_scratch == FINISHED && m->reach == 1 )

	    if ( m->arcs[THEN_ARC] == n->arcs[THEN_ARC] ) {
		new = get_orif( v, FALSE, n->arcs[ELSE_ARC], FALSE,
				 n->arcs[THEN_ARC], m->arcs[ELSE_ARC] );
		i = m->arcs[THEN_ARC];
		new->reach = n->reach;
		m->arcs[THEN_ARC] = NONE;
		m->arcs[ELSE_ARC] = NONE;
		n->arcs[THEN_ARC] = NONE;
		n->arcs[ELSE_ARC] = NONE;
		node_array[v] = new;
		node_array[node_count - 1] = n;
		node_array[i]->reach--;
		compound_if( v );

	    } else if ( m->arcs[ELSE_ARC] == n->arcs[THEN_ARC] ) {
		new = get_orif( v, FALSE, n->arcs[ELSE_ARC], TRUE,
				 n->arcs[THEN_ARC], m->arcs[THEN_ARC] );
		i = m->arcs[ELSE_ARC];
		new->reach = n->reach;
		m->arcs[THEN_ARC] = NONE;
		m->arcs[ELSE_ARC] = NONE;
		n->arcs[THEN_ARC] = NONE;
		n->arcs[ELSE_ARC] = NONE;
		node_array[v] = new;
		node_array[node_count - 1] = n;
		node_array[i]->reach--;
		compound_if( v );
	    }

    } else if ( n->node_type == N_CASE ) {
	/* add a N_SWITCH node for proper case stmt nesting */
	if ( node_count + n->num_arcs > node_max )
	    node_grow();
	new = get_node( 2 );
	new->node_type = N_SWITCH;
	new->start_address = n->start_address;
	new->end_address = n->end_address;
	new->num_arcs = 2;
	new->arcs[0] = n->arcs[0]; /* case exit */
	new->arcs[1] = node_count - 1; /* case stmt. */
	node_array[node_count - 1] = n;
	node_array[v] = new;

	/* and add some case labels */
	for ( i = 1; i < n->num_arcs; i++ ) {
	    new = get_node( 1 );
	    new->node_type = N_CASELAB;
	    new->num_arcs = 1;
	    new->arcs[0] = n->arcs[i];
	    n->arcs[i] = node_count - 1;
	    new->varpart[V_CASESLOT] = i - 1 + n->varpart[V_BASE];
	    node_array[node_count - 1] = new;
	}
    }

 skip_else:
    node_array[v]->node_scratch = FINISHED;
}

static struct node *
get_orif( a_pred, a_negate, b_pred, b_negate, then_arc, else_arc )
int a_pred;
int a_negate;
int b_pred;
int b_negate;
int then_arc;
int else_arc;
{
    register struct node *n;

    if ( node_count + 1 > node_max )
	node_grow();

    n = get_node( 2 );
    n->node_type = N_ORIF;
    n->num_arcs = 2;
    n->arcs[THEN_ARC] = then_arc;
    n->arcs[ELSE_ARC] = else_arc;
    n->varpart[V_NEGATE] = FALSE;
    n->varpart[V_PRED1] = node_count - 1; /* this will be a_pred */

    if ( a_negate )
	node_array[a_pred]->varpart[V_NEGATE] =
	    ! node_array[a_pred]->varpart[V_NEGATE];

    n->varpart[V_PRED2] = b_pred;

    if ( b_negate )
	node_array[b_pred]->varpart[V_NEGATE] =
	    ! node_array[b_pred]->varpart[V_NEGATE];

    return n;
}

/*
 * using depth first search, mark back edges using mark_edge,
 * and nodes entered by back edges using MARK
 */
static
search( v )
register int v;
{
    register int adj;
    register int i;
    register struct node *n;

    n = node_array[v];
    n->node_scratch = STACKED;

    for (i = 0; i < n->num_arcs; i++) {
	adj = n->arcs[i];

	if ( node_array[adj]->node_scratch == UNSEEN )
	    search( adj );

	else if ( node_array[adj]->node_scratch == STACKED ) {

	    /* mark adj node as entered by back edge */
	    mark( node_array[adj] );
	    /* mark edge as being back edge */
	    mark_edge( n->arcs[i] );
	}
    }
    n->node_scratch = FINISHED;
    access_count += 1;
}

/*
 * mark unreachable nodes.  Don't change N_IF nodes if they are
 * unreachable--we need the type information later.
 */
static
unreach()
{
    int v;

    for ( v = 0; v < node_count; v++ )
	if ( node_array[v]->node_scratch == UNSEEN &&
	    node_array[v]->node_type != N_IF &&
	    node_array[v]->node_type != N_ORIF )

	    node_array[v]->node_type = N_UNREACH;
}

/* add N_LOOP, N_ITER at nodes entered by back edges, and adjust edges */
addloop()
{
    register int v;
    register int adj;
    register int j;
    register int oldnum;
    register struct node *n, *loop, *iter;

    /* insloop increases node_count */

    for (v = 0, oldnum = node_count; v < oldnum; ++v) {

	n = node_array[v];

	if ( marked(n) ) {
	    /* remove mark indicating v entered by back edge */
	    unmark(n);

	    if ( node_count + 2 >= node_max )
		node_grow();

	    /* add N_LOOP, N_ITER since v entered by back edge*/
	    loop = get_node( 1 );
	    loop->node_type = N_LOOP;
	    loop->num_arcs = 1;

	    iter = get_node( 1 );
	    iter->node_type = N_ITER;
	    iter->num_arcs = 1;

	    access_count += 2;

	    /* want N_LOOP to take on node number v, so that arcs other than
	       back arcs entering v will enter N_LOOP */

	    node_array[v] = loop;
	    node_array[node_count-2] = iter;
	    node_array[node_count-1] = n;

	    loop->arcs[0] = node_count - 2;
	    iter->arcs[0] = node_count - 1;
	    iter->varpart[V_FATHER] = v;
	}
    }

    /* arcs which used to enter v now enter N_LOOP;
     * must make back edges enter N_ITER */

    for (v = 0; v < node_count; ++v)
	for ( j = 0; j < node_array[v]->num_arcs; ++j ) {

	    if ( marked_edge( node_array[v]->arcs[j] ) ) {

		unmark_edge( node_array[v]->arcs[j] );
		adj = node_array[v]->arcs[j];

		if ( node_array[adj]->node_type != N_ITER )
		    /* change arc to point to N_ITER */
		    node_array[v]->arcs[j] = node_array[adj]->arcs[0];
	    }
	}
}

/* repeat df search in order to fill in after, ntoaft, ntobef tables */
static
repsearch(v)
register int v;
{
    register int adj;
    register int i, temp;

    ntobef(v) = befcount;
    befcount++;

    for ( i = 0; i < node_array[v]->num_arcs; i++ ) {
	adj = node_array[v]->arcs[i];
	if ( ntobef(adj) == NONE )
	    repsearch( adj );
    }

    aftcount++;
    temp = access_count - aftcount;
    after(temp) = v;
    ntoaft(v) = temp;
}


/* define ANC(v,w) true if v == w or v is ancestor of w (reflexive ancestor) */
#define ANC(v,w) ( ntobef(v) <= ntobef(w) && ntoaft(v) <= ntoaft(w) )

/*
 * set head(v) to N_ITER heading smallest loop containing v, for each v
 */

/*
 * Search nodes in reverse of after numbering so that all paths from
 * a node to an ancestor are searched before the node.
 *
 * At any point, the current value of head allows chains of nodes
 * to be reached from any node v by taking head(v), head(head(v)), etc.
 * until an NONE value is reached.  Upon searching each arc, 
 * the appropriate chains must be merged to avoid losing information.
 *
 * For example, from one path out of a node v it may be known that
 * v is in a loop headed by z, while from another
 * it may be known that v is in a loop headed by w.
 * Thus, head(v) must be set to whichever of z,w is the closer ancestor,
 * and the fact that this node is in a loop headed by the other must be
 * recorded in head.
 */
static
gethead()
{
    register int v, w, adj;
    register int i, j;

    for (v = 0; v < node_count; ++v)
	head(v) = NONE;

    for (i = access_count -1; i >= 0; i--) {
	v = after(i);

	for (j = 0; j < node_array[v]->num_arcs; ++j) {
	    adj = node_array[v]->arcs[j];

	    if ( ntoaft(adj) < i ) /* back edge */
		merge( v, adj );

	    else if ( ANC(v, adj) ) { /* not back edge or cross edge */
		/*
		 * need to do only tree edges - must not do edge (v,adj)
		 * when head(adj) is not ANC of v
		 */
		if ( DEFINED(head(adj)) && ANC(head(adj),v) )
		    merge( v, head(adj) );

	    } else {		/* cross edge */

		w = lowanc( adj, v );
		if ( DEFINED(w) )
		    merge( w, v );
	    }
	}
	if ( node_array[v]->node_type == N_LOOP )
	    /* head of N_ITER must be different N_ITER */
	    head(node_array[v]->arcs[0]) = head(v);
    }
}


/* find the first node in chain of y which is anc of z, if it exists */
static int
lowanc( y, z )
register int y, z;
{
    while ( y != -1 && !ANC(y,z) )
	y = head(y);

    return y;
}


/* merge chains of w and y according to ANC relation */
static
merge( w, y )
int w, y;
{
    int t, min;

    if ( w == y )
	return;

    if ( ANC(w,y) ) {		/* set t to min of w,y */
	t = y;
	y = head(y);
    } else {
	t = w;
	w = head(w);
    }

    /* construct chain at t by adding min of remaining elements */

    while (w != -1 && y != -1) {
	if ( ANC(w,y) ) {
	    min = y;
	    y = head(y);
	} else {
	    min = w;
	    w = head(w);
	}

	if ( t != min ) {
	    head(t) = min;
	    t = min;
	}
    }

    if ( w == -1 )
	min = y;
    else
	min = w;

    if ( t != min )
	head(t) = min;
}


/*
 * find forward in-arcs for each node, pretending that arcs which jump
 * into a loop jump to the head of the largest such loop instead, based
 * on the depth first search tree
 */

/* construct array "inarc" containing in arcs for each node */
static
getinarc()
{
    register int v, adj, x;
    register int i, j;

    for (v=0; v < node_count; v++)
	inarc(v) = 0;

    /* fill in inarc nodes */

    for (i = 0; i < access_count; ++i) {
	v = after(i);

	for (j = 0; j < node_array[v]->num_arcs; ++j) {
	    adj = node_array[v]->arcs[j];

	    /* not a back edge */
	    /* if edge jumps into loop, pretend jumps to head of
	       largest loop jumped into */

	    if ( ntoaft(adj) > ntoaft(v) ) {
		x = maxentry( v, adj );
		if ( !DEFINED(x) )
		    x = adj;
		else
		    x = node_array[x]->varpart[V_FATHER];

		/* insert v in list inarc[x] */
		inarc(x) = consls( v, inarc(x) );
	    }
	}
    }
}

/* return z if z is N_ITER of largest loop containing y but not x,
   NONE otherwise */
static int
maxentry( x, y )
int x, y;
{
    if ( head(y) == NONE )
	return(NONE);

    if ( loomem( x, head(y) ) )
	return (NONE);

    y = head(y);

    while ( head(y) != NONE ) {
	if ( loomem( x, head(y) ) )
	    return(y);

	y = head(y);
    }

    return(y);
}

/* return TRUE if x is in loop headed by y, FALSE otherwise */
static int
loomem( x, y )
register int x, y;
{
    register int w;

    if ( !DEFINED(y) )
	return TRUE;

    w = (node_array[x]->node_type == N_ITER) ? x : head(x);

    for ( ; DEFINED(w); w = head(w) )
	if ( w == y )
	    return TRUE;

    return FALSE;
}


/*
 * set dom(v) to immediate dominator of v, based on arcs as stored in inarcs
 * (i.e. pretending the graph is reducible if it isn't).
 * Algorithm is from Hecht and Ullman, Analysis of a simple algorithm for
 * global flow analysis problems, except bit vector operations replaced by
 * search through DOM to save quadratic blowup in space 
 */
static
getdom()
{
    register int v;
    register int i;
    register struct list *ls;

    for (v = 0; v < node_count; ++v)
	dom(v) = NONE;

    for (i = 1; i < access_count; ++i) {
	v = after(i);
	for (ls = inarc(v); ls; ls = ls->next_list) {
	    dom(v) = comdom( dom(v), ls->element );
	}
    }
}

/* find closest common dominator of u,v */
static int
comdom( u, v )
register int u, v;
{
    if (u == NONE)
	return(v);

    if (v == NONE)
	return(u);

    while(u != v) {
	if (ntoaft(u) < ntoaft(v))	
	    v = dom(v);
	else
	    u = dom(u);
    }

    return(u);
}

/*
 * use inarc, dom, and head to build tree representing structure of program.
 *	Each node v has children denoted by
 *	node_array[v]->child[0], node_array[v]->child[1], ...
 *	representing code nested within v
 *
 *	node_array[v]->right_sibling is right sibling of v or NONE,
 *	and represents code following v at the same level of nesting,
 */

/* build tree */
static
gettree()
{
    register int v, u, from;
    register int i;
    register int found;
    register struct node *from_node;

    for ( v = 0; v < node_count; ++v ) {
	node_array[v]->right_sibling = NONE;

	for ( i = 0; i < CHILDNUM(v); ++i )
	    node_array[v]->child[i] = NONE;
    }

    for (i = access_count-1; i > 0; --i) {
	v = after(i);
	found = FALSE;

	/* the unique element of inarc(v) or NONE */
	from = one_element( inarc(v) );

	if ( DEFINED(from) ) {

	    from_node = node_array[from];

	    if ( ( from_node->node_type == N_BRANCH ||
		  from_node->node_type == N_IF ||
		  from_node->node_type == N_ORIF ) &&
		( head(v) == head(from) || asoc( v, exit_size ) != -1 ) ) {

		/*
		 * place in clause of N_BRANCH, N_[OR]IF if in smallest loop
		 * containing it or if size of code for v is <= exit_size
		 */

		if ( from_node->arcs[THEN_ARC] == v ) {
		    from_node->child[THEN_ARC] = v;
		    found = TRUE;

		} else {
		    from_node->child[ELSE_ARC] = v;
		    found = TRUE;
		}

	    } else if ( node_array[v]->node_type == N_ITER ||
		     from_node->node_type == N_ITER ) {

		/* N_LOOP -> N_ITER -> BODY always in same loop */
		from_node->child[0] = v;
		found = TRUE;

	    } else if ( node_array[from]->node_type == N_SWITCH ) {

		if ( from_node->arcs[1] == v ) {
		    from_node->child[0] = v;
		    found = TRUE;
		}
	    }
	}

	if ( found )
	    continue;

	if ( loomem( v, head(dom(v)) ) ) {

	    /* v is in smallest loop containing dom(v) */
	    insib( dom(v), v );

	} else {

	    /*
	     * make v follow N_LOOP heading largest loop
	     * containing dom(v) but not v
	     */

	    for ( u = head(dom(v)); head(u) != head(v); u = head(u) )
		;
	    insib( node_array[u]->varpart[V_FATHER], v );
	}
    }
}

/*
 * make right_sibling[w] = v, and make
 * right_sibling[ rightmost sibling of v ] = previous right_sibling[w]
 */
static
insib( w, v )
register int w, v;
{
    register int u, temp;

    temp = node_array[w]->right_sibling;
    node_array[w]->right_sibling = v;
    for ( u = v; DEFINED(node_array[u]->right_sibling);
	 u = node_array[u]->right_sibling )
	;

    node_array[u]->right_sibling = temp;
}

/* return # of nodes associated with v if <= n, -1 otherwise */
static
asoc( v, n )
register int v;
register int n;
{
    register int count, i, temp;
    register int w;

    i = node_array[v]->node_type;
    if ( i == N_FLOW || i == N_IF || i == N_BRANCH || i == N_SWITCH ||
	i == N_END )
	count = node_array[v]->end_address - node_array[v]->start_address;
    else
	count = 1;

    for ( i = 0; i < CHILDNUM(v); ++i ) {
	w = node_array[v]->child[i];
	if ( !DEFINED(w) )
	    continue;

	temp = asoc( w, n-count );
	if ( temp == -1 )
	    return -1;

	count += temp;
	if ( count > n )
	    return -1;
    }

    if ( DEFINED(node_array[v]->right_sibling) ) {
	temp = asoc( node_array[v]->right_sibling, n - count );
	if ( temp == -1 )
	    return -1;
	count += temp;
    }

    if ( count > n )
	return -1;
    else
	return count;
}

/*
 * list manipulation functions
 */

/* make a list, insert it in front of ls */
static struct list *
consls( v, ls )
register int v;
register struct list *ls;
{
    register struct list *temp;

    temp = (struct list *) malloc( sizeof(struct list) );
    temp->element = v;
    temp->next_list = ls;
    return temp;
}

/* free a list */
static
freelst( ls )
register struct list *ls;
{
    if ( ls == NULL )
	return;

    if ( ls->next_list != NULL )
	freelst( ls->next_list );

    free( ls );
}

/* return element only if it is only element in list */
static int
one_element( ls )
register struct list *ls;
{
    if ( ls == NULL )
	return NONE;

    if ( ls->next_list )
	return NONE;

    return ls->element;
}
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦e44dbe9ea⟧ TextFile

Derivation

TextFile
