[LLVMdev] HazardRecognizer and RegisterAllocation

[Dan Gohman]

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