On Monday 19 January 2009 18:21, Dan Gohman wrote:> > Dan, how does the scheduler handle memory dependence? I'm working on > > something that requires memory dependence information for > > MachineInstructions. > > At the moment, it knows simple things, like constant pool loads > don't have dependencies, and references to distinct stack slots are > independent, and so on.Ok.> I have a few ideas for how more precise memory dependencies might be > achieved. > > We have MachineMemOperands, which can be used to make AliasAnalysis > or other LLVM-IR-level analysis queries. They need some work though; > the main issue is that there are some places in codegen that don't > preserve them.Where are those places? Can they be used in conjunction with MemoryDependenceAnalysis? e.g. can we write a MachineInstructions-based memory dependence analysis that uses MachineMemoryOperands?> Another possibility is to record dependence information from the > SelectionDAG in MachineInstrs somehow. We don't yet have precise > memory dependencies in the SelectionDAG, but it would be good to > fix that too :-).Agreed.> This would probably also involve AliasAnalysis queries from codegen, > possibly going though the MemoryDependenceAnalysis interface.Do you have a vision for how this might work? Wouldn't we need a new MachineFunctionPass to essentially do the same thing as MemoryDependenceAnalysis? I don't think it's sufficient to just preserve the information we had from Instructions. Codegen might introduce new memory operations after lowering (spilling, for example). Some of these might be easily analyzable (spills) but others might not be. But maybe we don't need to worry about that right now. As I think about the problem I'm working on, "merely" preserving dependence information from Instructions would help. It seems like if we can preserve that information in SelectionDAG we ought to be able to record it in MachineInstructions (or MachineMemOperands?) when lowering. Hmm...then again looking at the MachineMemOperand documentation, fixing the places that invalidate those might work well too. I'm a little wary of having the same information in two different places. -Dave
On Jan 19, 2009, at 5:06 PM, David Greene wrote:> On Monday 19 January 2009 18:21, Dan Gohman wrote: > >>> Dan, how does the scheduler handle memory dependence? I'm working >>> on >>> something that requires memory dependence information for >>> MachineInstructions. >> >> At the moment, it knows simple things, like constant pool loads >> don't have dependencies, and references to distinct stack slots are >> independent, and so on. > > Ok. > >> I have a few ideas for how more precise memory dependencies might be >> achieved. >> >> We have MachineMemOperands, which can be used to make AliasAnalysis >> or other LLVM-IR-level analysis queries. They need some work though; >> the main issue is that there are some places in codegen that don't >> preserve them. > > Where are those places?We don't have a definite list. It's largely testable though; you could add an assert like this: !(MI->mayLoad() || MI->mayStore()) || !MI->memoperands_empty() to catch most cases. There may not be many places left at this point.> Can they be used in conjunction with > MemoryDependenceAnalysis? e.g. can we write a MachineInstructions- > based > memory dependence analysis that uses MachineMemoryOperands?Right, the existing MemoryDependenceAnalysis works in terms of LLVM-IR-level Instructions, but yes, it would be possible to implement the same thing for MachineInstrs, using AliasAnalysis queries from MachineMemOperands. As of this writing I'm not prepared to guess whether this would be a good idea :-).> > >> Another possibility is to record dependence information from the >> SelectionDAG in MachineInstrs somehow. We don't yet have precise >> memory dependencies in the SelectionDAG, but it would be good to >> fix that too :-). > > Agreed. > >> This would probably also involve AliasAnalysis queries from codegen, >> possibly going though the MemoryDependenceAnalysis interface. > > Do you have a vision for how this might work? Wouldn't we need a new > MachineFunctionPass to essentially do the same thing as > MemoryDependenceAnalysis?A possible vision is that SelectionDAGBuild could use MemoryDependenceAnalysis when building the initial SelectionDAG. It's walking the IR-level Instructions, so it can use any IR-level analysis. I haven't yet looked into this in detail. A significant question is whether non-local dependencies are important; some day we may extend SelectionDAGs to handle more than one block at a time.> > > I don't think it's sufficient to just preserve the information we > had from > Instructions. Codegen might introduce new memory operations after > lowering > (spilling, for example). Some of these might be easily analyzable > (spills) > but others might not be.This is where PseudoSourceValues come in. There are pseudo-values representing the stack, constants area, GOT, and other memory locations that aren't represented at the LLVM-IR level.> > > But maybe we don't need to worry about that right now. As I think > about the > problem I'm working on, "merely" preserving dependence information > from > Instructions would help. It seems like if we can preserve that > information in > SelectionDAG we ought to be able to record it in MachineInstructions > (or > MachineMemOperands?) when lowering. > > Hmm...then again looking at the MachineMemOperand documentation, > fixing the > places that invalidate those might work well too. I'm a little wary > of having > the same information in two different places.I think the biggest challenge here is finding a design that is reasonably efficient in terms of compile time and space while still providing useful information. Dan
On Monday 19 January 2009 19:47, Dan Gohman wrote:> > Can they be used in conjunction with > > MemoryDependenceAnalysis? e.g. can we write a MachineInstructions- > > based > > memory dependence analysis that uses MachineMemoryOperands? > > Right, the existing MemoryDependenceAnalysis works in terms of > LLVM-IR-level Instructions, but yes, it would be possible to > implement the same thing for MachineInstrs, using AliasAnalysis > queries from MachineMemOperands. As of this writing I'm not > prepared to guess whether this would be a good idea :-).Sure. It seems fairly straightforward though. Heck, it might even be possible to take MemoryDependenceAnalysis and turn it into generic code that could operate on Instructions or MachineMemOperands.> >> This would probably also involve AliasAnalysis queries from codegen, > >> possibly going though the MemoryDependenceAnalysis interface. > > > > Do you have a vision for how this might work? Wouldn't we need a new > > MachineFunctionPass to essentially do the same thing as > > MemoryDependenceAnalysis? > > A possible vision is that SelectionDAGBuild could use > MemoryDependenceAnalysis when building the initial SelectionDAG. > It's walking the IR-level Instructions, so it can use any > IR-level analysis. I haven't yet looked into this in detail. > A significant question is whether non-local dependencies are > important; some day we may extend SelectionDAGs to handle > more than one block at a time.I should think non-local dependencies would be important. We have a number of machine code passes that work globally.> > I don't think it's sufficient to just preserve the information we > > had from > > Instructions. Codegen might introduce new memory operations after > > lowering > > (spilling, for example). Some of these might be easily analyzable > > (spills) > > but others might not be. > > This is where PseudoSourceValues come in. There are pseudo-values > representing the stack, constants area, GOT, and other memory > locations that aren't represented at the LLVM-IR level.Ok, that's good. But what happens if some codegen pass deletes a memory instruction (or a Value or whatever) and recreates it elsewhere. Presumably the dependence information would be lost. How would we re-generate it.> I think the biggest challenge here is finding a design that > is reasonably efficient in terms of compile time and space while > still providing useful information.Isn't that the definition of compiler development? :) -Dave