[pypy-dev] More on optimization

holger krekel hpk at trillke.net
Wed Nov 3 16:40:01 CET 2004


Hi again, 

[Armin Rigo Wed, Nov 03, 2004 at 02:50:46PM +0000]
> Hi Holger,
> 
> On Wed, Nov 03, 2004 at 03:28:42PM +0100, holger krekel wrote:
> > So we do already keep possibly different function versions for
> > differently typed sets of input parameters to this function?
> 
> Er, no...
> 
> > I guess i am mixing up flow analysis and annotation somewhat
> > here. Or even have a deeper misunderstanding :-)
> 
> Hum.  We have the flow analysis which, using merge point detection, produces a
> flow graph that follows the control flow of the input functions (one graph per
> function).  This works fine and we don't plan to change anything there.
> 
> Then we have the annotation phase which follows by abstract interpretation the
> existing flow graphs, ... 

me hum, too :-) this means that 

    http://codespeak.net/pypy/index.cgi?doc/architecture.html

is not right when it says: 

    The translation process is done in three steps:

    - producing a flow graph representation of the standard
      interpreter. A combination of a plain interpreter and a
      flow object space performs "abstract interpretation" to record
      the flow of objects and execution throughout a python program
      into such a flow graph.

    - ... 

because your current prescribed notion of abstract
interpretation starts with already existing flow graphs. Hum. 

I am ready to accept your current use of the terms but it is
confusing that we keep changing notions and terms quite a bit ... 
I guess that when i get confused about this that other 
people could get confused about this as well. 

> and which merges the dicovered information exactly when
> two branches meet in flow graph.  This is a "flow-sensitive" kind of
> analysis.  It is good because in this kind of code:
> 
>    if x:
>        y = 1
>    else:
>        y = 2
> 
> when the annotation follows the flow graph of this piece of code, if 'x' is
> not a constant, then both paths are followed and when the two paths merge, the
> two incompatible results ("y is the constant 1" and "y is the constant 2") are
> merged into less precise information ("y is an integer").  But if 'x' is a
> constant, then only one path will be followed, and we keep the precise
> knowledge of the value of 'y' even after the if/else statement.

But if one part of the program uses the one branch and another
part uses the other branch then you will generalize the function
to annotate 'y' as being an integer. This was what i was refering
to when i was suprisedly asking: 

    So we do already keep possibly different function versions
    for differently typed sets of input parameters to this function?

to which the answer apparently is "no".  Only when just one branch
is used will the flow-sensitive annotation analysis regard 'y' as
being a constant. 

> > right. They have to do that because they look at the static 
> > source code and not at a representation obtained from abstract 
> > execution like we do in objspace/flow. 
> 
> No, that's not related.  It's just that there are big advantages if you don't
> care about the precise flow for some kind of algorithms.  We could also
> collect all the operations that appear in a flow graph and deduce things in a
> flow-insensitive manner if we wanted to; and conversely Starkiller could also
> look at the static source and still infer things in a more flow-sensitive way.

But in order to do that starkiller would probably need to utilize a
representation that is reflecting the actual possible flows of
execution.  

I didn't intend to claim that looking at source code couldn't
be done in a flow-sensitive manner.  Such a claim wouldn't
make much sense as source code and its execution flow are
mostly equivalent.

cheers, 

    holger



More information about the Pypy-dev mailing list