• bearophile (26/26) Sep 11 2009 To compile code efficiently the compiler has to find/infer lot of semant...

bearophile <bearophileHUGS lycos.com> writes:

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