[LLVMdev] alias information in codegen

[Dan Gohman]

There have been a few queries about this recently, and I've done some
work in this area recently, so I'm posting a summary of what the major
outstanding issues are.

* BasicAliasAnalysis, the default AliasAnalysis implementation, doesn't
   understand lowered GEPs, integer arithmetic, or PHIs, and the
   regular codegen process involves passes that lower GEPs.

One way to solve this is to use a different AliasAnalysis  
implementation.
I haven't looked at it in detail, but I'd guess that the Andersen's
pass handles all of these constructs reasonably well. And it has the
advantage of being much more capable than the BasicAliasAnalysis.

Another alternative is to develop a SCEV-based alias analysis. The SCEV
framework currently has the opposite problem; it understands integer
arithmetic and PHIs quite well, but doesn't currently understand GEPs.
I know it can be made to understand GEPs though, and it's on my TODO
list to implement this.

* There are still a variety of places in SelectionDAG creation that
   don't preserve SVOperand/SVOffset (as well as alignment and  
volatile).

These places need to be found and fixed. This is pretty straight- 
forward,
and the places that need changing can be found by inserting some
strategic assert(SVOperand)'s.

  * The DAGCombiner's alias-analysis handling isn't ideal.

This is the -combiner-alias-analysis and -combiner-global-alias-analysis
options. They basically work, though they aren't turned on by default
currently. The algorithm used wants some scrutiny as well.

  * MachineInstrs currently don't reliably record information about
    memory accesses.

This is being addressed by MemOperands. However, currently there is a
problem; the current code misses memory references in anonymous
patterns, like this in x86:

def : Pat<(zextloadi64i32 addr:$src),
           (SUBREG_TO_REG (i64 0), (MOV32rm addr:$src),  
x86_subreg_32bit)>;

I can provide more details about what's going on here if anyone's
interested.

However, for people just interested in post-regalloc scheduling and
VLIW packing and similar things, MemOperands aren't the only approach.
A potentially better way to do this would be to extend MachineInstrs
to preserve the chain dependencies from the SelectionDAG.

This would be more efficient, as the SelectionDAG already needs a full
dependence graph, so there's no need to make any further alias queries.
There would be some details to resolve, such as how to handle loads
and stores inserted after instruction selection. Also, this depends on
the SelectionDAG having good dependence information, but improving
that would be beneficial for pre-regalloc scheduling as well.

Dan