opt_singleton.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_singleton
@a M. Kersten
@- Singleton Set Reduction
Application semantics and precise cost analysis may
identify the result of an operation to produce a BAT with
a single element. Such variables can be tagged with the
property @sc{singleton}, whereafter the operation
@sc{optimizer.singleton()} derives an MAL program
using a symbolic evaluation as far as possible.

During its evaluation, more singleton sets can be created, 
leading to a ripple effect through the code.
A non-optimizable instruction leads to
a construction of a new table with the single instance.

	@verbatim
	b:= bat.new(:int,:int);
	bat.insert(b,1,2);
	c{singleton}:= algebra.select(b,0,4);
	d:= algebra.markH(c);
	io.print(d);
	optimizer.singleton();
@end verbatim
is translated by into the code block
@verbatim
	b := bat.new(:int,:int);
	bat.insert(b,1,2);
	c{singleton} := algebra.select(b,0,4);
	(_15,_16):= bat.unpack(c{singleton});
	d := bat.pack(nil,_16);
	io.print(d);
@end verbatim
@{
@mal
pattern optimizer.singleton():str
address OPTsingleton;
pattern optimizer.singleton(mod:str, fcn:str):str
address OPTsingleton
comment "Perform singleton optimization";

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

/* #define DEBUG_OPT_SINGLETON     show partial result */
#endif
@c
#include "mal_config.h"
#include "opt_singleton.h"
#include "opt_aliases.h"
#include "mal_interpreter.h"	/* for showErrors() */
#include "mal_builder.h"

@-
When we run into an instruction that can not be optimized,
we have to rebuild the singleton set as an ordinary BAT.
@c
typedef struct {
	int vidx;
	int hidx;
	int htpe;
	int tidx;
	int ttpe;
	int packed;
} STtuple;

static int
STalias(int idx, int top, STtuple * tuples)
{
	int i;

	for (i = 0; i < top; i++)
		if (tuples[i].vidx == idx)
			return i;
	return -1;
}

static int
STnewTuple(MalBlkPtr mb, int vidx, int *top, STtuple * tuples)
{
	tuples[*top].packed = 1;
	tuples[*top].vidx = vidx;
	tuples[*top].htpe = getHeadType(getVarType(mb, vidx));
	tuples[*top].htpe= TYPE_oid;
	tuples[*top].hidx = newTmpVariable(mb, tuples[*top].htpe);
	tuples[*top].ttpe = getTailType(getVarType(mb, vidx));
	tuples[*top].tidx = newTmpVariable(mb, tuples[*top].ttpe);
	*top = *top + 1;
	return *top - 1;
}

static void
STunpack(MalBlkPtr mb, int varid, STtuple * tuples)
{
	InstrPtr p = 0;

	if (tuples[varid].packed == 0)
		return;

	p = newFcnCall(mb, batRef, unpackRef);
	getArg(p, 0) = tuples[varid].hidx;
	setVarUsed(mb,getArg(p,0),TRUE);
	setArgument(mb, p, 1, tuples[varid].tidx);
	setVarUsed(mb,getArg(p,1),TRUE);
	p->retc++;
	pushArgument(mb, p, tuples[varid].vidx);
	tuples[varid].packed = 0;
}

static void
STpack(MalBlkPtr mb, int varid, STtuple * tuples)
{
	InstrPtr p = 0;

	p = newFcnCall(mb, batRef, packRef);
	getArg(p, 0) = tuples[varid].vidx;
	p->retc = 1;
	p->argc = 1;
	pushArgument(mb, p, tuples[varid].hidx);
	pushArgument(mb, p, tuples[varid].tidx);
}

static int
STevaluate(MalBlkPtr mb, int cnt, int *vars)
{
	int i, j = 0, k, limit, actions = 0;
	InstrPtr p;
	InstrPtr *old;
	STtuple *tuples;
	int top = 0;

	if( mb->errors) 
		return 0;
	tuples = alloca(mb->stop * sizeof(STtuple));
	limit = mb->stop;
	old = mb->stmt;

@-
Prepare the list of tuple aliases using allocation of
variables on the stack.
@c
	for (i = 0; i < cnt; i++)
		STnewTuple(mb, vars[i], &top, tuples);
#ifdef DEBUG_OPT_SINGLETON
	stream_printf(GDKout, "START SINGLETON OPTIMIZER %d:", cnt);
	for (i = 0; i < top; i++)
		stream_printf(GDKout, "[%d,%d,%d] ", vars[i], tuples[i].hidx, tuples[i].tidx);
	stream_printf(GDKout, "\n");
	printFunction(GDKout, mb, LIST_MAL_ALL);
	stream_printf(GDKout, "START OPTIMIZER ");
#endif
	newMalBlkStmt(mb, mb->stop);

	for (i = 0; i < limit; i++) {
		p = old[i];
		/* decode operations */
		if (getModuleId(p) == batRef) {
			if (getFunctionId(p) == reverseRef && 
				(k = STalias(getArg(p, 1), top, tuples) >= 0)) {
				setModuleId(p, NULL);
				setFunctionId(p, NULL);
				p->retc = p->argc = 2;
				pushArgument(mb, p, tuples[k].hidx);
				pushArgument(mb, p, tuples[k].tidx);
				k = STnewTuple(mb, getArg(p, 0), &top, tuples);
				p->argv[0] = tuples[k].hidx;
				p->argv[1] = tuples[k].tidx;
				p->token= ASSIGNsymbol;
				actions++;
			} else
				goto STrepack;
		} else if (getModuleId(p)== ioRef) {
			if (getFunctionId(p) == printRef &&
				p->argc == 3 && 
				(k = STalias(getArg(p, 1), top, tuples)) >= 0) {
				if (tuples[k].packed == 0) {
					getArg(p, 1) = tuples[k].hidx;
					pushArgument(mb, p, tuples[k].tidx);
				} else
					goto STrepack;
			} else
				goto STrepack;
		} else if (getModuleId(p) == algebraRef) {
			if (getName("markH", 5) == getFunctionId(p) && 
				(k = STalias(getArg(p, 1), top, tuples)) >= 0) {
				STunpack(mb, k, tuples);
				setModuleId(p, NULL);
				setFunctionId(p, NULL);
				p->retc = p->argc = 2;
				pushOid(mb, p,0);
				pushArgument(mb, p, tuples[k].tidx);
				k = STnewTuple(mb, getArg(p, 0), &top, tuples);
				tuples[k].packed = 0;
				p->argv[0] = tuples[k].hidx;
				setVarUsed(mb,getArg(p,0),TRUE);
				p->argv[1] = tuples[k].tidx;
				setVarUsed(mb,getArg(p,1),TRUE);
				p->token = ASSIGNsymbol;
				p->fcn = NULL;
				actions++;
			} else if (getFunctionId(p) == markTRef && 
						(k = STalias(getArg(p, 1), top, tuples)) >= 0) {
				STunpack(mb, k, tuples);
				setModuleId(p, NULL);
				setFunctionId(p, NULL);
				p->retc = p->argc = 2;
				pushArgument(mb, p, tuples[k].hidx);
				pushOid(mb, p,0);
				k = STnewTuple(mb, getArg(p, 0), &top, tuples);
				tuples[k].packed = 0;
				p->argv[0] = tuples[k].hidx;
				setVarUsed(mb,getArg(p,0),TRUE);
				p->argv[1] = tuples[k].tidx;
				setVarUsed(mb,getArg(p,1),TRUE);
				p->token = ASSIGNsymbol;
				p->fcn = NULL;
				actions++;
			} else if (getFunctionId(p) == joinRef) {
				int k1 = STalias(getArg(p, 1), top, tuples);
				int k2 = STalias(getArg(p, 2), top, tuples);

				if (k1 >= 0 && k2 >= 0) {
					if (tuples[k2].htpe == TYPE_oid && tuples[k1].htpe == TYPE_oid) {
						STunpack(mb, k1, tuples);
						STunpack(mb, k2, tuples);
						printf("MERGE VOID JOIN \n");
						setModuleId(p, NULL);
						setFunctionId(p, NULL);
						STnewTuple(mb, getArg(p, 0), &top, tuples);
						p->argc = 0;
						pushReturn(mb, p, tuples[top - 1].hidx);
						pushReturn(mb, p, tuples[top - 1].tidx);
						p->retc = 2;
						pushArgument(mb, p, tuples[k1].hidx);
						pushArgument(mb, p, tuples[k2].tidx);
						p->token = ASSIGNsymbol;
						p->fcn = NULL;
					}
				} else if (k1 >= 0) {
					goto STrepack;
				} else if (k2 >= 0) {
					goto STrepack;
				} else
					goto STrepack;
				/* just push instruction */
			} else
/*
				getName("kunion",6)== getFunctionId(p) ||
				getFunctionId(p) == joinRef ||
				getName("fetchjoin",9)== getFunctionId(p) ||
				getName("mergejoin",9)== getFunctionId(p) ||
				getName("indexjoin",9)== getFunctionId(p) ||
				getName("hashjoin",8)== getFunctionId(p) ||
				getName("cartesianproduct",16)== getFunctionId(p) ||
				getName("union",5)== getFunctionId(p) )
*/
			if (getFunctionId(p) == countRef && 
				(k = STalias(getArg(p, 1), top, tuples)) >= 0) {
				STunpack(mb, k, tuples);
				/* count propagation */
				setModuleId(p, NULL);
				setFunctionId(p, NULL);
				p->argc = 1;
				p->token = ASSIGNsymbol;
				pushLng(mb,p,1);
			} else {
			STrepack:
				/* pack everything you need */
				for (j = 0; j < p->argc; j++)
					if ((k = STalias(getArg(p, j), top, tuples)) >= 0 && tuples[k].packed == 0)
						STpack(mb, k, tuples);
			}
		} else if (getName("datacell", 8) == getModuleId(p)) {
			if (getName("bindReceptor", 12) && (k = STalias(getArg(p, 0), top, tuples)) >= 0) {
				setFunctionId(p, putName("bindReceptorTuple", 17));
				getArg(p, 0) = tuples[k].hidx;
				setArgument(mb, p, 1, tuples[k].tidx);
				p->retc++;
				tuples[k].packed = 0;
			} else if (getName("keep", 4) && p->argc >= 3 && (k = STalias(getArg(p, 3), top, tuples)) >= 0) {
				getArg(p, 3) = tuples[k].tidx;
			}
		} else {
			/* check for any target alias */
			for (j = 0; j < p->retc; j++)
				for (k = 0; k < top; k++)
					if (getArg(p, j) == tuples[k].vidx) {
						getArg(p, j) = tuples[k].hidx;
						setArgument(mb, p, j + 1, tuples[k].tidx);
						p->retc++;
					}
		}
		pushInstruction(mb, p);
	}
#ifdef DEBUG_OPT_SINGLETON
	if (actions) {
		printf("FINAL STAGE actions=%d\n", actions);
		printFunction(GDKout, mb, LIST_MAL_ALL);
		for (i = 0; i < top; i++)
			stream_printf(GDKout, "[%d,%d:%s,%d:%s] ", tuples[i].vidx, tuples[i].hidx, getTypeName(tuples[i].htpe), tuples[i].tidx, getTypeName(tuples[i].ttpe));
		stream_printf(GDKout, "\n");
	}
#endif
	GDKfree(old);

#ifdef DEBUG_OPT_SINGLETON
	printf("FINAL STAGE SINGLETON errors=%d\n", mb->errors);
	printFunction(GDKout, mb, LIST_MAL_ALL);
#endif
	return actions;
}

static int
OPTsingletonImplementation(MalBlkPtr mb, MalStkPtr stk, InstrPtr p)
{
	int *vars;
	int cnt = 0, i, j;

	(void) stk;
	vars = (int *) alloca(mb->vtop);

	for (i = 1; i < mb->stop; i++) {
		p = getInstrPtr(mb, i);
		for (j = 0; j < p->retc; j++)
			if (fndProperty(getVarProperties(mb, getArg(p, j)), "singleton")) {
				vars[cnt++] = getArg(p, j);
			}
	}
	return STevaluate(mb, cnt, vars);
}

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