🚀 go-pugleaf

On 2 Nov 90 00:13:15 GMT, barmar@think.com (Barry Margolin) said:

barmar> In article <PCG.90Nov1171210@odin.cs.aber.ac.uk>
barmar> pcg@cs.aber.ac.uk (Piercarlo Grandi) writes:

pcg> A program in some language, at any level of abstraction, defines an
pcg> higher level virtual machine than that offered by the language. The
pcg> primitives of the virtual machine defined by a program (most obviously,
pcg> but only, its procedures and macros) are actually composed out of the
     ^^^^^^^^
barmar> Should this have been "but not only"?

Yes, a Freudian slip (was thinking of Lisp...).

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

barmar> So aggressive optimization refers to optimization that does
barmar> things like interprocedural flow analysis?  Are loop unrolling,
barmar> strength reduction, and common subexpression elimination
barmar> aggressive or not?

They are all aggressive. Even substituting a shift for a multiplication
or division by a power of two may be considered aggressive in certain
languages where the properties of the two are not precisely identical.

barmar> Code generators, and certainly unagressive optimizers, are
barmar> almost always required to "recognize combinations of primitive
barmar> operators".

Ah yes, but not to rewrite them. And the recognition is typically simple
and well defined. It does not usually imply trying to understand the
effect of what is recognized. Languages where code generation itself (or
even parsing) is strongly context dependent make for dangerous
compilers (not to mention for hard to understand programs).

barmar> The only optimizers that are independent of the primitive
barmar> operators are peephole optimizers.

Yep, yep. Long live peephole optimizers!

barmar> To some extent a compiler is simply an optimizer for an
barmar> interpreter.  The dividing lines between code generation,
barmar> ordinary optimization, and aggressive optimization are very
barmar> fuzzy.

They are nearly the same thing, just like iteration can be said is a
special case of recursion.  But, as in this example, their conceptual
difficulty level is far different.  Code generation deals with
equivalences between a virtual and a real machine, ordinary optimization
with machine dependent transformations (already hazardous enough,
because the rewriting algebras of many real machines are underspecified
and contrived enough) and aggressive optimizations with rewriting
programmer's code.

barmar> Where does this "rewriting algebra" come from, and what makes it
barmar> poorly defined?  I don't think the ANSI C standard includes a
barmar> rewriting algebra; I presume it's a function of the language's
barmar> semantics.  So, the rewriting algebra could conceivably be as
barmar> well defined as the language itself.

Precisely. But usually this is not true, unless special care has been
taken. Often one has a fairly workable algebra that defines what is the
effect of a program, and a far less well defined one (usually implicit
in the former, as you say) that allows you to "prove" that transformations
preserve semantics. Theses are written about such things.

barmar> A poorly defined rewriting algebra could be the result of a
barmar> poorly defined language, or because the designer of the
barmar> rewriting algebra did a poor job.

Or maybe because the language was not designed with that goal in mind.
Some languages have been designed so that it is relatively easy to
reason about semantics preserving transformations; but even for these I
still think that tranformations ought to be in the open, as source
rewriting, than hidden in the code generator. But languages that people
want to aggressively optimize have not been designed with that goal in
mind, maybe because they were designed forty or twenty years ago as
autocoders or super assemblers.

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

barmar> Many of the things we do with computers were once thought to be
barmar> too complex to program, but that doesn't mean we shouldn't have
barmar> tried to implement them.

Indeed, but such difficult things, especially for languages that have
not been designed for them, should not be put into the reliability
bottleneck of an entire system. That's why I think that algorithmic
transformation should be done in an independent module, and on the
source code. It's a plain question of responsibility. The programmer
takes responsibility for what is fed to the compiler. This ought to be
clear. It is the programmer's task, IMNHO, to ensure that the source is
OK and efficiently written -- the compiler's responsibility should be to
ensure that it is faithfully translated. If risky technology hs to be
used, it should be used by the programmer, and it should be evident in
the source.

I am sick of having to disassemble compiler output to see where the
optimizer has botched it. I'd rather like that the effort put in the
pursuit of code generator level aggressive optimizers were put into
source code level rewrite assistants, and in making compilers more
stable, efficient, and reliable at doing translation, not rewriting.

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

barmar> Also, many programs are targeted for multiple (or unspecified)
barmar> physical machines and/or compilers, so the programmer may not be
barmar> able to choose language primitives that are good for all the
barmar> target environments.

This is damn good reason to use higher level languages, and let the
compiler translate their primitives into locally efficient versions. It
is not good reason for the compiler to rewrite pieces of program.

pcg> Are there alternatives?

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

barmar> Are you saying that this should be done in a module that is
barmar> independent of the target machine and compiler?

Certainly of the compiler. Possibly of the machine. Such a module may be
either a source level rewrite assistant, or a librarian, or both.
Consider the Amsterdam Compiler Kit; they define a tolerably well
specified machine independent intermediate code, and then work on that.
I don't like that a lot, but it is a defensible approach. I still think
it is too hazardous, because the intermediate code generated by the
compiler may well be equivalent to the source, but maybe not
transformations of it. Demonstrating that the intermediate code output
of the compiler is equivalent to the source under all possible
transformations of it is not that simple.

barmar> I was under the impression that most complex optimization was
barmar> already beind done using source-source translation,

Not really. What happens is that the program is translated into some
very low level representation, this is analyzed and rewritten, and the
rewritten form is translated to machine code. Most of the time this very
low level representation is not terribly well defined.

barmar> For instance, strength reduction and common subexpression
barmar> elimination translate the source into source with an additional
barmar> temporary variable.

Well, no. You do not see the source. If you did, this would be a
rewriting assistant.

barmar> Also, I don't think it matters what the destination of the
barmar> rewrite is.

Ah, as long as things work. But making things work is the problem -- it
is easy to say that aggressive optimization is either semantics
preserving and OK, or it is broken, as Jim Giles says. The problem is to
show that it is, not to assume that it can be made so. The engineering
problem is to demonstrate that it does not add to the unreliability of a
compiler, contrarily to appearances, and that hiding it in the code
generator does not lower the confidence level in the correctness of
compiled programs.

I don't think I ever claimed that aggressive optimization should be
avoided even if it is bug and cost free. The problem is whether it can
be made so, and at what price, and if a more conservative and
step-by-step approach should be used.

barmar> I think the hard part is recognizing large combinations of
barmar> primitives and reasoning about them.

barmar> Transformation bugs usually result from unexpected interations
barmar> between seemingly unrelated portions of the code (e.g. due to
barmar> use of global variables or aliasing).

In other words they result from underspecified or poorly designed
language algebra. On the order hand some languages have been designed
for easing semantic tranformations:

barmar> This is one reason why much of the program transformation
barmar> research has been done with functional languages: the absence of
barmar> side effects makes semantic analysis much easier.

Precisely. But this to me is somewhat extreme. I wish there were a
better way. I have my own ideas on the subject, but let's keep them out
of the way for now.

pcg> Yes, using a language whose primitives are at the abstraction level
pcg> desired, i.e. the primitives offered by the language are those
pcg> needed for the application.

barmar> Unfortunately, the computer industry doesn't abound with
barmar> application-specific languages.  And even if there were, finding
barmar> programmers proficient in many of them would be hard.

Ah. Here we get outside the scope of this newgroup: we should be
discussing here what *ought* to be done. This is not
biz.compiler.marketing or soc.programming.education. I have repeatedly
conceded that the "dusty deck" or "dusty programmer" or "dusty language"
problem means that the quick fix solution may be indeed the tricky job
of doing aggressive optimization. I still think however that even in
thios common but pathological case source level rewriting, which is a
very interesting growth industry in the commercial sector (and this is a
remark that should appear in biz.compsci.opportunities), would be
better.

pcg> Are the alternatives cost effective?

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

Sorry, I meant to write "manual rewriting".

barmar> How does the automatic rewriter know which parts are time
barmar> critical?  In many cases, program optimization is an incremental
barmar> process: you find the bottleneck, rewrite it efficiently, find
barmar> the new bottleneck, rewrite it, etc., until the overall
barmar> efficiency meets the goals.

Precisely, precisely. That's why I meant "manual". Naturally "manual" in
this case may also mean "assisted by tools", but still under programmer
control. As to automatic rewriting, instead:

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

barmar> Ah, now I see that you're talking about *replacing* the source
barmar> file with this automatically rewritten source file.

Yes, yes.

barmar> I thought you were talking about source-level transformations
barmar> internal to the compiler (usually operating on the parse-tree,
barmar> not the actual source text).  Since the purpose of the
barmar> transformation is to produce code that will map better by a
barmar> specific compiler onto a particular hardware, I don't see the
barmar> portability benefit of saving the transformed code.

But I wrote about automatic rewriting to a higher level language, or the
same language with calls to library procedures instead of ad hoc
codes...  This solves the problem at the root. You eliminate the need
for aggressive optimization, and you get better maintainability and
portability.

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

barmar> This is true if you can find such a language and programmers who
barmar> know it.  If the application is not very common then you will
barmar> probably have to spend quite a bit to purchase or develop the
barmar> language implementation.  Subroutine libraries for general
barmar> purpose languages can often do nearly as well and are much
barmar> easier to come by.

Indeed. That is why I say that the nice alternatives to aggressive
optimization are either a higher level language compiler or a librarian.

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

barmar> You made the statement that these optimizations don't buy much,
barmar> but didn't back it up with any evidence.

Bah. Hand waving hard here, the impression seems that on general purpose
architectures we get improvements in the 10-30% range. For special
purpose architectures running specific application classes the payoff
may be much higher, but here the issue of whether the language is well
matched to the application and the target machine becomes much much more
important.

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

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

barmar> Very little can be *proven* about any program; there are just
barmar> too many variables and dependencies.  A compiler writer who
barmar> makes such a statement is merely asserting that he's as
barmar> confident about his optimizations as he is about the rest of his
barmar> compiler.

Which must be supported by good evidence, because reasoning says that
adding complexity, especially about murky areas of language definitions,
and especially where AI like behaviour is expected, to a program
normally does lower it reliability. Anectodal evidence supports the
impression that aggressive optimization in the code generator is still a
black art rather than a science.

It is up to the proponents of aggressive optimization to demonstrate
that it does not add to the complexity or reliability of a program, and
that it is a better alternative than rewriting, manually or
automatically, the program in a higher level form more amenable to
straightforward code generation, and that the benefits so gained are
worth the effort.
--
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