[LLVMdev] value tracking

[Adam Olsen]

On Mon, Jan 19, 2009 at 4:54 PM, Nuno Lopes <nunoplopes at sapo.pt> wrote:
> Hi,
>
> I've been thinking about a (potentially lazy) value tracking analysis that
> could be reused by several optimization passes. I don't know if it exists in
> llvm or not, but to my better knowledge it does not. ok there exists the
> ValueTracking class, but it does not provide a function like e.g.
> MayHaveTheValue(Value* v, APSInt x) to check if a given var v may ever have
> the value x
>
> My proposal:
>  - create a value tracking analysis interface that can provide extensive
> info about vars (e.g. the set of possible values for a given vars, etc..)
>  - implement that interface in several ways with different tradeoffs of
> preciseness vs speed (e.g. range analysis, value set tracking, path
> sensitive or not, interprocedural, etc..)
>
> I believe this could reuse some code from PredSimplify and hopefully make it
> a very simple pass (as much of the work would then be hidden in the value
> tracking analysis).
> Having this sort of readily available analysis would allow us to build other
> optimization more easily. I've already a few ideas in mind (I've implemented
> one of them, but I had to unnecessarily implement too much of this value
> tracking logic).
>
> Any ideas, opinions, etc..?

I'm experimenting with doing value tracking of Python code.  I likely
have to go a lot further than you do:

* variables don't have a type, so I treat the type as just another
value to track
* integers have no limit, so I break them down into many different
ranges and let it step up through them
* classes and methods are just more variables to track
* all variables start out undefined, so I need DSA (dynamic single
assignment) to eliminate that
* DSA at the global scope is likely to scale very badly, so I'll be
playing with various alternatives

Those familiar with Python will know there's various sources of
unbounded dynamism, such as exec().  To control that I'm adding a sort
of privates, except everybody in your own "compartment" is your
friend.  A compartment is a collection of code compiled as a single
unit, and usually (other than an interactive interpreter) is closed to
adding new code; you can create a new compartment to load a plugin
though.


-- 
Adam Olsen, aka Rhamphoryncus