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..? Regards, Nuno
Nuno Lopes 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 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. -- John T.> 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..? > > Regards, > Nuno > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
On Tuesday 20 January 2009 12:09, John Criswell wrote:> > 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. -Dave
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