----- Original Message -----
From: "Anton V. Belyaev" <anton.belyaev@...>
Sent: Monday, August 28, 2006 3:06 PM
> I've found a "suggested programming project" at
> > Add some loop optimizations (such as invariant lifting, common
> subexpression elimination, ...) to sbcl's compiler. (a few weeks to
> years; some knowledge of compiler technology helpful)
> Is this still actual?
> Could somebody advise where I could start?
> Who is the contact person on this task?
There's no specific contact person. Hacking SBCL is pretty much a DIY
project, and sometimes getting
help from busy developers is difficult. Specific questions are more likely
to get a response than general questions.
Anyway, for places to start, I would recommend learning about the IR1 stage
of the compiler. This is where
the code is converted into CPS (continuation passing style) graphs, and then
various operations are performed until
the graphs are turned into VOPS, which is the second stage. Operations such
as loop invariant lifting would
probably be done at the IR1 stage. For resources, there's the manual on
CMUCL (look on its web site)that describes
various stages of the compiler and the CPS format. Also, if you poke around
the code, I'll bet there's a
global variable you can set to make the compiler print out the code graph as
You might also want to look at how the IR1 systems does constant folding,
which is somewhat similar but probably much
simpler. For constant folding, you simply have to identify function calls
where the arguments are guaranteed constant at compile time, and
then replace that part of the graph with the results of the function call.
For loop invariant stuff, you would need to recognize you're in
a loop, identify functions that are side-effect free, and that don't use any
arguments or bindings that change with the loop repetition.
You would then rewrite the graph to do those function calls outside of the
loop and use a binding with the results of the function
call inside the loop. This way that function is called just once and not
every time through the loop. [This explanation is subject to severe
brain damage on my part].
Another area that might be helpful is to make some test cases to see if the
compiler does various types of
loop invariant lifting. For example if you disassemble:
(defun naughty-loop (x)
(let ((var 0))
(loop for i to x do
(setf var (+ x 300)) ;invariant
(print (* i var))))
you can try to determine whether VAR is calculated every time through the
loop. Obviously, it can be calculated once outside the loop
and thereby avoid redundant calculations.
Hope this helps,