opt_commonterms.mx

一个内存数据库的源代码这是服务器端还有客户端

@' The contents of this file are subject to the MonetDB Public License
@' Version 1.1 (the "License"); you may not use this file except in
@' compliance with the License. You may obtain a copy of the License at
@' http://monetdb.cwi.nl/Legal/MonetDBLicense-1.1.html
@'
@' Software distributed under the License is distributed on an "AS IS"
@' basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
@' License for the specific language governing rights and limitations
@' under the License.
@'
@' The Original Code is the MonetDB Database System.
@'
@' The Initial Developer of the Original Code is CWI.
@' Portions created by CWI are Copyright (C) 1997-2007 CWI.
@' All Rights Reserved.

@f opt_commonTerms
@a M. Kersten
@{
@mal
pattern optimizer.commonTerms():str
address OPTcommonTerms;
pattern optimizer.commonTerms(mod:any_1, fcn:any_2):str
address OPTcommonTerms
comment "Common sub-expression optimizer"
@h
#ifndef _OPT_COMMONTERMS_
#define _OPT_COMMONTERMS_
#include "opt_prelude.h"
#include "opt_support.h"

/* #define DEBUG_OPT_COMMONTERMS     show partial result */

#endif
@c
#include "mal_config.h"
#include "opt_commonTerms.h"
#include "mal_interpreter.h"	/* for showErrors() */
#include "opt_aliases.h"
@}
@- Common Subexpression Elimination
Common subexpression elimination merely involves a scan through the 
program block to detect re-curring statements.
The key problem to be addressed is to make sure that the parameters involved
in the repeatative instruction are invariant. 

The analysis of @sc{optimizer.commonTerms()}
is rather crude. All functions with possible side-effects on
their arguments should have been marked as 'unsafe'.
Their use within a MAL block breaks the dataflow graph for all 
objects involved (BATs, everything kept in boxes).
@-
The common subexpression optimizer locates backwards the identical 
instructions. 
It stops as soon as it has found an identical one. Before we can replace the 
expression with the variable(s) of the previous one, we should assure that
we haven;t passed a safety barrier.

@verbatim
    b:= bat.new(:int,:int);
    c:= bat.new(:int,:int);
    d:= algebra.select(b,0,100);
    e:= algebra.select(b,0,100);
    k1:= 24;
    k2:= 27;
    l:= k1+k2;
    l2:= k1+k2;
    l3:= l2+k1;
    optimizer.commonTerms();
@end verbatim
is translated into the code block where the first two instructions 
are not common, because they have side effects.
@verbatim
    b := bat.new(:int,:int);
    c := bat.new(:int,:int);
    d := algebra.select(b,0,100);
    e := d;
    l := calc.+(24,27);
    l3 := calc.+(l,24);
@end verbatim
@{
The current implementation is rather expensive nested-loop algorithm,
which does not perform well for large MAL blocks.
The search can be improved significantly by prefiltering.
For, equality of instruction implies that
all variables have been used before in a similar context.

We should also immediately perform alias removal, because it
creates opportunities for additional rewrites.

Note, we skip the first instruction because it signifies the signature.
The last instruction signifies the end.

@c
static int
OPTcommonTermsImplementation(MalBlkPtr mb, MalStkPtr stk, InstrPtr pci)
{
	int i, j, k, last, n=1;
	InstrPtr p, q;
	int actions = 0;
	int filter[1024];
	int *mask,*alias,limit;
	InstrPtr *old;
	lng c;

	(void) stk;
	(void) pci;
	mask= (int *) alloca(mb->stop * sizeof(int));
	memset((void*) filter, 0, 1024 * sizeof(int));

	alias= (int*) alloca(sizeof(int)* mb->vtop);
	for(i=0; i<mb->vtop; i++) alias[i]=i;

	setLifespan(mb);
	old= mb->stmt;
	limit= mb->stop;
	newMalBlkStmt(mb, mb->stop); /* a new statement stack */
	for ( n= i = 0; i < limit; i++) {
		p = old[i];
		pushInstruction(mb,p);
		n++;
@-
First apply alias propagation, before considering a match.
@c
		if( p->token == ENDsymbol){
			for(i++; i<limit; i++)
				pushInstruction(mb,old[i]);
			break;
		}
		if( p->token == NOOPsymbol) continue;
		if( p->token == ASSIGNsymbol && p->argc== 2 && p->barrier==0){
			if( getLastUpdate(mb,getArg(p,0)) == i &&
				getBeginLifespan(mb,getArg(p,0)) == i &&
				getLastUpdate(mb,getArg(p,1)) < i){
					alias[getArg(p,0)]= alias[getArg(p,1)];
					freeInstruction(p);
					mb->stop--;
					mb->stmt[mb->stop]=0;
					n--;
					continue;
			}
		} else {
			for(j=0; j<p->argc; j++)
				getArg(p,j)= alias[getArg(p,j)];
		}
@-
Use a hash filter to speed up matching
@c
		c = p->argc;
		for(j=p->retc; j<p->argc; j++){
			c *= 4;
			if( !isConstant(mb,getArg(p,j)) )
				c += getArg(p,j);
		}
		c &= 1023;
		mask[n-1] = c;
		
		if (filter[c] && p->retc != p->argc){
@-
We look back in the code base to determine a candidate for
replacement. We don't have to look further back then the last
relevant assignment. Beware, we may miss opportunities due to
multiple occurrences of the same constant in the symbol table.
@c
			last=1;
			for( j = p->retc; j<p->argc; j++)
			if( getBeginLifespan(mb,getArg(p,j)) > last )
				last = getBeginLifespan(mb,getArg(p,j));

			for (j = (n-1) - 1; j >= last-(i-(n-1)) && j>0; j--) 
			if( mask[j] == c ){
				if (safetyBarrier(p, q = getInstrPtr(mb, j)))
					break;
#ifdef DEBUG_OPT_COMMONTERMS
				printInstruction(GDKout, mb, q, LIST_MAL_ALL);
				printInstruction(GDKout, mb, p, LIST_MAL_ALL);
				printf("%d, %d  %d %d ", i, j, 
					hasSameSignature(p, q), 
					hasSameArguments(mb, p, q));
				printf(" :%d %d %d %d\n", 
					!isUpdated(mb, i), 
					!hasCommonResults(p, q), 
					!hasSideEffects(p, TRUE),
					!hasSideEffects(q, TRUE));

#endif
				if (hasSameSignature(p, q) && 
					hasSameArguments(mb, p, q) && 
					!isUpdated(mb, i) && 
					!hasCommonResults(p, q) && 
					!hasSideEffects(p, TRUE) &&
					allTargetsVisible(mb,j,n-1) 
					) {
#ifdef DEBUG_OPT_COMMONTERMS
					stream_printf(GDKout, "Found a common expression " "%d <-> %d\n", j, i);
#endif
					clrFunction(p);
					p->token = ASSIGNsymbol;
					p->argc = p->retc + q->retc;
					for (k = 0; k < q->retc; k++)
						p->argv[p->retc + k] =  q->argv[k];
#ifdef DEBUG_OPT_COMMONTERMS
					stream_printf(GDKout, "common modified expression");
					printInstruction(GDKout, mb, p, LIST_MAL_ALL);
#endif
					actions++;
					if( p->argc== 2 &&
						getLastUpdate(mb,getArg(p,0)) == i &&
						getBeginLifespan(mb,getArg(p,0)) == i &&
						getLastUpdate(mb,getArg(p,1)) < i){
							alias[getArg(p,0)]= alias[getArg(p,1)];
							freeInstruction(p);
							mb->stop--;
							mb->stmt[mb->stop]=0;
							n--;
					}
					j= 0; /* end of search */
				}
			}
		}
		filter[c ]= 1;
	}
	return actions;
}

@include optimizerWrapper.mx
@h
@:exportOptimizer(commonTerms)@
@c
@:wrapOptimizer(commonTerms,OPT_CHECK_ALL)@
@}