subexpr.c

/* Asp applicative language.
 * J.Cupitt,  November '86
 * Common up sub-expressions in the parse tree. */

#include "asphdr.h"			/* Standard bit */
#include "lextypes.h"			/* Needed .. */
#include "parsetypes.h"			/* The parse tree */
#include "evaltypes.h"			/* Need IDENTITY */
#include "parser.h"			/* Need global ST */
#include "symboltypes.h"		/* Need to look inside symbols */
#include "error.h"			/* Might need this */
#include "tree.h"			/* Need ApplyAll */

/* We walk the parse tree commoning up sub-expressions. These
 * might for example be generated by an earlier pass that expanded
 * WHERE clauses. This is supposed to give us most of the advantages
 * of proper local recursion without the performance hit of continually
 * having to use RefCopy.
 * 
 * The compilation stage uses the I nodes generated here to do sharing
 * in the code produced.
 */

/* Test two constant nodes for equality. Used by EqualGraph (see below) */
static enum Boolean EqualConst( c1, c2 )
struct ConstVal *c1, *c2;
{	if( c1 == c2 ) 
		/* I'm not quite sure how this might happen .. just
	 	 * as well to test for it anyway. */
		return( TRUE );
	if( c1->tag != c2->tag )
		/* Different things altogether */
		return( FALSE );
	/* Same sorts of things ... switch & apply comparision prims */
	switch( c1->tag ) {
		case NUM:	
			return( (enum Boolean) (
				c1->details.intconst == 
				c2->details.intconst ) );
		case CHAR:
			return( (enum Boolean) (
				c1->details.charconst ==
				c2->details.charconst ) );
		case BOOL:
			return( (enum Boolean) (
				c1->details.boolconst ==
				c2->details.boolconst ) );
		case NIL:
			return( TRUE );
		/* Don't need to compare strings ... these have already
		 * been expanded into [char] by the tree builder. */
		default:
			errorstart();
			errorstr( "broken in EqualConst" );
			errorend();
			quit();
	};
};

/* A function to test two sub-expressions for equality. Just walk each
 * in parallel until we find a discrepancy. */
static enum Boolean EqualGraph( n1, n2 )
struct ExpressionNode *n1, *n2;
{	if( n1 == n2 ) 
		/* Have already commoned up these two! Perhaps should
		 * return false (as we do not need to common up again)
		 * but this would be confusing! */
		return( TRUE );
	if( n1->tag != n2->tag )
		/* Different tags */
		return( FALSE );
	/* Same tag .. have to look at bodies to find discrepancy */
	switch( n1->tag ) {
		/* Unary ops */
		case IDENTITY:
		case CODE:
		case READ:
		case DECODE:
		case ERROR:
		case UNARYMINUS:
		case NOT:
		case HD:
		case TL:		
			return( (enum Boolean)
				EqualGraph( n1->details.thisop,
					n2->details.thisop ) );
		case GEN1:		
			return( (enum Boolean) 
				EqualGraph( n1->details.gennode.gen1,
					n2->details.gennode.gen1 ) );
		/* Do binary ops */
		case AND:
		case OR:
		case CONS:	
		case BINARYPLUS:	
		case BINARYMINUS:
		case TIMES:	
		case DIVIDE:
		case LESS:		
		case MORE:	
		case EQUAL:
		case MOREEQUAL:		
		case LESSEQUAL:	
		case NOTEQUAL:		
		case APPLICATION:
		case COMP:
			return( (enum Boolean) (
				EqualGraph( n1->details.binop.leftop,
					n2->details.binop.leftop ) &&
				EqualGraph( n1->details.binop.rightop,
					n2->details.binop.rightop ) ) );
		case GEN2:		
		case GEN3:
			return( (enum Boolean) (
				EqualGraph( n1->details.gennode.gen1,
					n2->details.gennode.gen1 ) &&
				EqualGraph( n1->details.gennode.gen2,
					n2->details.gennode.gen2 ) ) );
		case VARREF:
			return( (enum Boolean) (
				n1->details.ident == n2->details.ident ) );
		case IF:
			return( (enum Boolean) (
				EqualGraph( n1->details.ifnode.condition,
					n2->details.ifnode.condition ) &&
				EqualGraph( n1->details.ifnode.thenpart,
					n2->details.ifnode.thenpart ) &&
				EqualGraph( n1->details.ifnode.elsepart,
					n2->details.ifnode.elsepart ) ) );
		case GEN4:
			return( (enum Boolean) (
				EqualGraph( n1->details.gennode.gen1,
					n2->details.gennode.gen1 ) &&
				EqualGraph( n1->details.gennode.gen2,
					n2->details.gennode.gen2 ) &&
				EqualGraph( n1->details.gennode.gen3,
					n2->details.gennode.gen3 ) ) );
		case CONSTANT:
			return( EqualConst( n1->details.cons,
					n2->details.cons ) );
		default:		
			errorstart();
			errorstr( "broken in EqualGraph" );
			errorend();
			quit();
	};
};

/* Finding of common sub-expressions is a little hamfisted:
 * - For every node in tree,
 * 	- Decide whether to select this node as the root for a
 * 	possible common sub-expression. We want to only chose subexprs
 * 	which will generate boxed results (no point in sharing an
 *	unboxed result!)
 *	- If we select this node as a candidate for sub-expression
 *	elimination, then for every subexpr *strictly* to the right
 *	of the selected sub expr:
 *		- Test for this node equal to the selected subexpr.
 *		- If equal, replace this node by an I node, pointing
 *		back to the selected common subexpr. Continue search
 *		from nodes *strictly* to the right of the matched
 *		common subexpr
 *		- Otherwise continue search.
 */

static int nnodes;		/* Used to count nodes in an expr */

/* Note a node .. */
static enum Boolean NoteNode( node )
struct ExpressionNode *node;
{	++nnodes;	/* Up total */
	return( TRUE );
};

/* Count the number of subexprs in an expr .. rather horrible */
static int CountNodes( tree )
struct ExpressionNode *tree;
{	nnodes = 0;	/* Zero total */
	ApplyAll( NoteNode, tree );
	return( nnodes );
};

static struct ExpressionNode *subexpr;	/* Selected common subexpr */
static int startat;		/* From here .. */

/* Innermost part of loop: is this node equal to the selected expr?
 * As this is called from an ApplyAll, have to pass selected expr
 * through static above ^^ */ 
static enum Boolean TestEqual( node )
struct ExpressionNode *node;
{	if( startat != 0 ) {
		/* Not past selected subexpr yet */
		--startat;
		return( TRUE );
	};
	if( EqualGraph( node, subexpr ) ) {
		/* Found a match. Replace by I node and resume
 		 * search to right of this node */
		node->tag = IDENTITY;
		node->details.thisop = subexpr;
		return( FALSE );	/* See comment on ApplyAll */
	};
	return( TRUE );
};

static int sofar;		/* How far through walk */
static struct ExpressionNode *functionbase;	/* Root of current */

/* Outer part of loop .. decide whether to select or not, if so then
 * test against every node to the right of this one. */
static enum Boolean DoNodes( node )
struct ExpressionNode *node;
{	++sofar;
	if( node->tag != IDENTITY &&
		node->tag != VARREF &&
		node->tag != CONSTANT ) {
		/* Candidate for selection .. find number of expr
		 * strictly to the right of this one and test against
		 * those. */
		subexpr = node;
		startat = sofar + CountNodes( node ) - 1;
		ApplyAll( TestEqual, functionbase );
		return( TRUE );
	}
	else
		/* Since we have an I, V or C, do not need to look
		 * within this sub-tree */
		return( FALSE );
};

/* Start up DoNodes .. given a function, scan it commoning up 
 * subexpressions. Called from ForAllSym. */
static void RemoveSub( sym )
struct Symbol *sym;
{	if( !ISFUNC(sym) ) {
		errorstart();
		errorstr( "broken in RemoveSub" );
		errorend();
		quit();
	};
	functionbase = sym->details.func.body;
	sofar = 0;
	ApplyAll( DoNodes, functionbase );
};

/* Remove common sub-expressions from every function.
 * Exported. */
void CommonSub()
{	ForAllSym( CurrentTable, RemoveSub );
};