[LLVMdev] Alias analysis and instruction level parallelism

[Dan Gohman]

On Apr 3, 2008, at 2:20 PM, Pertti Kellomäki wrote:
> Dan Gohman wrote:
>> I think this is trickier than it sounds; the reason GEPs are lowered
>> is to
>> allow strength-reduction and other things to do transformations on  
>> them.
>> It would require those passes to know how to update the mapping.
>
> Yes, I do appreciate the amount of work involved, and I am
> very open to other suggestions.

To clarify, I was responding to the approach of mapping
address values back to their original GEP instructions
here.

>
>
> What the backend really needs to know is what loads and
> stores are independent of each other. When looking at a
> scheduling region (basic block for now), we already know
> at the LLVM IR level which loads and stores could potentially
> be scheduled at the same cycle, so essentially we can
> anticipate which alias queries the backend would make.
>
> An alternative game plan would then be to identify the
> loads and stores of interest, do the alias queries
> at the LLVM IR level, and store the independence info
> somewhere. The back end would then trace the target memory
> references back to LLVM IR loads and stores, and consult
> the stored independence information while scheduling.
>
> It seems to me that this should be safe, at least if
> one is careful about what passes are run between
> the alias analysis and the back end. I cannot think
> of anything offhand that could make two independent
> memory references to be dependent, which would need
> to happen in order for things to go bad.

I agree. I think what you're describing here and what
I described in a separate email are very similar :-).

The current SelectionDAG already has a way to store the
the information you want here, using its chain dependencies.
It needs improvement to do a better job identifying
interesting loads and stores and making alias queries --
the things you're describing here.

If we do that, and then preserve this dependency information
when SelectionDAG nodes are translated to MachineInstrs,
we'll have a very useful system.

Dan