⟦d400e9114⟧

TextFile

/*
 * Module: hll.c
 *
 * Author: J. Reuter
 *
 * This module converts the tree of generic control constructs produced
 * by hier() into a tree of C-specific 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 NTYPE(v) (node_array[v]->node_type)
#define REACH(v) (node_array[v]->reach)
#define RSIB(v) (node_array[v]->right_sibling)
#define LCHILD(v,i) (node_array[v]->child[i])
#define ARCNUM(v) (node_array[v]->num_arcs)
#define ARC(v,i) (node_array[v]->arcs[i])
#define CHILDNUM(v) (node_info[node_array[v]->node_type].num_children)

/* lexical successor of v, for N_ITER only */
#define BRK(v) (node_array[v]->varpart[V_FATHER])
#define LABEL(v) REACH(v)
#define NEG(v) (node_array[v]->varpart[V_NEGATE])
#define NXT(v) (node_array[v]->varpart[V_NEXT])
#define LPRED(v) (node_array[v]->varpart[V_LOOP_PRED])

struct pair {
    int smallest;
    int second;
};

static int num_counter;
static int *head;

hll()
{
    int v;

    num_counter = 0;
    getreach();

    fixflow( 0, NONE );

    getthen( 0 );

    head = (int *) malloc( node_count * sizeof(int) );

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

    for ( v = 0; DEFINED(v); v = RSIB(v) )
	fixhd( v, NONE );

    /* fixhd must be called before getloop so that
       it gets applied to N_IF which becomes NXT(w) for N_UNTIL w */

    getloop();

    getbranch();

    free( head );
    head = NULL;
}

/*
 * set REACH(v) = w if w is only node outside subtree of v which is
 * reached from within subtree of v, REACH(v) = NONE otherwise
 */

#define NUM(v) ( DEFINED(v) ? node_array[v]->node_scratch : NONE )
#define SETNUM(v) (node_array[v]->node_scratch)

/* strategy in obtaining REACH(v) for each node v:
 * Since only need to know whether there is exactly one exit from subtree of v,
 * need keep track only of 2 farthest exits from each subtree rather than all
 * exits.
 * The first may be the unique exit, while the second is used when the children
 * of a node has the same first exit.
 * To obtain 2 farthest exits of v, look at 2 farthest exits of children of
 * v and the nodes entered by arcs from v.  Farthest exits are identified
 * by numbering the nodes from -2 to -(accessnum-2) starting at the bottom
 * left corner of tree using procedure number().  The farthest exit from
 * the subtree of v is the one with the least number according NUM to
 * this numbering.  If a node w is an exit from the subtree of v, THEN_ARC
 * NUM(w) < NUM(v).  The negative numbers allow NUM(v) to be stored in
 * the same location as REACH(v).  REACH(w) may already be set when an
 * arc (v,w) to a child is searched, but the negative numbering is
 * consistent, i.e. NUM(v) < NUM(w) in this case as in other cases
 * where w is not an exit from the subtree of v.
 */

/* obtain REACH(v) for each node v */
static
getreach()
{
    register int v;
    struct pair pair;

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

    number( 0 );

    for (v = 0; DEFINED(v); v = RSIB(v))
	exits( v, &pair );
}

/*
 * set REACH(v) = w if w is only node outside subtree of v which is
 * reached from within subtree of v, leave REACH(v) NONE otherwise
 */
static
exits( v, vpair )
register int v;
register struct pair *vpair;
{
    struct pair chpair;
    register int w, t;
    register int i;

    vpair->smallest = vpair->second = NONE;

    for ( i = 0; i < CHILDNUM(v); i++ ) {
	w = LCHILD(v,i);
	if (!DEFINED(w))
	    continue;

	for ( t = w; DEFINED(t); t = RSIB(t) ) {
	    exits( t, &chpair );

	    /*
	     * set vpair->smallest,second to two smallest of vpair->smallest,
	     * second, chpair->smallest,second
	     */
	    if ( inspr( chpair.smallest, vpair ) )
		inspr( chpair.second, vpair );
	}
    }

    for ( i = 0; i < ARCNUM(v); i++ ) {
	w = ARC(v,i);
	if (!DEFINED(w))
	    continue;
	inspr( w, vpair );
    }

    /* throw out nodes in subtree of  v */
    if ( NUM( vpair->second ) >= NUM( v ) ) {
	vpair->second = NONE;
	if ( NUM( vpair->smallest ) >= NUM( v ) )
	    vpair->smallest = NONE;
    }

    if ( vpair->second == NONE )
	REACH(v) = vpair->smallest; /* vpair->smallest possibly NONE */
    else
	REACH(v) = NONE;
}

/*
 * number nodes from -2 to -(accessnum+2) starting at bottom left
 * corner of tree
 */
static
number( v )
register int v;
{
    register int i;
    register int w;

    for ( i = 0; i < CHILDNUM(v); i++ ) {
	w = LCHILD(v,i);
	if ( DEFINED(w) )
	    number( w );
    }

    SETNUM(v) = num_counter - 2;
    num_counter--;

    if ( DEFINED(RSIB(v)) )
	number( RSIB(v) );
}

/* insert w in order in pr, return TRUE if <= smaller of pr */
/* don't insert duplicates */
static int
inspr( w, pr )
register int w;
register struct pair *pr;
{
    if (w == pr-> smallest)
	return TRUE;

    if ( NUM( w ) < NUM( pr->smallest ) ) {
	pr->second = pr->smallest;
	pr->smallest = w;
	return TRUE;
    }

    if ( w == pr->second )
	return FALSE;

    if ( NUM( w ) < NUM( pr->second ) )
	pr->second = w;

    return FALSE;
}

/*
 * correct the flow of control in the new program - use GOTO's which may
 * be changed later to NEXT, BREAK, etc.
 */

/* for these, control never flows directly to following statement */
/* (also N_BREAK, N_CONTINUE, but these don't yet exist) */
#define HASLEX(t) ( t != N_GOTO && t != N_ITER && t != N_END && t != N_CASE )

static
fixflow( v, autolex )
register int v;
register int autolex;		/* lexical successor of v */
{
    register int lex, chlex, z, x, w;
    register int i;

    if ( HASLEX( NTYPE(v) ) ) {

	lex = lexval( v, autolex );
	if ( DEFINED(REACH(v)) && REACH(v) != lex )
	    insib( v, makebr( REACH(v) ) );
    }

    if ( NTYPE(v) == N_ITER ) {
	BRK(v) = autolex;
	chlex = v;
    } else {
	chlex = lexval( v, autolex );
	if ( NTYPE(v) == N_SWITCH )
	    BRK(v) = chlex;
    }

    for ( i = 0; i < CHILDNUM(v); i++ ) {
	w = LCHILD(v,i);

	if ( DEFINED(w) )
	    fixflow( w, chlex );

	else {
	    z = ARC(v,i);

	    if (z != chlex) {
		x = makebr( z );
		LCHILD(v,i) = x;
		RSIB(x) = NONE;
	    }
	}
    }

    if ( DEFINED( RSIB(v) ) )
	fixflow( RSIB(v), autolex );
}

static int
lexval( v, lastlex )
register int v, lastlex;
{
    register int sib;

    if ( !HASLEX( NTYPE(v) ) )
	return NONE;

    sib = RSIB(v);

    if ( !DEFINED(sib) )
	return lastlex;

    else if ( NTYPE(sib) == N_GOTO )
	return ARC(sib,0);
    else
	return sib;
}

/* make branching node leading to w */
static int
makebr( w )
register int w;
{
    register struct node *new;

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

    new = get_node( 1 );
    new->node_type = N_GOTO;
    new->num_arcs = 1;
    new->arcs[0] = w;
    new->right_sibling = NONE;
    new->reach = NONE;
    node_array[node_count - 1] = new;
    return node_count - 1;
}

#define BRANCHTYPE(t) (t == N_GOTO || t == N_BREAK || t == N_CONTINUE || \
		       t == N_END)
#define MAXCHUNK 100

/* if ELSE_ARC clause smaller than MAXCHUNK and smaller than THEN_ARC clause,
 * and there is no reason not to negate the if, negate the if */

/* turn N_IF into THEN_ARC when appropriate, create ELSE_ARC ifs where
 * possible  */
static
getthen( v )
register int v;
{
    register int tch, fch;
    register int tn,fn;
    register int recvar;

    if ( NTYPE(v) == N_IF || NTYPE(v) == N_ORIF || NTYPE(v) == N_BRANCH ) {
	tch = LCHILD(v,THEN_ARC);
	fch = LCHILD(v,ELSE_ARC);

	if ( DEFINED(fch) ) {
	    if ( !DEFINED(tch) )
		negate( v );
	    else if ( BRANCHTYPE( NTYPE(tch) ) )
		mkthen( v );
	    else if ( BRANCHTYPE( NTYPE(fch) ) ) {
		negate( v );
		mkthen( v );
	    } else if ( ( NTYPE(fch) != N_IF && NTYPE(fch) != N_ORIF &&
			 NTYPE(fch) != N_BRANCH ) || DEFINED( RSIB(fch) ) )
		if ( ( NTYPE(tch) == N_IF || NTYPE(tch) == N_ORIF
		      || NTYPE(tch) == N_BRANCH ) && !DEFINED( RSIB(tch) ) )
		    /* not an else if */
		    /* invert into else if */
		    negate( v );
		else {
		    /* asoc(v,n) returns number of statements associated with v
		       if <= n, -1 otherwise */
		    tn = asoc( tch, MAXCHUNK );
		    fn = asoc( fch, MAXCHUNK );
		    if ( fn >= 0 && (tn < 0 || fn < tn) )
			/* else clause smaller */
			negate( v );
		}
	}
    }

    for ( recvar = 0; recvar < CHILDNUM(v); recvar++ )
	if ( DEFINED( LCHILD(v,recvar) ) )
	    getthen( LCHILD( v, recvar ) );

    if ( DEFINED( RSIB(v) ) )
	getthen( RSIB(v) );
}

static
mkthen( v )
register int v;
{
    register int w;

    w = LCHILD(v,ELSE_ARC);

    if ( DEFINED(w) ) {
	insib( v, w );
	LCHILD(v,ELSE_ARC) = NONE;
    }
}

static
negate( v )
register int v;
{
    register int temp;

    temp = LCHILD(v,THEN_ARC);
    LCHILD(v,THEN_ARC) = LCHILD(v,ELSE_ARC);
    LCHILD(v,ELSE_ARC) = temp;
    NEG(v) = !NEG(v);
}

#define ARCCOUNT(v)	REACH(v)

static
fixhd( v, hd )
register int v, hd;
{
    register int w, newhd;
    register int i;

    head[v] = hd;
    newhd = ( NTYPE(v) == N_ITER || NTYPE(v) == N_SWITCH ) ? v : hd;

    for ( i = 0; i < CHILDNUM(v); i++ )
	for ( w = LCHILD(v,i); DEFINED(w); w = RSIB(w) )
	    fixhd( w, newhd );
}

static
getloop()
{
    cntarcs();
    fixloop( 0 );
}

/* count arcs entering each node */
static
cntarcs()
{
    register int w,v;
    register int i;

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

    for ( v = 0; v < node_count; v++ )
	if ( NTYPE(v) != N_UNREACH && NTYPE(v) != N_GOTO &&
	    NTYPE(v) != N_SWITCH )
	    for ( i = 0; i < ARCNUM(v); i++ ) {
		w = ARC(v,i);
		if ( DEFINED(w) )
		    ARCCOUNT(w)++;
	    }
}

/* find WHILE loops  */
static
fixloop( v )
register int v;
{
    register int r;

    if ( NTYPE(v) == N_LOOP ) {
	NXT(ARC(v,0)) = ARC(v,0);
	if ( !getwh(v) )
	    getun( v );
    }

    for ( r = 0; r < CHILDNUM(v); r++ )
	if ( DEFINED( LCHILD(v,r) ) )
	    fixloop( LCHILD(v,r) );

    if ( DEFINED( RSIB(v) ) )
	fixloop( RSIB(v) );
}

static
getwh( v )
register int v;
{
    register int vchild, vgrand, vgreat;

    vchild = LCHILD(v,0);
    vgrand = LCHILD(vchild,0);

    if ( !DEFINED(vgrand) || !( ( NTYPE(vgrand) == N_IF ||
				 NTYPE(vgrand) == N_ORIF ) &&
			       !DEFINED( LCHILD(vgrand,ELSE_ARC) ) ) )
	return FALSE;

    vgreat = LCHILD(vgrand,THEN_ARC);
    if ( DEFINED(vgreat) && NTYPE(vgreat) == N_GOTO &&
	ARC(vgreat,0) == BRK(vchild) ) {

	/* turn into WHILE */
	NTYPE(v) = N_WHILE;
	NEG( vgrand ) = !NEG( vgrand );
	LPRED( v ) = vgrand; 
	LCHILD(vchild,0) = RSIB(vgrand);
	RSIB(vgrand) = NONE;
	return TRUE;
    }
    return FALSE;
}

/* change loop to REPEAT UNTIL if possible */
static
getun(v)
register int v;
{
    register int vchild, vgrand,  vgreat, before, ch;

    vchild = LCHILD(v,0);

    if ( ARCCOUNT(vchild) > 2 )
	return FALSE;		/* loop can be iterated without passing
				   through predicate of UNTIL */
    vgrand = ARC(vchild,0);

    if ( !DEFINED(vgrand) )
	return FALSE;

    for ( ch = vgrand,before = NONE; DEFINED( RSIB(ch) ); ch = RSIB(ch) )
	before = ch;

    if ( ( ( NTYPE(ch) != N_IF && NTYPE(ch) != N_ORIF )
	   || DEFINED( LCHILD(ch,ELSE_ARC) ) ) )
	return FALSE;

    vgreat = LCHILD(ch,THEN_ARC);

    if ( DEFINED(vgreat) && NTYPE(vgreat) == N_GOTO &&
	ARC(vgreat,0) == BRK(vchild) ) {
	/* create  UNTIL node */
	NTYPE(v) = N_UNTIL;
	NXT( vchild ) = ch;
	NEG( ch ) = !NEG( ch );
	LPRED( v ) = ch;
	RSIB( before ) = NONE;
	return TRUE;
    }
    return FALSE;
}

static
getbranch()
{
    register int v;

    for ( v = 0; v < node_count; v++ )
	LABEL(v) = FALSE;

    for ( v = 0; DEFINED(v); v = RSIB(v) )
	chkbranch( v );
}

static
chkbranch( v )
register int v;
{
    register int w;
    register int i;

    if ( NTYPE(v) == N_GOTO ) {

	w = head[v];
	if ( DEFINED(w) ) {

	    if ( ARC(v,0) == BRK(w) )
		NTYPE(v) = N_BREAK;

	    else if ( ARC(v,0) == NXT(w) )
		NTYPE(v) = N_CONTINUE;
	}

	if ( NTYPE(v) == N_GOTO )
	    LABEL( ARC(v,0) ) = TRUE;
    }

    for ( i = 0; i < CHILDNUM(v); i++ )
	for ( w = LCHILD(v,i); DEFINED(w); w = RSIB(w) )
	    chkbranch( w );
}

/*
 * 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 = RSIB(w);
    RSIB(w) = v;
    for ( u = v; DEFINED( RSIB(u) ); u = RSIB(u) )
	;

    RSIB(u) = 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_CASE ||
	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;
}
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦d400e9114⟧ TextFile

Derivation

TextFile
