Super Compiler

A SuperCompiler is a dynamic optimiser that can transform the code of an object according to its actual usage. The word was introduced by ValentinTurchin, who built one using his RefalLanguage.

This may be simple static optimisations, removing state that isn't used from an object; or it may be very complex e.g. partial evaluation of functions leading to code transformation.

An introduction can be found here: http://www.refal.org/doc/turchin/dag/dag.html An implementation and documentation here: http://www.refal.org/english/s_compil.htm

A related technique is object elaboration which involves generating many possible execution sequences and generating an optimal processing object to handle that sequence. This is a static version of super-compilation.

E.g. z = F(a,b,c,d,e,f,g).

Given a parameter a, we can often refactor z = G(b,c,d,e,f,g) where a is now internal to G. This is called LambdaDropping

If a is internal to G then an algebraic simplification may be available.

So:

z = F(x,y) = x*x + y*y.

Given x = k.

z = F(x,y) = x*x+y*y = G(y) = k*k + y*y.

If the parameters don't arrive simultaneously then this optimisation may improve performance by doing work early.

-- RichardHenderson.

A JavaLanguage implementation is in the make. See http://inet.keldysh.ru/dpt_16/ScpJ/index.htm

Some of the ideas implemented in SynthesisOs.

See also CurryingSchonfinkelling GamesCompiler? SuperCombinators