opt_support.mx

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

@tab    Accumulator Evaluations.
@item 
@tab    Result Cacher.
@item
@tab	Replication Manager.

@item group E:
@tab    MAL Compiler.
@item 
@tab    Dynamic Query Scheduler.
@item 
@tab    Vector Execution.
@item 
@tab    Staged Execution.

@item group F:
@tab    Alias Removal.
@item 
@tab    Dead Code Removal.
@item 
@tab    Garbage Collector.
@end multitable
@-
Alias removal can be applied after each other optimization step.
@node Building Blocks, Framework, Dependencies, The MAL Optimizer
@- Optimizer Building Blocks

Some instructions are independent of the execution context. In particular,
expressions over side-effect free functions with constant parameters could
be evaluated before the program block is considered further.

A major task for an optimizer is to select instruction (sequences) which
can and should be replaced with cheaper ones. The cost model underlying
this decision depends on the processing stage and the overall objective.
For example, based on a symbolic analysis their may exist better 
implementations within the interpreter to perform the job (e.g. hashjoin vs
mergejoin). Alternative, expensive intermediates may be cached for later use.

Plan enumeration is often implemented as a Memo structure, which
designates alternative sub-plans based on a cost metric.
Perhaps we can combine these memo structures into a large table
for all possible combinations encountered for a user.

The MAL language does not imply a specific optimizer to be used. Its programs
are merely a sequence of specifications, which is interpreted by an engine
specific to a given task. Activation of the engine is controlled by a 
scenario, which currently includes two hooks for optimization; a 
strategic optimizer and a tactical optimizer.
Both engines take a MAL program and produce a (new/modified) MAL program for 
execution by the lower layers. 

MAL programs end-up in the symbol table linked to a user session.
An optimizer has the freedom to change the code, provided it is known that
the plan derived is invariant to changes in the environment.
All others lead to alternative plans, which should be collected as a trail of
MAL program blocks. These trails can be inspected for a
posteriori analysis, at least in terms of some statistics on the properties
of the MAL program structures automatically.
Alternatively, the trail may be pruned and re-optimized when appropriate
from changes in the environment.

Breaking up the optimizer into different components and
grouping them together in arbitrary sequences calls for
careful programming.

The rule applied for all optimizers is to not-return
before checking the state of the MAL program,
and to assure the dataflow and variable scopes are properly set.
It costs some performance, but the difficulties
that arise from optimizer interference are very hard to debug.
One of the easiest pitfalls is to derive an optimized
version of a MAL function while it is already referenced by or
when polymorphic typechecking is required afterwards.
@{
The optimizers defined here are registered to the optimizer module.
@mal
pattern optimizer.heuristics():str
address OPTheuristics;
pattern optimizer.heuristics(mod:str, fcn:str):str
address OPTheuristics
comment "Handle simple replacements";

@h
#include "mal.h"
#include "mal_function.h"
#include "mal_scenario.h"
#include "mal_builder.h"

/* #define DEBUG_OPT_OPTIMIZER     show partial result */

#ifdef WIN32
#ifndef LIBOPTIMIZER
#define opt_export extern __declspec(dllimport)
#else
#define opt_export extern __declspec(dllexport)
#endif
#else
#define opt_export extern
#endif

opt_export str MALoptimizer(Client c);
opt_export int optimizerCheck(MalBlkPtr mb, str name, int actions, lng usec, int flag);
opt_export void resetOptimizerDebugger(void);
opt_export str optimizeMALBlock(MalBlkPtr mb);
opt_export void showOptimizerStep(str fnme,int i, int flg);
opt_export void showOptimizerHistory(void);
opt_export str debugOptimizers(MalBlkPtr mb, MalStkPtr stk, InstrPtr pci);
opt_export void replaceAlias(MalBlkPtr mb, int pc, int pcl, int src, int alias);

opt_export int isUnsafeInstruction(InstrPtr q);
opt_export int isUnsafeFunction(InstrPtr q);
opt_export int isInvariant(MalBlkPtr mb, int pcf, int pcl, int varid);
opt_export int isDependent(InstrPtr p, InstrPtr q);
opt_export int safetyBarrier(InstrPtr p, InstrPtr q);
opt_export int hasSameSignature(InstrPtr p, InstrPtr q);
opt_export int hasSameArguments(MalBlkPtr mb, InstrPtr p, InstrPtr q);
opt_export int isUpdated(MalBlkPtr mb, int pc);
opt_export int hasCommonResults(InstrPtr p, InstrPtr q);
opt_export int hasSideEffects(InstrPtr p, int strict);
opt_export int allArgumentsVisible(MalBlkPtr mb, int pc,int qc);
opt_export int allTargetsVisible(MalBlkPtr mb, int pc, int qc);

#define isAlife(M,I,X)          ( (M)->var[I]->beginLifespan<=X && \
                                  (M)->var[I]->endLifespan>=X)
#define isSinglepoint(M,I)  ( (M)->var[I]->beginLifespan== \
                  (M)->var[I]->endLifespan)
@}
@-
@node Framework, Lifespan Analysis, Building Blocks, The MAL Optimizer
@subsection Optimizer framework
The large number of query transformers calls for a flexible scheme for
the deploy them. The approach taken is to make all optimizers visible
at the language level as a MAL pattern. Then (semantic) optimizer merely
inspects a MAL block for their occurrences and activitates it.

Furthermore, the default optimizer scheme can be associated with
a client record. The strategic optimizer merely prepends each query with 
this scheme before it searches/activates the optimizer routines.

The optimizer routines have access to the client context, the MAL block,
and the program counter where optimizer call was found. Each query
transformer should remove itself from the MAL block;

The optimizer terminates when no optimizer transformer call remains.
[Some of the optimizers above should be moved to the tactic level]

Note, all optimizer instructions are executed only once. This means that the
instruction can be removed from further consideration. However, in the case
that a designated function is selected for optimization (e.g. 
commonTerms(user,qry)) the pc is assumed 0. The first instruction always
denotes the signature and can not be removed.

To safeguard against incomplete optimizer implementations it
is advisable to perform an optimizerCheck at the end.
It takes as arguments the number of optimizer actions taken
and the total cpu time spent.
The body performs a full flow and type check and re-initializes
the lifespan administration. In debugging mode also a copy
of the new block is retained for inspection.

@node Lifespan Analysis, Flow Analysis, Framework, The MAL Optimizer
@subsection Lifespan analysis
Optimizers may be interested in the characteristic of the
barrier blocks for making a decision.
The variables have a lifespan in the code blocks, denoted by properties
beginLifespan,endLifespan. The beginLifespan denotes the intruction where
it receives its first value, the endLifespan the last instruction in which
it was used as operand or target.

If, however, the last use lies within a BARRIER block, we can not be sure
about its end of life status, because a block redo may implictly
revive it. For these situations we associate the endLifespan with
the block exit.

In many cases, we have to determine if the lifespan interferes with
a optimization decision being prepared.
The lifespan is calculated once at the beginning of the optimizer sequence.
It should either be maintained to reflect the most accurate situation while
optimizing the code base. In particular it means that any move/remove/addition
of an instruction calls for either a recalculation or delta propagation.
Unclear what will be the best strategy. For the time being we just recalc.
@{
If one of the optimizers fails, we should not attempt others.
@c
#include "mal_config.h"
#include "opt_prelude.h"
#include "opt_support.h"
#include "mal_interpreter.h"
#include "mal_debugger.h"


@-
The optimizerCheck is defensive. In some cases, e.g. coercion,
a light check would be sufficient. Such a refinement is left
for the future using an additional flag.
@h
#define OPT_CHECK_FLOW	1
#define OPT_CHECK_TYPES 2
#define OPT_CHECK_DECL 4
#define OPT_CHECK_SPAN 8

#define OPT_CHECK_ALL (OPT_CHECK_FLOW | OPT_CHECK_TYPES | OPT_CHECK_DECL | OPT_CHECK_SPAN)
@c
int
optimizerCheck(MalBlkPtr mb, str name, int actions, lng usec, int flag)
{
	Client cntxt = MCgetClient();
	if( actions > 0){
		if( flag & OPT_CHECK_TYPES) chkTypes(cntxt->nspace, mb);
		if( flag & OPT_CHECK_FLOW) chkFlow(mb);
		if( flag & OPT_CHECK_DECL) chkDeclarations(mb, TRUE);
		if( flag & OPT_CHECK_SPAN) setLifespan(mb);
	}
	if( cntxt->debugOptimizer){
		/* keep the actions take as post block comments */
		char buf[BUFSIZ];
		InstrPtr p= getInstrPtr(mb,mb->stop-1);
		sprintf(buf,"actions=%d time=" LLFMT " usec %s",actions,usec,name);
		if( p->token == REMsymbol)
			removeInstruction(mb,p);
		newComment(mb,buf);
		if (mb->errors) {
			showErrors();
			stream_printf(GDKout, "Optimizer %s failed\n", name);
			printFunction(GDKout, mb, LIST_MAL_ALL);
		}
	}
	return mb->errors;
}
@-
Limit the loop count in the optimizer.
@c
str
optimizeMALBlock(MalBlkPtr mb)
{
	InstrPtr p;
	int pc, qot = 0;
	str msg = MAL_SUCCEED;
	int cnt = 0;
	InstrPtr *optimizers= alloca(sizeof(InstrPtr)*256);

#ifdef DEBUG_OPT_OPTIMIZER
	int oldstop = mb->stop;
#endif

	optimizerInit();
	/* assume the type and flow have been checked already */
	do {
		qot = 0;
		for (pc = 0; pc < mb->stop && qot<256; pc++) {
			p = getInstrPtr(mb, pc);
			if (getModuleId(p) == optimizerRef && p->fcn) 
				optimizers[qot++]= p;
		}
		/* we collected all optimizers known so far */
		for( pc=0; pc<qot; pc++)
			if (optimizers[pc]->fcn)
				/* all optimizers should behave like patterns */
				/* However, we don;t have a stack now */
				msg = (str) (*optimizers[pc]->fcn) (mb, 0, optimizers[pc]);
			else {
				msg = createException(MAL, "optimizer", "Implementation missing");
				printInstruction(GDKout,mb,optimizers[pc],LIST_MAL_ALL);
			}
			if (msg) {
				str place = getExceptionPlace(msg);
				showException(getExceptionType(msg), place, getExceptionMessage(msg));
				GDKfree(place);
				showErrors();
				return msg;
			}
	} while (qot && cnt++ < 64);
#ifdef DEBUG_OPT_OPTIMIZER
	stream_printf(GDKout, "Optimizer effect %d -> %d instructions\n", 
			oldstop, mb->stop);
#endif
	if (cnt >= 64)
		throw(MAL, "optimizer.MALoptimizer", "too many optimization cycles\n");
	return 0;
}

str
MALoptimizer(Client c)
{
	return optimizeMALBlock(c->curprg->def);
}

int hasSameSignature(InstrPtr p, InstrPtr q){   
	if( q->retc != p->retc || q->argc != p->argc) return FALSE;
	if( getFunctionId(q)==0 && getFunctionId(p)!=0 ) return FALSE;
	if( getFunctionId(q)!=0 && getFunctionId(p)==0 ) return FALSE;
	if( getFunctionId(q) && getFunctionId(p) && idcmp(getFunctionId(q),getFunctionId(p)) ) 
		return FALSE;
	if( getModuleId(q)==0 && getModuleId(p)!=0 ) return FALSE;
	if( getModuleId(q)!=0 && getModuleId(p)==0 ) return FALSE;
	if( getModuleId(q) && getModuleId(p) && idcmp(getModuleId(q),getModuleId(p)))
		return FALSE;
	/* actually also check their types */
	return TRUE;
}

int hasSameArguments(MalBlkPtr mb, InstrPtr p, InstrPtr q)
{   int k;
	(void) mb;
	if( p== NULL || q== NULL || p->retc != q->retc || p->argc != q->argc)
		return FALSE;
	for(k=p->retc; k<p->argc;k++)
		if( q->argv[k]!= p->argv[k]){
			if( isConstant(mb,getArg(p,k)) && isConstant(mb,getArg(q,k)) ) {
					ValPtr w,u;
					w= &getVarConstant(mb,getArg(p,k));
					u= &getVarConstant(mb,getArg(q,k));

					if( ATOMcmp(w->vtype, VALptr(w), VALptr(u)) == 0)
						continue;
			}
			return FALSE;
		}
	return TRUE;
}
@-
If two instructions have elements in common in their target list,
it means a variable is re-initialized and should not be considered
an alias.
@c
int
hasCommonResults(InstrPtr p, InstrPtr q)
{
	int k, l;

	for (k = 0; k < p->retc; k++)
		for (l = 0; l < q->retc; l++)
			if (p->argv[k] == q->argv[l])
				return TRUE;
	return FALSE;
}
@-
Dependency between target variables and arguments can be
checked with isDependent().
@c
int
isDependent(InstrPtr p, InstrPtr q){
	int i,j;
	for(i= 0; i<q->retc; i++)
	for(j= p->retc; j<p->argc; j++)
		if( getArg(q,i)== getArg(p,j)) return TRUE;
	return FALSE;
}
@-
See is all arguments mentioned in the instruction at point pc
are still visible at instruction qc and have not been updated
in the mean time.
Take into account that variables may be declared inside
a block. This can be calculated using the BARRIER/CATCH
and EXIT pairs.
@c
int
countBlocks(MalBlkPtr mb, int start, int stop){
	int i,cnt =0;
	InstrPtr p;
	for(i= start; i< stop; i++){