Simple question about how the optimizer works

[Robin Becker]

In article <mailman.1021020318.20910.python-list at python.org>, James J.
Besemer <jb at cascade-sys.com> writes
>
>Robin Becker wrote:
>
>> In article <mailman.1021010718.12133.python-list at python.org>, James J.
>> Besemer <jb at cascade-sys.com> writes
>> .....
>> >
>> >The way most optimizers work is they detect patterns known to be safe and 
>also
>> >sufficiently common to be worth dealing with.  Anything that does not fit 
>the
>> >pattern 100% does not get optimized.
>> >
>> .....
>> Well strictly speaking this is untrue. This class of optimisation is
>> called 'local', 'greedy' or perhaps 'peephole'. Since in fact they may
>> not be optimal these methods are really improvers. As to whether most
>> optimisers are like this I suppose all the compiler builders who claim
>> 'global' etc etc may want to dispute.
>
>No, I was using "pattern" in it's most general sense, meaning to include both
>global and local optimizers.  In this overall thread I have alluded to examples 
>in
>both extremes.
>
>Global optimizers typically examine the attributed parse tree for an entire 
>module
>(multiple variable and function declarations), searching for arbitrarily 
>complex
>"patterns" in the overall tree.  When there's a "match," an arbitrarily complex
>transformation may be applied to the tree.  Analysis can can include 
>determining
>data flows and control flows, necssary to handle some of the tricky things even 
>in
>
.....
well I disagree with the term pattern in this reply as it implies
something that matches anything which is optimisable ie such a pattern
must match all inputs. The problem of code optimisation problem is
approximately

choose c to optimise F(c,X(c,d))
      such that X(c,d)=S(p,d)
c=code
p=program
d=program data
F=utility function ie code size/speed etc
X=execution function
S=semantic function

expressed in this form looking for patterns in p is clearly wrong since
S(p,d) is fixed for a particular program only up to the program data
which we don't normally know. Classic example is all that loop hoisting
which is wasteful if the loop never actually gets used.

Real experts on optimisation will also tell us that there are extended
versions of the above eg vector valued F etc etc and will almost always
be very cautious about solvability.

Clearly the most important thing here is to ensure feasibility ie
X(c,d)=S(p,d) for all d; I suppose that's what we mean by safe.

>James J. Besemer  503-280-0838 voice
>http://cascade-sys.com  503-280-0375 fax
>mailto:jb at cascade-sys.com
-- 
Robin Becker