[self-interest] Re: self in self - plan B

[Jecel Assumpcao Jr.]

In a message with this subject on November 22, I mentioned some alternatives
for the code generation part of the Self compiler:

> We could:
> 
>   - write a program that would read a description of the CPU and
>     generate a code generator for it Self automatically. This would
>     be a kind of "mango for the back end".
> or
>   - write the back end in a very abstract style, suitable for any
>     CPU. Then we would create a child object for a specific CPU
>     and implement the abstract methods ('generateJump:') manually.
>     The inlining compiler would optimize most of the implied
>     indirections, so the final code would be similar to that of
>     the first option (I am talking about how fast the code
>     generator runs, not the quality of the code it generates)
> or
>   - write the back end to generate a very primitive and abstract
>     machine code. A patttern matcher in the final pass would
>     translate that into the actual machine language for each CPU

I commented that the first two options (gcc-style) would generate the fastest
code generator, but the third option would allow the best scheduling (which is
critical for high performance in modern processors). I would recomend that
anyone interested in scheduling look at the various papers by Steve Novack
(http://www.ics.uci.edu/~snovack/) and also this paper by Urs Hölzle and his
students: http://www.cs.ucsb.edu/oocsb/papers/dispatch.html

Just a little background: when David Ungar and Randy Smith first defined the
Self language, most people thought that it would be impossible to make it
perform as well as Smalltalk since they hadn't compromised the language model
to make it more efficient. Well, Craig Chambers and friends proved them wrong
by inventing sophisticated type inference systems. They got 50% of C speed on
highly numerical code (the kind that brings Smalltalk to its knees) which is
simply amazing when you consider that C is fast by ignoring numerical errors,
addressing errors and so on that are carefully handled in Self. The problem was
that the compiler was slow, which was bad since it was running in parallel with
your applications. So Urs Hölzle used two compilers in order to replace type
analysis (slow but precise) with type feedback (much faster and a little less
precise) to make the system both more responsive and simpler. It was also
better in highly object-oriented code, though not as good with numerical code.
Now both Craig and Urs were interested in their new ideas, and so didn't put as
much effort into the register allocation and code generation as commercial
compilers (or even gcc). This makes the 50% of C above even more impressive,
but has made Self have a performance penalty on more advanced processors.
This is how I remember it, but I welcome corrections.

In the other thread, John Ars wrote:
> Hmm, intriguing.  How would you go about that?? Could you write the VM
> in Self (a la Squeak)?

and José Baltasar García Perez-Schofield wrote:
>          I will be pleased to study your next mail, in order to know what
> means to implement self on self. I am very intrigued about it.

The Squeak model is very interesting. There is a normal Squeak program that
implements the whole Squeak Virtual Machine. So you can run Squeak inside of
Squeak (it works perfectly, though 600 times slower than normal). You can make
changes and generate the next version of Squeak this way. When it is working
the way you want it to, you can translate this Squeak program to C (it must be
written in a very restricted, non object oriented style for you to be able to
do this) and then compile this C program to get a new executable VM.

The problem with this is that it doesn't help your own Squeak programs (you
have to write parts of your application in the restricted style and then
generate C as new primitives to be integrated into the virtual machine, hardly
easy stuff to do!). Also, the write Smalltalk -> simulate -> translate to
C -> compile -> restart virtual machine development cycle is not very direct.

But what if we did what the Squeak people did but replaced the bytecode
interpreter in the virtual machine with a compiler (or two)? The virtual
machine could now be written in the normal Self style (no restrictions) and it
would include a part that would take bytecodes and generate (for example) X86
machine language code. If the current machine can't execute this X86 code
(which will be the case, since I am using a Sun Utra 5 as the development
plartform), the code can be sent over a network to a machine that can. Since I
explained this in the VM99 workshop position paper, I won't repeat how this is
done here. See http://www.squeak.org/oopsla99_vmworkshop/jecel.txt

Note that at some point, this Self program will be capable of generating X86
code for any Self program, including itself! It will be used by the whole
system, including all user applications (no more translating to primitives to
make things fast).

Ok, so back to plan B and how to make a good code generator for Self. My
current idea is to combine the three options that I described at the very
begining:

 - (option 2) the compiler will be written in a very abstract way, with more
specific compilers inheriting from it

 - (option 1) the more specific compilers will override data structures, not
methods, so a procesesor description will be declarational instead of functional

 - (option 3) the compiler will work with very simple instructions (just moves
between functional units) until the very end, and then translate these to the
actual machine language

Note that this will favor a move-based CPU (such as I designed for the Merlin
6) even though the first port will be for the X86. Since I am doing the work, I
guess I am entitled to show my biases :-)

The data structures that are used by the compilers are a description of each
CPU in terms of functional units and scheduling. While I have been speaking of
a X86 code generator, the descriptions for the 386, 486, Pentium, Pentium II and
so on could be very different (though the other data structure, the translation
table, would be mostly the same for all of them).

What is the problem with this? The way Self compilers are now, this particular
Self program won't be very efficient. But this program takes away processing
time from all the applications, so the system will not be very responsive if
the compiler is slow (the problem we had in Self 2.0).

So here is a simple idea to fix this: optimize immutable data structures. I'll
give an example in Smalltalk, since it has a syntax for declaring constant
vectors while Self does not. Look at this code:

     #('first text is' 'and the second one is' 'finally, this one is')
                      do: [ :s | s print. ' ' print. s size printString print]

Now imagine that the compiler was smart enough to notice that the receiver of
the #do: message is a constant collection and could pre-evaulate some things to
generate the same code as:

    'first text is' print. ' ' print. 13 print.
    'and the second one is' print. ' ' print. 21 print.
    'finally, this one is' print. ' ' print. 20 print

Yes - this is what is called "partial evaluation". No - this particular case is
not hard to implement or require a Lisp derived language.

If the Self compiler in Self can do this (and we have a richer selection of
constant collections than just immutableString!) and it is implemented as
described above, then it would generate efficient code generators when it
compiled itself.

So this is what I am working on. Though it will take longer than a simple port
of the Sun VM I think the result will be worth it (specially when porting to a
second processor). I don't know if anyone made it this far, but if so I would
love to have some comments or questions on this.

-- Jecel