From: pcg@aber.ac.uk (Piercarlo Grandi)
Newsgroups: comp.compilers
Subject: Re: static estimation of conditional branches?
Keywords: optimize, analysis, algol68
Date: 15 Dec 92 15:36:14 GMT
Reply-To: pcg@aber.ac.uk (Piercarlo Grandi)
Organization: Prifysgol Cymru, Aberystwyth

(Herman Rubin) writes:
> ... the programmer should have some way of communicating this,
> and other, frequency considerations to the compiler.  As far as
> I know, this has not been done since the "FREQUENCY" statement
> in fairly early Fortran.  [As I recall, Fortran II dropped
> FREQUENCY because it was infrequently used and made little
> difference.  I've heard that it may even have been implemented
> backwards and nobody noticed. -John]

Actually there was an Algol 68 compiler with a kind of 'rarely' gragma, to
be used usually after then or else, as in

	IF a < b THEN ... ELSE PR rarely PR ... FI

Such a pragma has important performance effects; not only it helps with
instruction scheduling, and avoiding wasting optimizer effort and table
space on infrequently executed basic blocks, it also allows the rarely
executed code to be offlined to some other section of the executable.

This often substantially reduces the working set of the code, as in most
production programs a lot of code is involved only in initial setup, and
in error handling, and it is only executed once or never at all; and it's
bad if it gets interspepsed within the code that really does the work.

Henry Spencer responded:
> The other problem that occurs with such facilities is that
> programmer intuition is notoriously unreliable about such things.

But this is not a compiler problem -- it is a programmer education
problem. If the programmer does not know the macroscopic performance
profile of the algorithms used, then too bad. And intuition has nothing to
do with knowing such things; programmers that deserve the title either
know the properties of the algorithms they use, or they analyze them with
the right tools; not many do either.

I reckon that one of the two cases where even a programmer often gets
surprised is not the level of algorithmic complexity, but at the level of
the actual implementation and its interactions with the performance
profile of the environment, which is often poorly documented.

The other major cause of programmer surprise is that quite often the input
data fed to the program is quite different in consequences from that
expected by the programmer; and because such a case is frequent, this is
often not terribly useful:

> Now, if you amend Herman's statement to "the *profiler* should
> have some way of communicating this...", I'd agree... and observe
> that there are already compilers that will accept profiler data
> and exploit it for optimization.

because the profiler data can be misleading unless the data used to
generate the profile fed to the optimizer can be guaranteed to be typical.
But then a programmer that knows which input data are typical as to the
performance of his program already knows its performance profile, or at
least is competent enough to also be able to understand the algorithms he
uses and interpret and weight profiler data.

Unfortunately most programmers don't have a clue as to the performance
profile of the algorithms they use, and cannot interpret profile data, and
equivalently could not choose a set of appropriate input data for the runs
that would drive the optimizer.

> I don't know whether they do this particular optimization, but I
> wouldn't be surprised.

There are some compilers that use profiler output, e.g. notably the MIPS
compilers. But Hank Dietz (if I remember well) has done some studies on
(looping) branch prediction and apparently static prediction works well
there too.

--
Piercarlo Grandi, Dept of CS, PC/UW@Aberystwyth <pcg@aber.ac.uk>
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers