opt_support.mx

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

		p= getInstrPtr(mb,i);
		if ( p->barrier == BARRIERsymbol || p->token== CATCHsymbol)
			cnt++;
		if ( p->barrier == EXITsymbol )
			cnt--;
	}
	return cnt;
}
int
allArgumentsVisible(MalBlkPtr mb, int pc,int qc){
	int i;
	InstrPtr p;

	if( countBlocks(mb,pc,qc) )
		return FALSE;
	p= getInstrPtr(mb,pc);
	for(i=p->retc; i< p->argc; i++){
		VarPtr v = getVar(mb, getArg(p,i));
		if( v->lastUpdate > v->beginLifespan && qc > v->lastUpdate)
			return FALSE;
	}
	return TRUE;
}
int
allTargetsVisible(MalBlkPtr mb, int pc,int qc){
	int i;
	InstrPtr p;

	if( countBlocks(mb,pc,qc) )
		return FALSE;
	p= getInstrPtr(mb,pc);
	for(i=0; i < p->retc; i++){
		VarPtr v = getVar(mb, getArg(p,i));
		if( v->lastUpdate > v->beginLifespan && qc > v->lastUpdate)
			return FALSE;
	}
	return TRUE;
}
@}
@-
For each function it should be relatively easy to determine its
safety property. This calls for accessing the function MAL block
and to inspect the arguments of the signature.
@{
@c
int
isUnsafeFunction(InstrPtr q)
{
	InstrPtr p;

	if (q->fcn == 0 || getFunctionId(q) == 0 || q->blk == NULL)
		return FALSE;
	p= getInstrPtr(q->blk,0);
	if( p->retc== 0) 
		return TRUE;
	return isPropertyDefined( getVar(q->blk,getArg(p,0))->props, unsafeRef);
	/* check also arguments for 'unsafe' property */
}

@-
Instructions are unsafe is one of the arguments is also mentioned
in the result list. Alternatively, the 'unsafe' property is set
for the function call itself.
@c
int
isUnsafeInstruction(InstrPtr q)
{
	int j, k;

	for (j = 0; j < q->retc; j++)
		for (k = q->retc; k < q->argc; k++)
			if (q->argv[k] == q->argv[j])
				return TRUE;
	return FALSE;
}

@-
The routine isInvariant determines if the variable V is not
changed in the instruction sequence identified by the range [pcf,pcl].
@c
int
isInvariant(MalBlkPtr mb, int pcf, int pcl, int varid)
{
	(void) mb;
	(void) pcf;
	(void) pcl;
	(void) varid;		/*fool compiler */
	return TRUE;
}

@}
@-
Any instruction may block identification of a common
subexpression. It suffices to stumble upon an unsafe function 
whose parameter lists has a non-empty intersection with the
targeted instruction.
To illustrate, consider the sequence
@example
L1 := f(A,B,C);
...
G1 := g(D,E,F);
...
l2:= f(A,B,C);
...
L2:= h()
@end example

The instruction G1:=g(D,E,F) is blocking if G1 is an alias 
for @verb{ { }A,B,C@verb{ } }.
Alternatively, function g() may be unsafe and @verb{ { }D,E,F@verb{ } }
has a non-empty intersection with @verb{ { }A,B,C@verb{ } }. 
An alias can only be used later on for readonly (and not be used for a function with sideeffects)
@{
@c
int
safetyBarrier(InstrPtr p, InstrPtr q)
{
	int i,j;
	if( isDependent(q,p)) 
		return TRUE;
	if (isUnsafeFunction(q)) {
		for (i = p->retc; i < p->argc; i++)
			for (j = q->retc; j < q->argc; j++)
				if (p->argv[i] == q->argv[j]) {
#ifdef DEBUG_OPT_OPTIMIZER
					stream_printf(GDKout, "Found overlapping assignment barrier for \n");
					printInstruction(GDKout, mb, q, LIST_MAL_ALL);
#endif
					/* TODO check safety property of the argument */
					return TRUE;
				}
	}
	return FALSE;
}
@-
Variables can be changed later in the program and, thus, may
not be simply replaced by an alias.
Variables could also be changed by functions with side effects.
@c
int
isUpdated(MalBlkPtr mb, int pc)
{
	InstrPtr p, q;
	int j, k;

	p = getInstrPtr(mb, pc);
	for (pc++; pc < mb->stop; pc++) {
		q = getInstrPtr(mb, pc);
		/* target is later assigned a new value */
		for (j = 0; j < p->retc; j++)
			for (k = 0; k < q->retc; k++)
				if (p->argv[j] == q->argv[k]) {
					int c = 0;

					if (p->argc != q->argc)
						return TRUE;

					/* instruction q may not be a common expression */
					/* TO WEAK, test stability of its arguments */
					for (j = 0; j < p->argc; j++)
						if (p->argv[j] == q->argv[k] && isInvariant(mb, 0, pc, q->argv[k]))
							c++;
					return c != p->argc;
				}

		/* result is used in an unsafe function */
		for (j = 0; j < p->retc; j++)
			for (k = q->retc; k < q->argc; k++)
				if (p->argv[j] == q->argv[k] ){
@-
If the operation involves an update of the operand it should told.
@c
				if (getFunctionId(q) == insertRef ||
					getFunctionId(q) == appendRef ||
					getFunctionId(q) == deleteRef)
					return TRUE;
				if (getFunctionId(q) && idcmp("destroy", getFunctionId(q)) == 0)
					return TRUE;
			}
	}
	return FALSE;
}

@-
In many cases we should be assured that a variable is not used in
the instruction range identified. For, we may exchange some instructions that
might change its content.
@c
int
isTouched(MalBlkPtr mb, int varid, int p1, int p2)
{
	int i, k;

	for (i = p1; i < p2; i++) {
		InstrPtr p = getInstrPtr(mb, i);

		for (k = 0; k < p->argc; k++)
			if (p->argv[k] == varid)
				return TRUE;
	}
	return FALSE;
}

@}
@-
@node Flow Analysis, Optimizer Toolkit, Lifespan Analysis, The MAL Optimizer
@subsection Flow analysis
In many optimization rules, the data flow dependency between statements is
of crucial importance. The MAL language encodes a multi-source, multi-sink
dataflow network. Optimizers typically extract part of the workflow and use
the language properties to enumerate semantic equivalent solutions, which
under a given cost model turns out to result in better performance.

The flow graph plays a crucial role in many optimization steps.
It is unclear as yet what primitives and what storage structure is
most adequate. For the time being we introduce the operations needed and
evaluate them directly against the program

For each variable we should determine its scope of stability.
End-points in the flow graph are illustrative as dead-code,
that do not produce persistent data. It can be removed when
you know there are no side-effect.

Side-effect free evaluation is a property that should be known upfront.
For the time being, we assume it for all operations known to the system.
The property `unsafe` is reserved to identify cases where this does not hold.
Typically, a bun-insert operation is unsafe, as it changes one of the parameters.
@{
@
Summarization of the data flow dependencies can be modelled as a dependency graph.
It can be made explicit or kept implicit using the operators needed.
We start with the latter. The primary steps to deal with is dead code removal.
@- Basic Algebraic Blocks
Many code snippets produced by e.g. the SQL compiler is just 
a linear representation of an algebra tree/graph. Its detection
makes a number of optimization decisions more easy, because
the operations are known to be side-effect free within the tree/graph.
This can be used to re-order the plan without concern on impact of the outcome.
It suffice to respect the flow graph.
[unclear as what we need]
@}
@-
@node Optimizer Toolkit, Access Mode, Flow Analysis , The MAL Optimizer
@+ Optimizer Toolkit
In this section we introduce the collection of MAL optimizers 
included in the code base. The tool kit is incrementally built, triggered
by experimentation and curiousity. Several optimizers require
further development to cope with the many features making up the MonetDB system.
Such limitations on the implementation are indicated where appropriate.

Experience shows that construction and debugging of a front-end specific optimizer
is simplified when you retain information on the origin of the MAL code 
produced as long as possible. For example,
the snippet @code{ sql.insert(col, 12@@0, "hello")} can be the target
of simple SQL rewrites using the module name as the discriminator.
@menu
* Access Mode::
* Accumulators::
* Alias Removal::
* Code Factorization::
* Coercions::
* Common Terms::
* Constant Expressions::
* Cost Models::
* Dead Code Removal::
* Empty Set Removal::
* Garbage Collector::
* Generators::
* Heuristic Rules::
* Inline Functions::
* Join Paths::
* Macro Processing::
* Merge Tables ::
* Multiplex Compiler::
* Partitioned Tables::
* Peephole Optimization::
* Query Plans::
* Range Propagation::
* Remote Queries::
* Singleton Sets ::
* Stack Reduction::
* Strength Reduction::
@end menu
@{
@-
The dead code remover should not be used for testing, 
because it will trim most programs to an empty list.
The side effect tests should become part of the signature
definitions.
@c
int
hasSideEffects(InstrPtr p, int strict)
{
	if (blockStart(p) || blockExit(p) || blockCntrl(p))
		return TRUE;
	if( getFunctionId(p) == NULL) return FALSE;

	if (getFunctionId(p) == depositRef ||
		getFunctionId(p) == insertRef ||
		getFunctionId(p) == inplaceRef ||
		getFunctionId(p) == appendRef ||
		getFunctionId(p) == replaceRef ||
		getFunctionId(p) == deleteRef)
		return TRUE;

	if( getModuleId(p) == ioRef ||
		getModuleId(p) == bstreamsRef ||
		getModuleId(p) == bstreamsRef ||
		getModuleId(p) == mdbRef ||
		getModuleId(p) == optimizerRef ||
		getModuleId(p) == lockRef ||
		getModuleId(p) == semaRef ||
		getModuleId(p) == alarmRef)
			return TRUE;

	if( getModuleId(p) == sqlRef){
		if( getFunctionId(p) == bindRef) return FALSE;
		if( getFunctionId(p) == bindidxRef) return FALSE;
		if( getFunctionId(p) == binddbatRef) return FALSE;
		if( getFunctionId(p) == resultSetRef) return FALSE;
		return TRUE;
	}
	if( getModuleId(p) == languageRef){
		if( getFunctionId(p) == assertRef) return TRUE;
		return FALSE;
	}
	if (getModuleId(p) == constraintsRef)
		return TRUE;
	if( getModuleId(p) == mserverRef){
		if( getFunctionId(p) == rpcRef)
			return TRUE;
		if( getFunctionId(p) == reconnectRef)
			return TRUE;
		if( getFunctionId(p) == disconnectRef)
			return TRUE;
	}
	if (strict && getFunctionId(p)==newRef)
		return TRUE;
	return FALSE;
}
void
replaceAlias(MalBlkPtr mb, int pc, int pcl, int src, int alias)
{
	InstrPtr p;
	VarPtr v;
	int k;

	v = getVar(mb, alias);
	for (; pc < pcl; pc++) {
		p = getInstrPtr(mb, pc);
		for (k = p->retc; k < p->argc; k++)
			if (p->argv[k] == src) {
				p->argv[k] = alias;
				if (pc > v->endLifespan)
					v->endLifespan = pc;
			}
	}
}

@}