• 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.compilers

    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
  • From tfb@tfb@work.it.out to comp.compilers on Fri Oct 16 17:52:48 2026
    From Newsgroup: comp.compilers

    <anton@mips.complang.tuwien.ac.at> wrote:

    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).


    I've spent an awful lot of time incrementally modifying programs in
    response to optimization notes from CL compilers: 'you didn't tell me
    enough about this so I[*] couldn't infer a useful thing'; 'OK, here is some more information', or 'OK, let me adjust how I expressed that'.

    [*] Tragically, I probably now have to say that yes, I understand there is
    no 'I' talking there.

    --
    tfeb.org/computer/
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Stefan Monnier@monnier@iro.umontreal.ca to comp.compilers on Fri Oct 16 18:52:08 2026
    From Newsgroup: comp.compilers

    anton@mips.complang.tuwien.ac.at [2026-10-16 10:41:59] wrote:
    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.

    I often think about what it is that I want from my compilers.

    For 99% of my code, the compiler does a good enough job, but for the
    remaining case, I often would like to be able to state some specific
    property which I'd like to get, but often it's hard to state it clearly
    in terms of the source code in a way that will still make sense further
    down the compilation stages.


    === Stefan
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Stefan Monnier@monnier@iro.umontreal.ca to comp.compilers on Fri Oct 16 18:47:00 2026
    From Newsgroup: comp.compilers

    anton@mips.complang.tuwien.ac.at [2026-10-16 10:41:59] wrote:
    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).

    Thanks, I didn't know about that project.

    A modern take on a similar idea might be

    https://rise-lang.org/

    They claim to be able to generate very efficient parallel numerical code
    from a high-level source in a pure functional language.


    === Stefan
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Martin Ward@martin@gkc.org.uk to comp.compilers on Sat Oct 17 13:18:11 2026
    From Newsgroup: comp.compilers

    On 16/10/2026 11:41, anton@mips.complang.tuwien.ac.at wrote:
    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

    There is the FermaT program transformation system, with its front-end
    the FermaT Maintenance Environment:

    http://www.gkc.org.uk/fermat.html

    Admittedly, this has not entirely taken the world by storm :-)
    but FermaT is currently being used commercial by Rocket Software
    in the migration of IBM assembler systems to Rocket COBOL,
    C and Java:

    https://www.rocketsoftware.com/en-us/products/assembler-code-refactoring

    At Rocket, and the previous company Software Migrations Ltd,
    millions of lines of assembler code have been sucessfully migrated.

    "Pigs from Sausages? Reengineering from Assembler to C via
    FermaT Transformations", M.Ward, Science of Computer Programming,
    Special Issue on Program Transformation,
    Vol 52/1-3, pp 213-255, 2004. ISSN 0167-6423 doi:dx.doi.org/10.1016/j.scico.2004.03.007

    http://www.gkc.org.uk/martin/papers/migration-t.pdf

    The system can be used to derive a program from a formal specification
    by applying a sequence of semantics-preserving transformations:

    "Provably Correct Derivation of Algorithms Using FermaT"
    Martin Ward and Hussein Zedan
    Formal Aspects of Computing, September 2014.
    Volume 26, Issue 5, Pages 993--1031, 2014-09-01, ISSN: 0934-5043 doi:dx.doi.org/10.1007/s00165-013-0287-2

    http://www.gkc.org.uk/martin/papers/trans-prog-published-ward2014.pdf

    The test cases in the above paper were Knuth's polynomial addition
    problem from "Fundamental Algorithms", where the derived solution
    was 2.1 times faster than Knuth's, and the polynomial multiplication
    problem, where the derived source code worked perfectly the first time
    it was executed.

    --
    Mary

    Dr Mary Ward | Email: martin@gkc.org.uk | http://www.gkc.org.uk
    G.K.Chesterton site: http://www.gkc.org.uk/gkc | Erdos number: 4
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Derek M Jones@derek@knosof.co.uk to comp.compilers on Sat Oct 17 20:42:08 2026
    From Newsgroup: comp.compilers

    Stefan,

    For 99% of my code, the compiler does a good enough job, but for the remaining case, I often would like to be able to state some specific
    property which I'd like to get, but often it's hard to state it clearly
    in terms of the source code in a way that will still make sense further
    down the compilation stages.

    I think that programming language could become a build time option https://shape-of-code.com/2026/10/11/programming-language-choice-is-becoming-a-build-option/

    Why not specify language constructs specific to your case
    and modify the compiler to map these to the appropriate
    optimised form?

    Ok, at the moment, even with coding agents, this still requires
    a decent chunk of work.

    This time next year, it might on the way to being the norm.

    --
    Derek M. Jones Evidence-based software engineering blog:https://shape-of-code.com
    [This reminds me of the extensible languages like EL/1 and IMP72 that were popular in the 1970s. They ended up being unusable because every program
    was in a different language. -John]
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Derek M Jones@derek@knosof.co.uk to comp.compilers on Tue Oct 20 13:06:07 2026
    From Newsgroup: comp.compilers

    John,

    [This reminds me of the extensible languages like EL/1 and IMP72 that were popular in the 1970s. They ended up being unusable because every program
    was in a different language. -John]

    This is not necessarily a problem when a coding agent is available.

    Using a language that others know reduces the cost of on boarding a
    new developer, and a coding agent. But the coding agent cost may be
    trivial compared to the performance savings from using the DSL.

    --
    Derek M. Jones Evidence-based software engineering blog:https://shape-of-code.com
    [You have a lot more faith in coding agents than I do. -John]
    --- Synchronet 3.22a-Linux NewsLink 1.2