opt_strengthreduction.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_strengthReduction
@a M. Kersten
@- Strength Reduction
An effective optimization technique in compiler construction is to
move invariant statements out of the loops. The equivalent strategy can be
applied to the guarded blocks in MAL programs.
Any variable introduced in a block and assigned a value using a
side-effect free operation is a candidate to be moved.
Furthermore, it may not be used outside the block and the expression
may not depend on variables assigned a value within the same block.

@verbatim
	j:= "hello world";
barrier go:=true;
	i:= 23;
	j:= "not moved";
	k:= j; 
	io.print(i);
	redo go:= false;
exit go;
	z:= j;
optimizer.strengthReduction();
@end verbatim
which is translated into the following code:
@verbatim
	j := "hello world";
	i := 23;
barrier go := true;
	j := "not moved";
	k := j;
	io.print(i);
	redo go:= false;
exit go;
	z:= j;
@end verbatim
Application is only applicable to loops and not to
guarded blocks in general,
because execution of a statement outside the guarded block
consumes processing resources which may have been prohibited by
the block condition.

For example, it doesn't make sense to move creation of objects
outside the barrier.
@{
@mal
pattern optimizer.strengthReduction():str
address OPTstrengthReduction;
pattern optimizer.strengthReduction(mod:str, fcn:str):str
address OPTstrengthReduction
comment "Move constant expressions out of the loop";

@h
#ifndef _OPT_STRENGTHREDUCTION_
#define _OPT_STRENGTHREDUCTION_
#include "opt_prelude.h"
#include "opt_support.h"

/* #define DEBUG_OPT_STRENGTHREDUCTION     show partial result */

#endif
@c
#include "mal_config.h"
#include "opt_strengthReduction.h"
#include "mal_interpreter.h"	/* for showErrors() */

@+ Strength reduction implementation
Strength reduction of the code is defensive. 
This first shot assumes a single loop, so we do not have to
maintain a complex administration. We simply split the code
into two sections. Those that should do Before and  Within the loop.

A critical decision is to make sure that none of the arguments
are overwritten in a given context.
@c
static int
SRoverwritten(InstrPtr p, int varid)
{
	int i;

	for (i = p->retc; i < p->argc; i++)
		if (getArg(p, i) == varid)
			return 1;
	return 0;
}
static int
isNewSource(InstrPtr p) {
	str mp= getModuleId(p);
	if( mp == calcRef) return 1;
	if( mp == batcalcRef) return 1;
	if( mp == strRef) return 1;
	if( mp == batstrRef) return 1;
	if( mp == getName("array",5)) return 1;
	if( mp == getName("url",3)) return 1;
	if( mp == getName("daytime",7)) return 1;
	if( mp == getName("day",3)) return 1;
	if( mp == getName("date",4)) return 1;
	if( mp == getName("time",4)) return 1;
	if( mp == getName("tzone",5)) return 1;
	if( mp == getName("color",4)) return 1;
	if( mp == getName("batcolor",8)) return 1;
	if( mp == getName("blob",4)) return 1;
	return 0;
}
static int
OPTstrengthReductionImplementation(MalBlkPtr mb, MalStkPtr stk, InstrPtr pci)
{
	int i, j = 0, k, se= FALSE;
	InstrPtr p;
	int bk, ik, blk, blkbegin, blkexit, actions = 0;
	InstrPtr *before, *within;

	(void) pci;
	(void) stk;		/* to fool compilers */

	before = (InstrPtr *) alloca((mb->ssize + 1) * sizeof(InstrPtr));
	within = (InstrPtr *) alloca((mb->ssize + 1) * sizeof(InstrPtr));
	bk = 0;
	ik = 0;
	blk = 0;
	blkexit= blkbegin = 0;
	for (i = 0; i < mb->stop; i++)
		before[i] = within[i] = 0;
	before[bk++] = getInstrPtr(mb, 0);	/* to become a factory */

	setLifespan(mb);
	for (i = 1; i < mb->stop - 1; i++) {
		p = getInstrPtr(mb, i);
		if (blockStart(p)) {
			if (blkbegin == 0){
				if( isLoopBarrier(mb,i) ){
					blkbegin = i;
					blkexit = getBlockExit(mb,i);
				}
#ifdef DEBUG_OPT_STRENGTHREDUCTION
			stream_printf(GDKout, "check block %d-%d\n", blkbegin, blkexit);
#endif
			}
			within[ik++] = p;
			blk++;
			continue;
		}
		if (blockExit(p)) {
			blk--;
			if (blk == 0)
				blkexit= blkbegin = 0;
			/* move the saved instruction into place */
#ifdef DEBUG_OPT_STRENGTHREDUCTION
			stream_printf(GDKout, "combine both %d %d\n", bk, ik);
#endif
			for (k = 0; k < ik; k++)
				before[bk++] = within[k];
			ik = 0;
			before[bk++] = p;
			continue;
		}
@-
Strength reduction is only relevant inside a block;
@c
		if( blkexit == 0) {
			within[ik++] = p;
			continue;
		}
@-
Flow control statements may not be moved around
@c
		if ( p->barrier != 0){
			within[ik++] = p;
			continue;
		}
@-
Limit strength reduction to the type modules and the batcalc, batstr, batcolor
@c
		if( !isNewSource(p) ) {
			within[ik++] = p;
			continue;
		}
@-
Search the prospective new block and make sure that
none of the arguments is assigned a value.
@c
		for (j = ik-1; j > 0; j--) {
			InstrPtr q = within[j];
			for (k = 0; k < q->retc; k++)
				if (SRoverwritten(p, getArg(q, k))) {
					se = TRUE;
#ifdef DEBUG_OPT_STRENGTHREDUCTION
					stream_printf(GDKout, "variable is set in loop %d\n", 
						getArg(p, k));
#endif
					goto noreduction;
				}
		}
@-
Make sure the variables are not declared before the loop and used
after the loop, because then you may not simple move an expression.
@c
		for (k = 0; k < p->retc; k++)
			if ( getVar(mb, getArg(p, k))->beginLifespan <= blkbegin ||
				 getVar(mb, getArg(p, k))->endLifespan >= blkexit) {
				se = TRUE;
#ifdef DEBUG_OPT_STRENGTHREDUCTION
				stream_printf(GDKout, "variable may not be used out %d\n", getArg(p, k));
#endif
				goto noreduction;
			}

  noreduction:
#ifdef DEBUG_OPT_STRENGTHREDUCTION
		stream_printf(GDKout,"move %d to stack %s\n", i, (se ?"within":"before"));
		printInstruction(GDKout, mb, p, LIST_MAL_ALL);
#endif
		if (blkexit && se == FALSE && !hasSideEffects(p, TRUE) )
			before[bk++] = p;
		else
			within[ik++] = p;
	}
	actions += ik;
	for (k = 0; k < ik; k++)
		before[bk++] = within[k];
	before[bk++] = getInstrPtr(mb, i);
	GDKfree(mb->stmt);
	mb->stmt = (InstrPtr *) GDKzalloc((mb->ssize) * sizeof(InstrPtr));
	mb->stop = 0;

#ifdef DEBUG_OPT_STRENGTHREDUCTION
	stream_printf(GDKout,"stop= %d bk=%d\n",mb->stop,bk);
#endif
	for (i = 0; i < bk; i++)
	if( before[i])
		pushInstruction(mb, before[i]);
	return actions;
}
@include optimizerWrapper.mx
@h
@:exportOptimizer(strengthReduction)@
@c
@:wrapOptimizer(strengthReduction,OPT_CHECK_ALL)@
@}