Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!rpi!bu.edu!husc6!spdcc!esegue!compilers-sender
From: icsu8209@nero.cs.montana.edu (Glassy)
Newsgroups: comp.compilers
Subject: SLO too slow?
Keywords: optimize
Message-ID: <9009031649.AA02942@nero.cs.montana.edu>
Date: 3 Sep 90 16:49:11 GMT
Sender: compilers-sender@esegue.segue.boston.ma.us
Reply-To: icsu8209@nero.cs.montana.edu (Glassy)
Organization: Compilers Central
Lines: 61
Approved: compilers@esegue.segue.boston.ma.us

Hello.  I'm looking for information on source-level optimization (SLO,
coinage mine); specifically, for techniques one would use to incorporate
improvements to source-level code in a machine-independent way.

The idea, of course, is a portable optimiser.  Code improvements like CSE,
code motion, and strength reduction should (I wonder) be possible to perform
at the source level, instead of only at the IR level (which is what seems
most common).

The advantage of SLO over IR optimization, besides portability, would be that
a human could actually -read- the optimized source, and verify that the
optimizer is not mangling (too badly) the semantics of one's code.  Heaven
help the person who wants to read IR code...(or even debug it).  

(No flame intended to toilers in this area: I realize that great strides are
being made in debugging optimized code; maybe I'm a dinosaur that still
believes in the Mk. 1 Mod 0 Calibrated-Eyeball approach to code correctness.)

The price of portability?  With SLO, you lose machine-dependent optimizations
(e.g. splendid register allocation schemes).  My question is, how much
performance (speed or space) does a typical (tm) program gain from
machine-independent optimizations, and how much from machine-dependent ones?
(I know real cases exist where declaring something as 'register' yields 300%
speedup...I'm looking for journal, TR, TM sorts of references...not that
written evidence is more true or real than anecdotal evidence, just easier to
wade through.)

Scanning through about 15 yrs of BIT, 15 yrs of Computer Journal, 10 yrs of
CACM, and 9 yrs of Journal of Soft. Exp. and Prac., I found -one- reference
to SLO: an article in CJ, c.late 60's, in which a person in the UK described
an SLO for FORTRAN, and noted that 

  SLO + test program, gave almost as much speed gain as
  Optimizing Compiler + Optimizer On + test program.

(The baselines in his tests, were the original test programs compiled with
all optimization disabled.)

(I can dig up the specific CJ SLO reference if anyone wants it.)

In raw economic terms, I understand that fast buggy code will always outsell
not-so-fast correct code.  Let me abandon the business question (will it
sell?), and focus just on the basic empirical ones:

Is SLO used in commercially available compilers?  Is it so 'old hat'
that no one even mentions it anymore?

Has SLO been tried, and abandoned as impractical?

Is SLO too slow?

Thanks,
Lou Glassy (icsu8209@caesar.cs.montana.edu)

p.s. Please email replies, and I'll be glad to summarize in a week or
two.  or post, as you see fit...
[I'm sure this has been discussed before, but I can't find any reference
to it in the compilers archive. -John]
-- 
Send compilers articles to compilers@esegue.segue.boston.ma.us
{ima | spdcc | world}!esegue.  Meta-mail to compilers-request@esegue.