From: Jeff Dalton
Subject: What do compilers optimize?
Date: 
Message-ID: <7398@skye.ed.ac.uk>
(Do any Lisp implementors read this newsgroup?)

Are there any implementations that do any of the following (or
something similar):

  * Turn a CASE in which the alternatives are integers into
    an indirect transfer?

  * Use hashing for a CASE with many alternatives?

  * Allow fixnums (or floats) to be passed between procedures without
    any heap allocations (maybe just for local procedures in the same
    top-level form)?

-- jd

From: Barry Margolin
Subject: Re: What do compilers optimize?
Date: 
Message-ID: <17tvm1INNqdc@early-bird.think.com>
In article <····@skye.ed.ac.uk> ····@aiai.ed.ac.uk (Jeff Dalton) writes:
>(Do any Lisp implementors read this newsgroup?)

KMP of Symbolics has been participating quite a bit lately.  I know some
Lucid people read it but don't post much.

>Are there any implementations that do any of the following (or
>something similar):
>
>  * Turn a CASE in which the alternatives are integers into
>    an indirect transfer?

Symbolics and Lucid do this.  My gripe with the Symbolics implementation is
that it won't do the optimization if the case values are a dense set not
near 0 -- it doesn't want to create a sparse jump table, and it doesn't try
to offset the value to the base of the set.

Surprisingly, CMUCL doesn't do this optimization at all.

An interesting enhancement to this optimization would be to recognize when
the case values are a sparse set of dense sets, e.g.

(case x
  ((0 1 2 3 4 5 6) ...)
  ((7 9 11) ...)
  ((30 31 32) ...)
  ((33 34 35) ...)
  ((95 97 99 101) ...))

and transform this into

(cond ((<= 0 x 11)
       (case x ((0 1 2 3 4 5 6) ...)
	       ((7 9 11) ...)))
      ((<= 30 35)
       (case x ((30 31 32) ...)
	       ((33 34 35) ...)))
      (t (case x ((95 97 99 101) ...))))

I could imagine the above style of code being in the implementation of a
byte code interpreter.  A processor emulator might be similar, although the
dense sets would likely be found clustered above power-of-two values,
allowing for further optimization; instead of the outer level being a COND,
it could be another CASE that indexes off the high-order bits of the
opcode, which is likely to be a dense set that can be turned into a jump
table.

>  * Use hashing for a CASE with many alternatives?

Neither Symbolics, Lucid, nor CMUCL appear to do this.

>  * Allow fixnums (or floats) to be passed between procedures without
>    any heap allocations (maybe just for local procedures in the same
>    top-level form)?

Most implementations implement fixnums as immediate values, so they are
never allocated on the heap.  Symbolics also implements single floats as
immediate types.  I don't expect any implementations for conventional
32-bit processors to do this, though, since single floats take 32 bits, and
that doesn't leave any room for tags.  I believe this was the original
intent of the small-float type, but apparently it's not useful enough (most
FP hardware only supports 32 and 64 bit floats, and the limited precision
of smaller floats probably makes them pretty useless).

-- 
Barry Margolin
System Manager, Thinking Machines Corp.

······@think.com          {uunet,harvard}!think!barmar
From: Jeff Dalton
Subject: Re: What do compilers optimize?
Date: 
Message-ID: <7409@skye.ed.ac.uk>
Thanks to all who have responded so far.

Another item:

  * Avoid recomputation of common "subexpressions" in a single procedure.
    (There must be many cases where a programmer would rather not write
    a LET and introduce a new variable.)

It's fairly common to do this for CAR-CDR sequences, but I was
surprised to find that certain implementations didn't do it for,
say, LENGTH of a SIMPLE-VECTOR or even for arithmetic expressions.

-- jd
From: Rob MacLachlan
Subject: Re: What do compilers optimize?
Date: 
Message-ID: <Btwr6D.3E0.1@cs.cmu.edu>
>>Are there any implementations that do any of the following (or
>>something similar):
>>
>>  * Turn a CASE in which the alternatives are integers into
>>    an indirect transfer?
>
>Surprisingly, CMUCL doesn't do this optimization at all.

Yeah, it's on our list.  The utility of this optimization is reduced
somewhat in Lisp due to the tendency to represent "enumerations" as
symbols, but if the programmer goes to the trouble of using integers
(as in the byte-interpreter example), then we really ought to generate
a jump-table.

>
>>  * Use hashing for a CASE with many alternatives?
>
>Neither Symbolics, Lucid, nor CMUCL appear to do this.

It's a possibility I never thought of, which could be used to handle
CASE'ing off of symbols.  One approach would be to figure out a
perfect hashing function at compile time (based on the symbol's equal
hash, stored in the symbol).  This hash could be used as an index into
a jump table, and each table entry would only need to do an EQ test to
verify that the symbol is correct, branching off to the OTHERWISE case
if there is a mismatch.

>
>>  * Allow fixnums (or floats) to be passed between procedures without
>>    any heap allocations (maybe just for local procedures in the same
>>    top-level form)?

As Barmar says, in all the modern implementations I know of, fixnums
are "immediate", and don't need to be heap-allocated.  [This
terminology is confusing, since it is unrelated to the concept of an
immediate operand to an instruction.]

Within a block compilation unit, CMU CL supports non-consing register
passing of ([un]signed-byte 32), single-float and double-float values
as function arguments and return values.  CMU has START-BLOCK and
END-BLOCK proclamations which can delimit a compilation block smaller
than a file; entire files or multiple files can also be block
compiled.  The size of a block compilation is limited only by the
amount of memory needed for compilation.

  Robert A. MacLachlan (···@cs.cmu.edu)