Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!jarthur!uunet!mcsun!ukc!dcl-cs!aber-cs!athene!pcg From: pcg@cs.aber.ac.uk (Piercarlo Grandi) Newsgroups: comp.lang.misc Subject: Re: Aggressive optimization Message-ID: Date: 2 Nov 90 22:58:17 GMT References: <1990Oct30.105241.9733@tkou02.enet.dec.com> <1849@exodus.Eng.Sun.COM> <1990Nov2.001315.28208@Think.COM> Sender: pcg@aber-cs.UUCP Organization: Coleg Prifysgol Cymru Lines: 315 In-reply-to: barmar@think.com's message of 2 Nov 90 00:13:15 GMT On 2 Nov 90 00:13:15 GMT, barmar@think.com (Barry Margolin) said: barmar> In article 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