opt_macro.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_macro
@a M. L. Kersten
@- Macro and Orcam Processing
The optimizers form the basis for replacing code fragments.
Two optimizers are focused on code expansion and contraction.
The former involves replacing individual instructions by a block of
MAL code, i.e. a @sc{macro} call.
The latter depicts the inverse operation, a group of instructions
is replaced by a single MAL assignment statement, i.e. a @sc{orcam}
call.

The macro facility is limited to type-correct MAL functions,
which means that replacement is not essential from a semantic
point of view. They could have been called, or the block need
not be compressed. It is equivalent to inline code expansion.

The @sc{macro} and @sc{orcam} transformations provide 
a basis to develop front-end specific code generation templates.
The prototypical test case is the following template:
@example
function user.joinPath( a:bat[:any_1,:any_2],
                b:bat[:any_2,:any_3],
                c:bat[:any_3,:any_4]):bat[:any_1,:any_4]
address fastjoinpath;
    z:= join(a,b);
    zz:= join(z,c);
    return zz;
end user.joinPath;
@end example

The call @sc{optimizer.macro("user", "joinPath")} hunts
for occurrences of the instruction call in the block in
which it is called
and replaces it with the body, i.e. it in-lines the code.
Conversely,  the @sc{optimizer.orcam("user", "joinPath")}
attempts to localize a block of two join operations and,
when found, it is replaced by the direct call to @sc{joinPath}.
In turn, type resolution then directs execution to a built-in
function @sc{fastjoinpath}.

The current implementation is limited to finding a consecutive
sequence, ending in a return-statement. The latter is needed to
properly embed the result in the enclosed environment.
It may be extended in the future to consider the flow of control as well.

@{
After both operations the flow of control structure has to be
checked and for contraction we also have to resolve the new
code, e.g. to bind the new instruction with an implementation.
(Or become part of a macro expansion)

The implementation is based on matching MAL instructions.
This means they address the same function, but also that their 
variables are isomorphic.
The generalization of malMatch is malFcnMatch, which checks
equivalence of a function body as an occurrence in another one.
@}

The optimizer can be targeted to a function @sc{user.foo()}
using the call @sc{optimizer.macro("user","foo","user","joinPath");
@- Known issues. 
The functions subject to expansion or contraction should be
checked on 'proper' behavior.

The current implementation is extremely limited. 
The @sc{macro} optimizer does not recognize use of intermediate results 
outside the block being contracted. This should be checked and
it should block the replacement, unless the intermediates are part of
the return list.
Likewise, we assume here that the block has a single return
statement, which is also the last one to be executed.

The @sc{macro} optimizer can only expand functions. Factories already
carry a significant complex flow of control that is hard
to simulate in the nested flow structure of an arbitrary function.

The @sc{orcam} optimizer can not deal with calls controlled by a barrier.
It would often require a rewrite of several other statements as well.

@mal
pattern optimizer.macro(targetmod:str,targetfcn:str):void
address OPTmacro
comment "Inline the code of the target function.";
pattern optimizer.macro(mod:str,fcn:str,targetmod:str,targetfcn:str):void
address OPTmacro
comment "Inline a target function used in a specific function.";

pattern optimizer.orcam(targetmod:str,targetfcn:str):void
address OPTorcam
comment "Inverse macro processor for current function";
pattern optimizer.orcam(mod:str,fcn:str,targetmod:str,targetfcn:str):void
address OPTorcam
comment "Inverse macro, find pattern and replace with a function call.";

@-
@{
#pattern optimizer.macro(targetmod:str):void
#address OPTmacro
#comment "Inline functions known a specific module.";
#pattern optimizer.orcam(targetmod:str):void
#address OPTorcam
#comment "Inverse macro processor for a module";
@+ Implementation section
@h
#ifndef _MAL_MACRO_H_
#define _MAL_MACRO_H_

/* #define DEBUG_OPT_MACRO*/

opt_export str MACROprocessor(MalBlkPtr mb, Symbol t);
opt_export int inlineMALblock(MalBlkPtr mb, int pc, MalBlkPtr mc);
#endif /* _MAL_MACRO_H_ */
@-
@c
#include "mal_config.h"
#include "opt_prelude.h"
#include "opt_macro.h"
#include "mal_interpreter.h"

@-
The optimizer hooks are introduced first.
They are refered to from the optimizer module.
@c
static int
malMatch(InstrPtr p1, InstrPtr p2)
{
	int i, j;

	if (getFunctionId(p1) == 0 && getFunctionId(p2) != 0)
		return 0;
	if (getModuleId(p1) == 0 && getModuleId(p2) != 0)
		return 0;
	if (getModuleId(p1) != getModuleId(p2))
		return 0;
	if (getFunctionId(p2) == 0)
		return 0;
	if (getFunctionId(p1) != getFunctionId(p2))
		return 0;
	if (p1->retc != p2->retc)
		return 0;
	if (p1->argc != p2->argc)
		return 0;
	if (p1->barrier != p2->barrier)
		return 0;
	for (i = 0; i < p1->argc; i++)
		for (j = i + 1; j < p1->argc; j++)
			if ((getArg(p1, i) == getArg(p1, j) && getArg(p2, i) != getArg(p2, j)) || (getArg(p1, i) != getArg(p1, j) && getArg(p2, i) == getArg(p2, j)))
				return 0;
	return 1;
}

@-
Matching a block calls for building two variable lists used.
The isomorphism can be determined after-wards using a single scan.
The candidate block is matched with mb starting at a given pc.
The candidate block is expected to defined as a function, including
a signature and end-statement. They are ignored in the comparison

Beware, the variables in the block being removed, could be
used furtheron in the program. [tricky to detect, todo]
@c
static int
malFcnMatch(MalBlkPtr mc, MalBlkPtr mb, int pc)
{
	int i, j, k, lim;
	int *cvar, *mvar;
	int ctop = 0, mtop = 0;
	InstrPtr p, q;

	if (mb->stop - pc < mc->stop - 2)
		return 0;

	cvar = (int *) alloca(mc->vtop * MAXARG);

	mvar = (int *) alloca(mb->vtop * MAXARG);
	/* also trim the return statement */
	lim = pc + mc->stop - 3;
	k = 1;
	for (i = pc; i < lim; i++, k++) {
		p = getInstrPtr(mb, i);
		q = getInstrPtr(mc, k);
		if (malMatch(p, q) == 0)
			return 0;
		for (j = 0; j < p->argc; j++)
			cvar[ctop++] = getArg(p, j);

		for (j = 0; j < p->argc; j++)
			mvar[mtop++] = getArg(q, j);
	}
	assert(mtop == ctop);	/*shouldn;t happen */
#ifdef DEBUG_OPT_MACRO
	for (i = 0; i < ctop; i++)
		printf("match %d %d\n", cvar[i], mvar[i]);
#endif
	for (i = 0; i < ctop; i++)
		for (j = i + 1; j < ctop; j++)
			if ((cvar[i] == cvar[j] && mvar[i] != mvar[j]) ||(mvar[i] == mvar[j] && cvar[i] != cvar[j]))
				return 0;
	return 1;
}

@- Macro expansions
The macro expansion routine walks through the MAL code block in search
for the function to be expanded.  
The macro expansion process is restarted at the first new instruction.
A global is used to protect at (direct) recursive expansions
@c
#define MAXEXPANSION 256

int
inlineMALblock(MalBlkPtr mb, int pc, MalBlkPtr mc)
{
	int i, k, l, n;
	InstrPtr *ns, p,q;
	int *nv;

#ifdef DEBUG_OPT_MACRO
	printf("inlineMALblock\n");
	printFunction(GDKout,mb,LIST_MAL_ALL);
	printFunction(GDKout,mc,LIST_MAL_ALL);
#endif
	ns = GDKmalloc((l = (mb->ssize + mc->ssize - 3)) * sizeof(InstrPtr));
	nv = alloca(mc->vtop * sizeof(int));
	p = getInstrPtr(mb, pc);
	q = getInstrPtr(mc, 0);
	k = 0;

	/* add variables to target */
	for (n = 0; n < mc->vtop; n++) {
		if (mc->var[n]->isaconstant ){
			nv[n] = cpyConstant(mb,getVar(mc,n));
		} else
			nv[n] = newTmpVariable(mb, getVarType(mc, n));
		k++;
	}

	/* keep track of the actual arguments */
	for (n = 0; n < p->argc; n++)
		nv[getArg(q,n)] = getArg(p, n);
	k = 0;

	/* copy the stable part */
	for (i = 0; i < pc; i++)
		ns[k++] = mb->stmt[i];

	/* copying stops at the first return statement */
	for (i = 1; i < mc->stop - 1; i++) {
		p = mc->stmt[i];

		/* copy the instruction and fix variable references */
		ns[k] = copyInstruction(p);
		for (n = 0; n < p->argc; n++) 
			getArg(ns[k], n) = nv[getArg(p, n)];

		if (p->barrier == RETURNsymbol || p->barrier == YIELDsymbol) {
			ns[k]->barrier = 0;
			if (p->token == RETURNsymbol || p->token == YIELDsymbol)
				ns[k]->token = ASSIGNsymbol;
			/* fix returns that do not evaluate an expression */
			if( p->retc == p->argc){
				for (n =0; n < p->retc; n++) {
					pushArgument(mb,ns[k], nv[getArg(p,n)]);
					getArg(ns[k],n)= getArg(getInstrPtr(mb,pc),n);
				}
			} 
			k++;
			break;
		}
		k++;
	}
	/* copy the stable part */
	for (i = pc + 1; i < mb->stop; i++)