Path: utzoo!utgpu!water!watmath!clyde!ima!think!barmar
From: barmar@think.COM (Barry Margolin)
Newsgroups: comp.lang.misc
Subject: Re: Query re optimising compilers
Message-ID: <24414@think.UUCP>
Date: 24 Jul 88 08:10:51 GMT
References: <561@etive.ed.ac.uk>
Sender: usenet@think.UUCP
Reply-To: barmar@kulla.think.com.UUCP (Barry Margolin)
Organization: Thinking Machines Corporation, Cambridge, MA
Lines: 60

In article <561@etive.ed.ac.uk> db@lfcs.ed.ac.uk (Dave Berry) writes:
>Would it be sensible to optimise the following code:
>
>a := function ();
>b := (complicated expression) * a;
>
>to the equivalent of:
>
>a:= function ();
>if (a == 0)
>  b := 0;
>else
>  (complicated expression) * a;

I think that would not be a very useful optimization for a compiler to
make in most cases.  This would not speed things up unless function()
is likely to return 0 pretty frequently.  For example, assume that "if
(a == 0)" takes 2 units of time, "b := 0" takes 1 unit of time, and "b
:= (complicated expression) * a" takes 100 units.  100 invocations of
the unoptimized version takes 10,000 units.  If function() returns 0
1% of the time, then 100 invocations of the "optimized" version takes
100*2 (for the test) + 1*1 (for the optimized case) + 99*100 (for the
regular cases) = 10,101, i.e. it is about 1% slower than the original.
For this set of timings, the break even point is when function()
returns 0 2.0202...% of the time.  In general, if the complicated
version takes N times longer than the simple version, and the test
takes M times longer than the simple version, then you win if the test
succeeds more than M/(N-1) of the times.

I would be very surprised if an optimizing compiler were to make this
transformation on its own.  If there were a pragma that permitted the
programmer to inform the compiler of the expected frequency of 0
return values then the compiler could attempt the above computation to
decide whether the transformation improves things.

This should not be confused with the common optimization where boolean
expressions are short-circuited even when non-short-circuit operators
are used.  This can be done when the expressions don't have
side-effects (just like above).  However, since boolean expressions
only have two possible values, true and false, it is quite common for
compiler implementors to assume that each value will occur a
significant fraction of the time.  Under this assumption, the
transformation of

     if <complex-expr> & <simple-expr>
     then <result>

into

     if <simple-expr>
     then if <complex-expr>
	  then <result>

is reasonable.

Barry Margolin
Thinking Machines Corp.

barmar@think.com
{uunet,harvard}!think!barmar