Simple partial evaluation

[bearophile]

To compile code efficiently the compiler has to find/infer lot of semantics from the code, and then needs ways to use such information.

>From what I've seen using such information (for example to split or merge loops, to tile loop iterations on arrays, to inline virtual functions, to inline delegates, to unroll recursive templates, and so on) is not the harder thing. Quite harder is finding such semantics in the first place.

The compiler can infer some of such semantics studying for example the structure of two nested loops, the inheritance tree, the virtual call points, performing run-time profiling of the code in many different ways, iterating on the variables and constants to perform type inference, finding where delegates/lambdas come from to inline them, and so on. This can be sometimes done, but requires a complex compiler, and the compiler risks getting slow too (caching on disk some of such semantics may help a lot, but not the first time some code is compiled).

To reduce the compiler complexity, to increase safety a little, and speed up compilation, languages offer ways to tag and annotate types and other things, so attributes/keywords like const, immutable, pure, inline, restrict, etc. etc. are added.

For the programmer adding such annotations requires time and brain, so their number is better kept low. A significant percentage of lines of code of most programs isn't speed-critical, so adding many annotations everywhere may look like a waste of time (and looking for speed in such code can produce longer code, unsafe code, and less readable code, all in situations where speed is not important).

So a possible solution to this looks like having optional annotations, this is done for example in CLisp. One problem of this is that some annotations may work only if used consistently everywhere. Another problem for the programmer is how to find where to put such annotations. CLisp solves this problem printing to the user where it's not able to optimize things away (it prints such things only relative to functions the programmer has annotated as "fast", to avoid flooding the programmer with too many warnings).

Time ago I have asked if D may run functions at compile-time, when possible, even if their result isn't assigned to a constant. Related to this there is the more general idea of partial compilation. In D a limited form of partial compilation can be done manually using templated functions: some arguments can be template arguments, so a good compiler in theory can specialize the code for them. But using such templated functions as normal functions (where all arguments are known at run time) is not easy/possible, this may force to duplicate code (using a (string) mixins to avoid code duplication is sometimes possible, but the result may not look good). 

Few old nice papers about partial evaluation:
"Partial Evaluation Applied to Ray Tracing" (1995) by Peter Holst Andersen:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.5469
"C-Mix: Making Easily Maintainable C-Programs run FAST":
http://www.diku.dk/~panic/articles/STTT98-cmix.ps.gz

Implementing a general automatic partial compilation in D may look like too much work, but there can be ways to add optional annotations to functions to allow a partial compilation locally that for this purpose works better than D templated functions, gain speed, keep the both the compiler simple enough, keep most of the source code short, and avoid excessive bloat in the compiled binary.

C-Mix uses the "residual" directive to tell the partial specializator that a variable has to kept as variable and not specialized (often to avoid code bloat).

In several things D prefers to give the programmer tools to do things, instead of letting the compiler do all by itself (but inlining is left to the compiler in DMD. LDC has two pragmas that give back to the programmer the possibility to inline asm functions and force inlining).

So D may offer an annotation that does the opposite of residual, that tells the compiler a certain variable can be specialized. A subset of this feature is to allow the programmer to know when a certain argument given to a function is known at compile time.

So something like this can allow the compiler to produce two compiled versions of this function, one where x is a compile-time constant and one where it's not. With this the compiler doesn't need to be smart, and the programmer can control the amount of code bloat produced.

void foo(int x, int y) {
    static if (__traits(isCTconstant, x)) {
        ...
    } else {
        ...
}

This is just an half-backed idea, but I think it may be improved.

Bye,
bearophile