Re: [Caml-list] compiler bug?

[Xavier Leroy <Xavier.Leroy@inria.fr>]

>   I would like to report what I think might be a bug in the Ocaml
> compiler.  But first I wanted to run this by this group in case there's
> something I'm missing.  I have some very simple code that consists of 2
> nested loops.  Inside the inner loop, is a simple statement.
> Furthermore, the inner loop is not "tight".  Ie. the number of
> iterations within the inner loop is very large and the number of
> iterations of the outer loop is very small.  I then manually time this.
> I then change the code by inserting a simple function call between the
> inner and outer loops.  This should have virtually no effect
> whatsoever.  However, when I time this, I get exactly twice the time.
> This is somewhat inexplicable.

As John Carr mentioned, the function call forces the variables that
are live across the call (i.e. dummy1) to be spilled, causing one additional
memory read and one additional write at each iteration of the inner
loop.  Since your inner loop is approximately 4 integer instructions,
the additional memory traffic can easily halve performance.

I grant you that spill code generation could be more clever here and
spill/reload around the whole inner loop.  But, no, it's not a bug:
Ocaml has a bug when the generated code crashes or produces incorrect
results.

> I learned in basic compiler theory that when a function is called, you
> save all the registers before entering the function.

That's an over-simplification.  First, many compilers designate a
number of registers as "callee-save", meaning that all functions must
preserve their values.  These would be preserved across a call.
It happens that ocamlopt does not implement callee-save registers, as
they make garbage collection (more exactly, stack traversal) and
exception handling more expensive.  But even when a function call
destroys all registers, as with ocamlopt, there are many possible
placements for spills (saving a register in the stack) and reloads (of
a register from the stack), and the placement you suggest (only around
calls) is rarely optimal.  Well, in your example it is :-)

Generation of spill code is a dark corner of compiler construction.
As with many other compilation problems, there are a bunch of
NP-completeness results.  Unlike many other compilation problems, I'm
not aware of any published heuristics that works well in most cases.
Well, there is the paper by George and Appel where they use an ILP
solver (integer linear programming) to produce optimal spills, but
that's kind of expensive...

- Xavier Leroy