On Monday 18 August 2008 17:21, Chris Lattner wrote:> On Aug 18, 2008, at 3:19 PM, David Greene wrote: > > I'm not quite understanding how one would use the existing alias > > analysis > > framework to represent a flow-sensitive analysis. > > Yep, the current infrastructure isn't set up to support this. > > I haven't seen a real world case where flow sensitive AA is useful.Yes, in the general case, flow-sensitive AA isn't worth it.> Normally, the conversion to SSA form is sufficient. Can you talk > about cases where this matters to you?Mostly it involves tying into our memory dependence analysis which annotates things on program points. I need a way to translate back to our optimizer data structures. So it's not "flow-sensitive AA" in the strictest sense but it does require program point information. I looked at MemoryDependenceAnalysis and it's not quite what I want. I need to know things like "does this load and store pair interfere," not "give me the most recent instruction that interferes with this memory operation." It's the kinds of things you'd want to ask for scheduling purposes, where no particular instruction ordering is assumed. -Dave
On Monday 18 August 2008 17:48, David Greene wrote:> > Normally, the conversion to SSA form is sufficient. Can you talk > > about cases where this matters to you? > > Mostly it involves tying into our memory dependence analysis which > annotates things on program points. I need a way to translate back > to our optimizer data structures. > > So it's not "flow-sensitive AA" in the strictest sense but it does require > program point information.Ok, so this is not the ideal way to do things. AliasAnalysis was just a convenient way to hook into something. But as I've gone through this I've realized it's just not going to work very well. What I really need is a dependence analysis interface. I need to know about loop-carried dependencies and that sort of things, whether two memory operations reference the same data, distance information, etc.. As far as I can tell, there's no infrastructure for this in LLVM. I don't actually need the analysis because we have it in our optimizer. What I need is some kind of interface akin to AliasAnalysis that can chain analyses, etc. I'm sure there are others working on this. I believe Vikram mentioned his group is working on a parallelizing compiler based on LLVM. I would think it would be straightforward to taken the AliasAnalysis interface and essentially duplicate it and call it DependenceAnalysis or some such thing. But if someone's already done this I'd rather not duplicate the effort. -Dave
Chris Lattner
2008-Aug-20 16:27 UTC
[LLVMdev] Dependence Analysis [was: Flow-Sensitive AA]
On Aug 20, 2008, at 8:56 AM, David Greene wrote:> What I really need is a dependence analysis interface. I need to know > about loop-carried dependencies and that sort of things, whether two > memory > operations reference the same data, distance information, etc.. As > far as I > can tell, there's no infrastructure for this in LLVM.Right, this is something we've wanted for a long time, but noone has stepped up to add.> I don't actually need the analysis because we have it in our > optimizer. What > I need is some kind of interface akin to AliasAnalysis that can chain > analyses, etc.Ok.> I'm sure there are others working on this. I believe Vikram > mentioned his > group is working on a parallelizing compiler based on LLVM.That project is just barely starting to get off the ground and will take awhile before it starts doing much, as far as I know.> I would think it would be straightforward to taken the AliasAnalysis > interface > and essentially duplicate it and call it DependenceAnalysis or some > such > thing. But if someone's already done this I'd rather not duplicate > the > effort.In theory, it should be pretty easy to create a new DependenceAnalysis analysis class and start piping it around. It would be nice if there was a trivial implementation so that we can write regtests. -Chris