Subject: Re: compiler

From: Paul Sokolovsky <[email-masked]>
Date: Wed, 28 Oct 1998 23:20:09 +0300

Hello Clisp-list,

      What about general look at compilation ?

      Analysis  needed  to  make  optimal  code  may be divided in two
categories:

1. Data flow analysis
2. Control flow analysis

      First  is one best dealed with "traditional" compilers like GCC,
this  is  why  usually people prefer to compile to C, just not to mind
about such trivialities.

      But  control  flow  analysis always was powerful side of Lispish
compilers  - let's remember classic 'Rabbit: Compiler for Scheme' by Guy
Steele. CLISP with its 500k compiler, surely, too employs sofisticated
CF   analysis. AT opposite, this a weak side of conventional compilers
- even last features like EGCS far from good at this.

      So,  idea  may  be  viewed  as  to  combine this analyses in one
powerful  optimizer  having  nothing  in  common  with previous toyish
approaches. Of course, this analyzer must work in closed, complete and
hence  decidable  (I  don't  use  this  words  in  mathematical sense)
environment,  i.e.  know all about all. To achive this, system must be
basised  on  small  set  of primitives with known properties and other
operations  must  be  built  on  them.  This  will  allow sofisticated
dataflow  analysis, e.g. type deduction. To achive optimal translation
of  complex  operations  into  sequences  of  primitives, sofisticated
controlflow analyses required.

      Last  words on what it should compile to. C is out of scope - it
just  can't  represent  advanced  control-flow  structure.  So,  some
specific  representation  required  - not so hi-level to allow machine
code generation just with primitive additional anylasys (e.g. register
allocation),  but  still  machine (even virtual) independent - no such
things  as  registers.  It  may  be  noted  that  things  as  register
allocation  aren't  primitive at all - this surely right, but it's not
the  most important thing in all process. And at all, current hardware
more  and  more fades boundary between register and memory access - if
something  needed  often, it will be on cache, so even code generation
with  only  one  accumulator may be not so bad. Of course, that's not so
good  for  RISCs  unable to access memory in all commands - but anyway
all  that  just  inherent  hardware idiosyncrasies, last thing to deal
with.

     All  this  is  surely  not  new.  Maybe,  it's  very  trivial and
automagically  understandable,  but what is sure that we don't have it
implemented  (maybe  in  lisp  machines  - sorry, never seen something
except my creepy pentuin box). But at least we can see approaches to:

Aforementioned "Rabbit: A Compiler for Scheme" by Guy L. Steele, Jr.
ftp://publications.ai.mit.edu/ai-publications/0-499/AITR-474.ps
Type deducing is used in Standard ML
http://www.cs.bell-labs.com/cm/cs/what/smlnj/index.html
Something  about  proper  design  of  virtual machine that then allows
generation of effective code
ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/pvm.ps.gz
Described  closed-world  approach  exactly what is being done by Jeffrey
Siskind in his Stalin (Scheme compiler)
ftp://ftp.nj.nec.com/pub/qobi/stalin-0.7-no-binaries.tar.Z

     So,  it's  hardly  to  develop  something  new. Instead, it may be
developed  _usable_  -  point,  where  all  previously  written  stuff
connects with CLISP.

Best regards,
 Paul                          mailto:[email-masked]

---

From: Raymond Toy <[email-masked]>
Date: Wed, 28 Oct 1998 17:16:21 -0500

>>>>> "Paul" == Paul Sokolovsky <[email-masked]> writes:

    Paul> Hello Clisp-list,
    Paul>       What about general look at compilation ?

    Paul>       Analysis  needed  to  make  optimal  code  may be divided in two
    Paul> categories:

    Paul> 1. Data flow analysis
    Paul> 2. Control flow analysis

    Paul>       First  is one best dealed with "traditional" compilers like GCC,
    Paul> this  is  why  usually people prefer to compile to C, just not to mind
    Paul> about such trivialities.

Would a C compiler working on lisp-compiled-to-C code be able to
really do the correct "optimum" data flow analysis of the original C?
(I have no idea.)

    Paul>       Last  words on what it should compile to. C is out of scope - it
    Paul> just  can't  represent  advanced  control-flow  structure.  So,  some

Do you mean C can't handle this?  If so, then you might want to look
at a discussion on comp.lang.lisp or comp.lang.scheme a while back.
Jeffrey Siskind presented some results from his Stalin scheme compiler
that compiles to C.  The resulting C code was much faster than the
equivalent C version of the test.  I believe the gain came from the
fact that Stalin could do the interprocedural data-flow to produce
good code.  The C compiler couldn't do this, even when all of the
procedures were in the same file.  

This seems to say that using C is fine, if your Lisp compiler is smart
enough.

Ray

---

From: David Gadbois <[email-masked]>
Date: Wed, 28 Oct 1998 16:37:31 -0600

Date: Wed, 28 Oct 1998 14:03:41 -0800 (PST)
   From: Raymond Toy <[email-masked]>

   This seems to say that using C is fine, if your Lisp compiler is
   smart enough.

By way of an aside, there has lately been a lot of grumbling lately
about using C as a back end.  The C-- language
(http://research.microsoft.com/Users/simonpj/c--.html) looks like a
promising alternative.

--David Gadbois

---

From: Paul Sokolovsky <[email-masked]>
Date: Fri, 30 Oct 1998 17:04:32 +0300

Hello Raymond,

> really do the correct "optimum" data flow analysis of the original C?

        I think no.

> procedures were in the same file.  

        Yes, right this I argue too. Indeed, closed-world approach in
Lisp-like language lets to perform really total analysis, what is never
possible (and shouldn't) in C, which compilers stick to notion of
'function'.

> This seems to say that using C is fine, if your Lisp compiler is smart

        But then, C is superfluous! It just used as kind of assembly
language, and not-so-adequate one, since it can't handle computable gotos
(not calls), which surely emerge from continuation-passing style
transformation, one  element of the control-flow optimization.

        For example, resulting code may be compiled to never use hardware
stack (why - really don't know, but consider architectures without hardware
stack, and, maybe using own stack will ease such things as its winding),
except for FFI. Such code just couldn't be represented in C.

        But anyway, we se that compiling Common Lisp to Scheme, followed by
compiling latter in whatever, is more feasible than compiling directly to
whatever.

Best regards,

---

From: Giuseppe Attardi <[email-masked]>
Date: Sat, 31 Oct 1998 11:47:56 +0100 (MET)

As Bruno mentioned in passing, the most significant gain in performance can be
achieved by exploiting variable declarations.
This is especially true for code with many numeric operations:
exploiting declarations lots of boxing/unboxing operations, memory allocation
and type checks at runtime can be avoided.
By performing more careful type analysis, ECL for instance gains 30%
performance over GCL.
As far as I remember, CLISP discards most type information, and adding
type analysis is definitely a major undertaking.

-- Beppe