Common subexpression elimination merely involves a scan through the program block to detect re-curring statements. The key problem to be addressed is to make sure that the parameters involved in the repeatative instruction are invariant.
The analysis of optimizer.commonTerms()
is rather crude. All
functions with possible side-effects on their arguments should have
been marked as 'unsafe'. Their use within a MAL block breaks the
dataflow graph for all objects involved (BATs, everything kept in
boxes).
The common subexpression optimizer locates backwards the identical instructions. It stops as soon as it has found an identical one. Before we can replace the expression with the variable(s) of the previous one, we should make sure that we haven't passed a non-empty barrier block.
b:= bat.new(:int,:int);
c:= bat.new(:int,:int);
d:= algebra.select(b,0,100);
e:= algebra.select(b,0,100);
k1:= 24;
k2:= 27;
l:= k1+k2;
l2:= k1+k2;
l3:= l2+k1;
optimizer.commonTerms();
is translated into the code block where the first two instructions are not common, because they have side effects.
b := bat.new(:int,:int);
c := bat.new(:int,:int);
d := algebra.select(b,0,100);
e := d;
l := calc.+(24,27);
l3 := calc.+(l,24);