[LLVMdev] Alias analysis and instruction level parallelism

[Pertti Kellomäki]

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.

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.

There is a potential combinatorial explosion built into
this, but I don't think it would turn up in practice.
-- 
Pertti