🚀 go-pugleaf

On 30 Oct 90 21:22:38 GMT, chased@rbbb.Eng.Sun.COM (David Chase) said:

chased> diamond@tkou02.enet.dec.com (diamond@tkovoa) writes:

diamond> C was invented in order to be that better assembler.  If you
diamond> want machine level, you're supposed to program in C.  That is
diamond> exactly the purpose for which C was created.  If you want an
diamond> HLL, use one; don't cripple C.

chased> This may be true for (one dialect of) pre-ANSI C, but the
chased> specification of ANSI C allows (if you don't say "volatile") a
chased> large number of entertaining optimizing transformations, despite
chased> assertions by you and other posters here that C is a "low level
chased> language" and "low level languages ought not be aggressively
chased> optimized".

Haha. Never said that low level *languages* should not be optimized. We
are saying that *programs* in low level languages (or indeed in any
language) should not be optimized.

I have decided to stick out my neck again and try to define better what
is aggressive optimization.

When you have a language it has a set of primitive operators (+,*,...)
and of primitive operator combinators (if, ;, procedures, ...). The
language definition prescribes the effect of the primitive operators and
an algebra for such effects defined by the combinators.

In a way or another this implies that each language implies a virtual
machine. The task of the code generator is to map the virtual machine
onto the real machine as well as it can, which means faithfully
(semantics) and efficiently (pragmatics).

Optimization is doing the mapping from the virtual machine defined by
the language to the real machine in a clever (i.e. optimal for the
target real machine) instead of a straightforward way.

A program in some language, at any level of abstraction, defines an
higher level virtual machine than that offered by the language. The
primitives of the virtual machine defined by a program (most obviously,
but only, its procedures and macros) are actually composed out of the
primitives and combinators of the language, and their meaning is defined
according to the algebra for these as given in the language definition.

Aggressive optimization is mapping from the virtual machine defined by
the program (not by the language!) to the real machine *in the code
generator*.

This is in way of principle possible, because the code generator can
indeed recognize combinations of primitive operators and rewrite them to
other combinations that supposedly map better onto the target real
machine, as long as the two are equivalent under the algebra of the
language definition, in that particular context.

The problems are:

Is this desirable?

    No, because the rewriting algebra of the language may be poorly
    defined, or poorly understood, and thus it may be difficult to rely
    on the ability of the code generator to rewrite combinations of
    language primitives in semantics preserving ways. This is
    particularly true for languages like C, where a clean algebra for
    rewriting was not a design goal. Ansi C have tried to do some poor
    fixup engineering on this. We are not amused.

    No, because even assuming that the underlying algebra is clean,
    rewriting combinations of primitives is a far more concpetually
    difficult task than mapping each of them to the real machine. In
    particular it requires careful analysis. Such analysis tends to
    result in more bugs in the compiler, and the compiler is the
    bottleneck of an entire system's reliability.

    No, because even if two combinations of primitives can actually be
    shown in the given context to be equivaltn according to the
    language's algebra, it ought to be assumed that the programmer
    intended to write the particular one he chose to write for some
    good reason.

    No, because the speed advantages are not that dramatic (or
    nonexistent), *if* the author is a clever programmer that knows
    which of the equivalent formaulations will be optimal on the given
    machine.

Are there alternatives?

    Yes, rewriting the combinations of primitives not in the code
    generator, but at the source code level, either manually or
    automatically.

    Yes, using a language whose primitives are at the abstraction level
    desired, i.e. the primitives offered by the language are those
    needed for the application. In this case the optimization is not
    aggressive, because the generator is only doing optimal
    implementation of hopefully well defined language primitives, not
    supposedly optimal rewriting of pieces of a user program.

Are the alternatives cost effective?

    Yes, because for *many* even if not all codes the time critical
    portion is small enough that careful automatic rewriting is
    feasible.

    Yes, because automatic rewriting can be to a higher level language,
    which can then be more easily and non aggressively optimized, and
    automatic rewriting gives long lasting benefits in portability and
    confidence in the program.

    Yes, because using a language whose primitives are at the level of
    the problem is known to reduce costs and improve quality via reuse
    of the language's implementation or libraries, where otherwise the
    implementation of thsoe primitives would have to be rewritten and
    re-aggressively optimized for every application.

    Yes, because it separates the compiler from the code rewriter,
    which are two modules with very different goals and very different
    reliability profiles.

chased> C *is* a low level language, but the optimizations are 100%
chased> legal, often tend to make the code go faster, and thus they are
chased> applied.

They are legal but dangerous and not cost effective, according to the
above discussion.



chased> The compiler-writer's claim is "I can prove that these
chased> optimizations conform to the standard";


STOP THE PRESSES! Compiler writer proves that he can do program
rewriting in a bug free way! Program synthethizers must be round the
corner! Major software companies stocks collapse!

chased> can you *prove* that they should not be done?  How will it sell
chased> more computers/compilers to NOT do the transformations?  (Lest
chased> you forget, dollars and cents is what it all comes to in the
chased> end.)

The argument is that it is not *cost effective* for *users* of compilers
to pay for program rewriting in the code generator. They may require a
little education to acknowledge this, just like smokers. In the mean
time the tobacco industry has every incentive to educate the customers
to the contrary...

--
Piercarlo "Peter" Grandi           | ARPA: pcg%uk.ac.aber.cs@nsfnet-relay.ac.uk
Dept of CS, UCW Aberystwyth        | UUCP: ...!mcsun!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk