[pypy-dev] More on optimization

[Armin Rigo]

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, 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.

Flow-insensitive algorithms just look at the whole function and see two
statements: "y=1" and "y=2".  From that they guess that 'y' must be an integer
no matter what.  They can't tell you the value of 'y' even if they knew the
value of 'x'.  This difference is in the algorithm used; it's not related to:

> 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.


A bientôt,

Armin.