• Re: the death of optimization compiler

    From anton@anton@mips.complang.tuwien.ac.at to comp.compilers,comp.lang.lisp on Fri Oct 16 10:41:59 2026
    From Newsgroup: comp.lang.lisp

    Anton Antimo <anton@safunu.org> writes:
    In 1974, Donald Knuth had already remarked:

    --8<-------------------------------------------------------->8---
    For 15 years or so I have been trying to think of how to write a
    compiler that really produces top quality code. For example, most of
    the MIX programs in my books are considerably more efficient than any
    of todayN++N++N++s most visionary compiling schemes would be able to
    produce. [...] We [...] always [ran] up against the same problem: the
    compiler needs to be in a dialog with the programmer; it needs to know
    properties of the data, and whether certain cases can arise, etc.

    For some reason we all (especially me) had a mental block about
    optimization, namely that we always regarded it as a behind-the-
    scenes activity, [...] which the programmer isnN++N++N++t supposed to know.
    This veil was first lifted from my eyes in [...] 1973, when I ran
    across a remark by Hoare [...] that, ideally, a language should be
    designed so that an optimizing compiler can describe its optimizations
    in the source language. Of course! Why hadnN++N++N++t I ever thought of it?

    A program-manipulation system is obviously what weN++N++N++ve been leading up
    to, and I wonder why I never thought of it before. Of course, the
    idea isn't original with me; when I told Hoare, he said, ``Exactly!''
    and referred me to a recent work by Darlington and Burstall [...]
    which describes a system which removes some recursions from a
    LISP-like language (curiously, without introducing any [go-to]N++N++N++s)
    [...]. Since LISP programs are easily manipulated as LISP [...]
    objects, there has also been a rather extensive development of similar
    ideas in this domain, notably by Warren Teitelman [...]. The time is
    clearly ripe for program-manipulation systems, and a great deal of
    further work suggests itself.

    Source: ``Structured programming with go to statements,'' Donald
    E. Knuth, ACM Computing Surveys (CSUR) 6.4 (1974): 261--301.
    --8<-------------------------------------------------------->8---

    This reminds me the research project CIP (Computer-Aided,
    Intuition-Guided Programming): They designed a wide-spectrum language
    CIP-L (described in LNCS 183, published 1985) and a program
    transformation system CIP-S (described in LNCS 292, published 1987).
    The idea was that you write a specification in CIP-L, and then tell
    CIP-S to perform various transformation steps, that eventually result
    in an executable and efficient program.

    This idea looked interesting, amd I looked in the books, but did not
    find them inspiring apart from the basic idea. And apparently the
    idea has not taken the world by storm, not even in the research world (according to Springer there are 63 citations of LNCS 183 and 45 of
    LNCS 292).

    It seems that we prefer to write executable programs from the start,
    and either optimize them by applying transformations manually, or
    fully automatic (using an optimizing compiler), not
    semi-automatically. I guess one of the problems of the idea of
    semi-automatic transformations is that the transformations are no
    longer applicable after changes due to changes in requirements. So
    you either want to apply the changes to the transformed program (and
    when you transform it manually, and treat the transformed program as
    the new source, you can easily apply changes to the transformed
    program), or you want fully automatic transformation, even if you only
    get a best-effort result.

    It seems to me that telling the compiler what is mutable is a clear >illustration of how a compiler is in dialog with the programmer, just
    like declaring a variable's type, with the C ``register'' keyword as
    another example.

    It's actually a monolog. You might consider that error messages from
    a compiler turn it into a dialog, but that's not how programming in
    most languages works (including Lisp, while Rust may be the exception
    that proves the rule).

    But that should not distract from the idea that one should be able to
    express the optimized code in the source language. And in many
    respects C (not the standardized subset) gives us that. E.g., we can
    search for the index of the smallest element in an array by writing it
    in the common subset of Java and C:

    for (i=0, best=0; i<n; i++)
    if (a[i]<a[best])
    best=i;
    return best;

    or by using pointer arithmetics, which is not in Java.

    for (p=a, bestp=a, endp=a+n; p<endp; p++)
    if (*p < *bestp)
    bestp = p;
    return bestp-a;

    For the two versions gcc-10 -O3 produces the following code for RV64GC
    for the loop body of this code:

    Java-compliant pointer arithmetics
    #a0=best a3=a[i] #a1=endp a4=*p
    #a1=n a4=i #a2=bestp a5=p
    #a2=a[best] a5=a+i #a3=*bestp
    L4: ld a3,0(a5) L4: ld a4,0(a5)
    addi a5,a5,8
    bge a3,a2,L3 bge a4,a3,L3
    mv a0,a4 mv a2,a5
    mv a2,a3 mv a3,a4
    L3: addi a4,a4,1 L3: addi a5,a5,8
    bne a4,a1,L4 bltu a5,a1,L4

    The actual instruction that is optimized away by using pointer
    arithmetics is the second-to-last instruction of the Java-compliant
    version and it corresponds to the "i++". In the Java-compliant
    version, the compiler introduces an induction variable in register a5
    that has the same value as p has in the pointer arithmetics version.
    For many loops over arrays, the compiler can then optimize the index
    away with induction-variable elimination, but in this case it does
    not. So here we have a case where we can express an optimization in C
    source code that the compiler does not optimize by itself.

    "register" also used to be about that, too, but for a long time
    (certainly with gcc), I have considered every auto variable going into
    a register unless its address is taken or the compiler runs out of
    registers. But that's certainly the part of compilation where the
    source code has the least influence on the object code, but I don't
    see how this is avoidable given the differences between machines.
    Maybe by providing register priority numbers (lower-numbered variables
    are preferred in register allocation to higher-numbered ones) and
    register classes (caller-saved, callee-saved; others); e.g. in

    register("caller-saved"(92),"callee-saved"(328)) x;

    the variable x would be considered for allocation to a caller-saved
    register, and would not get it if all caller-saved registers are
    allocated to variables with a lower number; in that case, it would be
    allocated to a callee-saved register if there are any left when all
    <328 have been allocated. Or something like that.

    Another case where C does not allow to optimize the code at the
    source-code level is SIMD instructions. GCC and clang support the GNU
    C vector extensions <https://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html>, but these extensions are limited and don't allow programmers to express all
    operations supported by SIMD instruction sets nor all instructions
    generated (when you are lucky) by auto-vectorization. So I have
    written loops like

    for (j = ncities-SIMD_SIZE; (long)j >= (long)i; j -= SIMD_SIZE) {
    [...]
    for (k=0; k<SIMD_SIZE; k++)
    if (dist[k]<closedist[k]) {
    closedist[k]=dist[k];
    closeidx[k] = baseidx[k]+j;
    }

    ... in the hope that one of the compilers actually turns the inner
    loop into a few SIMD instructions. Some actually do, with certain
    flags, but I think that this is a very unsatisfactory way to tell the
    compiler how it should optimize.

    Concerning Lisp, my impression is that it is typically more removed
    from the machine than C, but I dimly remember reading about a Scheme implementation that uses a dialect/subset of Scheme that is closer to
    the machine.

    - anton
    --
    M. Anton Ertl
    anton@mips.complang.tuwien.ac.at
    http://www.complang.tuwien.ac.at/anton/
    --- Synchronet 3.22a-Linux NewsLink 1.2