Why heuristic optimization is wrong.

Charles Fiterman <cef@geodesic.com>
20 Dec 1995 11:37:37 -0500

          From comp.compilers

Related articles
Grammars for future languages schinz@guano.alphanet.ch (1995-10-22)
heuristic optimizations [was "Death by error checks."] mcintosh@rice.edu (1995-12-19)
Why heuristic optimization is wrong. cef@geodesic.com (Charles Fiterman) (1995-12-20)
| List of all articles for this month |

From: Charles Fiterman <cef@geodesic.com>
Newsgroups: comp.compilers
Date: 20 Dec 1995 11:37:37 -0500
Organization: Geodesic Systems
References: 95-10-103 95-12-125
Keywords: optimize

First by heuristic optimization I mean things like reduction in
strength, which is buggy where code depends on overflow. Not loop
unrolling, which may be unprofitable but which never causes bugs.

If you have heuristic optimization you must have a switch to turn it
off. Since there are a lot of heuristic optimizations you are stuck
with a lot of compiler switches. If you have ten two way switches you
must then run your tests 1024 times to get simple coverage and ship
your compiler. Since good compiler test streams run for about two days
this means 2048 days of testing to ship ... if nothing goes wrong.

Now suppose the user has a condition that breaks an optimization. The
debugger will show unoptimized code, or De-optimized code, which is
correct. The only useful approach is to explain the optimizations and
allow him to debug optimized code. Few users can live with this.

Few users can live with the explanation that "Reduction in strength
assumes code does not depend on overflow. You used it and your code
depends on overflow." They go off saying your compiler is buggy.
[Most languages that I know forbid depending on overflow. It's the
same old problem: just because one Fortran compiler runs your program
doesn't mean it's Fortran. -John]


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.