pardo@cs.washington.edu (David Keppel) (06/04/90)
Preston Briggs <preston@rice.edu> writes: >[Summary of A. Holub's ``Compiler Design in C''.] >[``It's better to provide maximum optimization even if dangerous.''] >[Outrageous!] I agree wholeheartedly. I've been taking a class this quarter and we've been studying optimizaing compilers for supercomputers, e.g., the vector machines, the SIMD machines, and the shared-memory multiprocessors. Today in class, I expressed the following opinion: ``You compile your program 100 times with optimization turned off and then 1 time with optimization turned on. It's no wonder that so many bugs show up in the optimizer, it hardly ever gets tested. Therefore, you should compile your programs with only the optimizations that you can ``debug through'' and leave it at that.'' An extreme position, I know, I was actually trying to be provocative rather than express my own opinion. Anyway, at this point one of my classmates -- who has worked on optimizing compilers for several high-performance computers -- tells me that I am free to feel that way, but that her customers won't buy my product. They'd rather spend time figuring out why their code gives wrong answers than spend time waiting for their computer to give the right answer. (Ok, so they run programs that take a week to execute...) It's not quite the same thing as ``provide optimizations even if dangerous'', but I'd just finished listening to a 10-minute report from a group that had spent most of their time trying to figure out why the compiler for a vectorizing multiprocessor kept producing incorrect code. Flame away... ;-D on ( Debugger they come, deharder they foul ) Pardo -- pardo@cs.washington.edu {rutgers,cornell,ucsd,ubc-cs,tektronix}!uw-beaver!june!pardo -- Send compilers articles to compilers@esegue.segue.boston.ma.us {spdcc | ima | lotus}!esegue. Meta-mail to compilers-request@esegue. Please send responses to the author of the message, not the poster.
larus@spool.cs.wisc.edu (06/05/90)
Just for the sake of argument, let me disagree with the prevailing sentiment
that compilers should only provide "safe" optimizations. Keppel has already
raised the argument that some programs are too slow to run without potentially
dangerous optimizations. This is an interesting argument that brings up the
real point: programming languages are not designed for parallel computation.
Compilers for machines with parallelism adhere to a standard that is too high:
sequential equivalence. Some programmers are willing to trade off the
semantics of the language (the effect of "bad" optimizations) for faster
programs. By arguing that compilers should only perform conservative
optimization, you are claiming that the sequential semantics of FORTRAN (fill
in your favorite or least favorite language) are suitable for parallel
execution. Think carefully before you argue this position.
/Jim
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus}!esegue. Meta-mail to compilers-request@esegue.
Please send responses to the author of the message, not the poster.MERRIMAN@ccavax.camb.com (George Merriman -- CCA/NY) (06/05/90)
In article <1990Jun4.044255.14857@esegue.segue.boston.ma.us>, pardo@cs.washington.edu (David Keppel) writes: > Anyway, at this point one of my > classmates -- who has worked on optimizing compilers for several > high-performance computers -- tells me that I am free to feel that way, > but that her customers won't buy my product. They'd rather spend time > figuring out why their code gives wrong answers than spend time waiting > for their computer to give the right answer. (Ok, so they run programs > that take a week to execute...) But can these people (and others who may inherit the code) always tell a wrong answer when they see one? George Merriman, Cambridge Computer Associates -- Send compilers articles to compilers@esegue.segue.boston.ma.us {spdcc | ima | lotus}!esegue. Meta-mail to compilers-request@esegue. Please send responses to the author of the message, not the poster.
mike@hpfcso.hp.com (Mike McNelly) (06/05/90)
Almost all compiler courses and texts I've seen in the past 10 years
have mainly devoted themselves to front end theory. My guesses about
why this is happening are:
1) The theory is neat, self contained, well understood and it
appeals to academia's sense of balance. It's also a subject
that can be covered adequately in one semester. The fact that
it has less practical use for graduates who work in compilers is
secondary. There's always a tendency to answer the easy
questions (that have neat answers) rather than the important
ones.
2) Lots of people take one course in compilers. Hence, lots of
books are written for the first course. Few take a second
course so the market for texts describing the back end is a lot
smaller. Reluctantly I'd have to agree that the first course in
compilers/language theory should discuss automata and some
parsing. People who write compilers, however, don't spend much
time doing this stuff anymore.
3) There's lots of optimization theory around. The trouble is,
theory alone just doesn't do much good. To measurably improve
code you have to know when to optimize and when not to and you
have to consider the intimacies of the particular architecture.
Academics hate to describe particular machines in texts because
a) the audience is too limited, and b) your text becomes dated
as soon as the machine becomes obsolete.
4) The incentive for the development of most early (and
fundamental) optimization theory was to improve FORTRAN.
Academics hate FORTRAN. They also write most of the texts.
5) Optimization theory only discusses the easy cases. When it's
time to discuss the really nasty issues of aliasing, etc.,
there's usually a lot of general statements and maybe even a
little hand waving.
These are only personal views. Treat them as religion only. It really
would be nice, though, if a few of the candidates I interview for jobs
in compiler technology had an adequate exposure to the back end of a
compiler however unclean it may be.
Mike McNelly
mike%hpfcla@hplabs.hp.com
[I agree, the textbooks tend to dwell on the easy parts. When I was teaching
compiler courses ten years ago, my inclination was to tell people to read
about the easy parts in the books because I'd only go over them quickly in
class, and I'd spend more class time on the stuff not well treated in the
texts. For some reason, this approach was not treated with a lot of
enthusiasm. -John]
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus}!esegue. Meta-mail to compilers-request@esegue.
Please send responses to the author of the message, not the poster.pardo@cs.washington.edu (David Keppel) (06/06/90)
larus@spool.cs.wisc.edu writes: >[Some programmers are willing to throw away some of > their sequential semantics in order to get processing power.] In which case you're no longer compiling the same language. The point that I would like to make is that such things are *language extensions* and not *compiler optimizations*. ;-D on ( Language retractions? ) Pardo -- pardo@cs.washington.edu {rutgers,cornell,ucsd,ubc-cs,tektronix}!uw-beaver!june!pardo -- Send compilers articles to compilers@esegue.segue.boston.ma.us {spdcc | ima | lotus}!esegue. Meta-mail to compilers-request@esegue. Please send responses to the author of the message, not the poster.
robinson@cs.dal.ca (John Robinson) (06/06/90)
In article <1990Jun4.212226.18389@esegue.segue.boston.ma.us> larus@spool.cs.wisc.edu writes: >... SOme programmers are willing to trade off the >semantics of the language (the effect of "bad" optimizations) for faster >programs. By arguing that compilers should only perform conservative >optimization, you are claiming that the sequential semantics of FORTRAN (fill >in your favorite or least favorite language) are suitable for parallel >execution. Think carefully before you argue this position. > Ok. I'll bite. But I'll rephrase it slightly. Compilers for languages that are designed for serial execution should only perform conservative optimizations for parallel platforms. The fact that the programmer may choose to bypass this is irrelevant. That is what programmers are for :). Consider what happens if we don't choose this course. Unsafe optimization => unsafe results. Definately not good. Far from being an argument for the suitablility of FORTRAN (or any other inherently sequential language) I see this as an argument against such suitablity. If we design languages with true parallelism in mind then what you are referring to as unsafe optimizations will disappear, along with the need for sequential equivalence. One can not have sequential equivalence in a language which can not be expressed sequentially. -- John Robinson, robinson@ac.dal.ca, robinson@cs.dal.ca, 902-492-1779 -- Send compilers articles to compilers@esegue.segue.boston.ma.us {spdcc | ima | lotus}!esegue. Meta-mail to compilers-request@esegue. Please send responses to the author of the message, not the poster.
stewart@sdsu.edu (Kris Stewart) (06/06/90)
I am planning to use Compiler Design in C in the fall semester.
Can members of the group point me to alternate texts or monographs that do a
good job on optimization?
Are there 'review' articles in the literature that might make a good addition
to class readings?
Are there a few recommended journal articles that could be appended to the
class reading list?
Since much optimization becomes machine specific, a detailed introductory
example for some specific machine might make a good lecture sequence - is
there any such documentation available that would be accessible reading for
upper division undergraduates?
Thank you
Kris Stewart
(stewart@cs.sdsu.edu)
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus}!esegue. Meta-mail to compilers-request@esegue.
Please send responses to the author of the message, not the poster.poser@csli.stanford.edu (Bill Poser) (06/06/90)
In article <1990Jun4.212226.18389@esegue.segue.boston.ma.us> larus@spool.cs.wisc.edu writes: >Some programmers are willing to trade off the semantics of the language (the >effect of "bad" optimizations) for faster programs. This misses the point. If you want to define a new version of a language for parallel execution and specify how the semantics differs from the sequential version of the language, fine. Then the programmer knows what he is getting into. The problem with dangerous optimization is that it changes the semantics behind the programmer's back. Such changes are known as "errors". Bill -- Send compilers articles to compilers@esegue.segue.boston.ma.us {spdcc | ima | lotus}!esegue. Meta-mail to compilers-request@esegue. Please send responses to the author of the message, not the poster.
larus@primost.cs.wisc.edu (James Larus) (06/07/90)
OK, now that everybody is interested in this argument, let me continue it.
Previously, I contended that "unsafe optimizations" are necessary for parallel
machines because without them, a programmer cannot express parallel
algorithms. A number of people jump on me and pointed out that what is really
needed is a new language that allows a programmer to express his or her
intent. I agree entirely, however a lot of programmers are stuck using
Fortran and C and will be using these languages for a long time.
Let's make this argument more concrete. Consider the example of summing the
elements of a vector:
for i <- 1 to n do
sum <- sum + A[i]
This operation takes O(n) time. However, on a parallel computer with
sufficient processors, it can take O(lg n) time by using a parallel prefix
algorithm that builds up a tree of additions. The problem is that this
optimization requires addition to be associative. Integer and floating point
addition isn't associative. However, how many programmers have carefully
analyzed their algorithm and convinced themselves that summing the elements
from 1 to N will produce the least error? When was the last time you did
that? Most programmers simply write the above loop as the most convenient
idiom for summing the vector. Although parallel prefix may produce a different
result, which is right and which is wrong?
Of course, some languages such as Fortran 90 permit a programmer to express
his intent in a manner that gives the compiler information about when order
matters. Unfortunately, such languages are rare and only include a few common
idioms.
/Jim
[I suppose there is merit to this suggestion, but the thought of an optimizer
that second guesses the programmer and attempts to generate code for what the
program would have said if the source language was different fills me with
considerable unease. -John]
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus}!esegue. Meta-mail to compilers-request@esegue.
Please send responses to the author of the message, not the poster.johnson@cs.uiuc.edu (Ralph Johnson) (06/08/90)
>Another reason for emphasizing front ends is probably the fact that these >techniques are useful for lots of things other than writing compilers, >whereas code generation and optimization is mainly of interest to compiler >writers. The most important part of code optimization is dataflow analysis, data and control dependencies, and so on. This is very important in many areas of program analysis. I think that main reason that compiler courses emphasize front ends is tradition. I don't think that is a good reason. Ralph Johnson -- Send compilers articles to compilers@esegue.segue.boston.ma.us {spdcc | ima | lotus}!esegue. Meta-mail to compilers-request@esegue. Please send responses to the author of the message, not the poster.
tli@%phakt.usc.edu (Tony Li) (06/08/90)
In article <1990Jun7.010349.2097@esegue.segue.boston.ma.us> larus@primost.cs.wisc.edu (James Larus) writes:
Although parallel prefix may produce a different result, which is
right and which is wrong?
That depends. If the semantics of the language specifies an order of
evaluation, then a "correct" compiler must implement that order of evaluation.
If your optimizer does something different then it is either a) broken, or b)
implementing a different semantics, which is a different language. If you
claim that your compiler correctly implements language X and you choose option
b, then you mislead your customers. You may claim that your compiler
implements extensions to language X, but if you do so, I would expect the
manual to describe the differences clearly. For example, I would expect that
your optimizer switch would tell me in big, blinking red letters that it
introduces nonstandard semantics.
Tony Li - USC Computer Science Department
Internet: tli@usc.edu Uucp: usc!tli
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{spdcc | ima | lotus}!esegue. Meta-mail to compilers-request@esegue.
Please send responses to the author of the message, not the poster.