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).
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 think the analysis group idea is a good idea. A standardized
interface for querying this sort of information makes code reuse between
LLVM developers doing different projects easier.
As an example of another transform which requires such information, in
the memory safety work that we do, we have transforms that could benefit
from knowing the range of values that an integer value can take
(specifically, we're usually interested in the min and max values a GEP
index can have). Having a standardized interface would allow us to
re-use analysis passes developed by other LLVM contributors for other
applications, and if we develop a pass that computes such information
more aggressively, it makes it easier for us to write that code in a way
that is usable by the LLVM community at large.
I agree with this approach. Just yesterday I ran into a situation where I
really wanted value range information. I really like the AliasAnalysis design
where cheaper analyses try to give an answer before querying more expensive
analyses. This would fit in well with Nuno's plan to provide analyses with
different time/completeness tradeoffs.
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.