[LLVMdev] alias analysis in backend

[Andrew Trick]

On Apr 17, 2013, at 2:33 AM, Hal Finkel <hfinkel at anl.gov> wrote:

> ----- Original Message -----
>> From: "Jonas Paulsson" <jonas.paulsson at ericsson.com>
>> To: "Hal Finkel" <hfinkel at anl.gov>
>> Cc: llvmdev at cs.uiuc.edu
>> Sent: Wednesday, April 17, 2013 12:22:49 AM
>> Subject: RE: [LLVMdev] alias analysis in backend
>> 
>> Hi Hal,
>> 
>> Thanks. How about a symbol with two different immediate offsets - the
>> Value* would be the same, right? I don't see how
>> AliasAnalysis::Location would handle this... And BasicAliasAnalysis
>> does
>> 
>> if (V1 == V2) return MustAlias;
>> 
>> , so I'm not sure how this would be done .. ?
> 
> If you run with -enable-misched -enable-aa-sched-mi 
> 
> then you'll get this logic from the end of MIsNeedChainEdge:
> 
>  // The following interface to AA is fashioned after DAGCombiner::isAlias
>  // and operates with MachineMemOperand offset with some important
>  // assumptions:
>  //   - LLVM fundamentally assumes flat address spaces.
>  //   - MachineOperand offset can *only* result from legalization and
>  //     cannot affect queries other than the trivial case of overlap
>  //     checking.
>  //   - These offsets never wrap and never step outside
>  //     of allocated objects.
>  //   - There should never be any negative offsets here.
>  //
> ...
> 
>  int64_t MinOffset = std::min(MMOa->getOffset(), MMOb->getOffset());
>  int64_t Overlapa = MMOa->getSize() + MMOa->getOffset() - MinOffset;
>  int64_t Overlapb = MMOb->getSize() + MMOb->getOffset() - MinOffset;
> 
>  AliasAnalysis::AliasResult AAResult = AA->alias(
>  AliasAnalysis::Location(MMOa->getValue(), Overlapa,
>                          MMOa->getTBAAInfo()),
>  AliasAnalysis::Location(MMOb->getValue(), Overlapb,
>                          MMOb->getTBAAInfo()));
> 
>  return (AAResult != AliasAnalysis::NoAlias);

This conservatively compensates for loads/stores that were split into narrower accesses during lowering, so doesn't help Jonas.

The MachineMemOperand offset is used differently for FixedFrameIndices, but we don't currently special case it here to disambiguate them. The general problem is that we don't have a  CodeGen-level alias analysis API yet. It looks like this particular case could be fixed with an easy patch though, unless I'm missing something.

-Andy

>>> -----Original Message-----
>>> From: Hal Finkel [mailto:hfinkel at anl.gov]
>>> Sent: Tuesday, April 16, 2013 7:35 PM
>>> To: Jonas Paulsson
>>> Cc: llvmdev at cs.uiuc.edu
>>> Subject: Re: [LLVMdev] alias analysis in backend
>>> 
>>> ----- Original Message -----
>>>> From: "Jonas Paulsson" <jonas.paulsson at ericsson.com>
>>>> To: llvmdev at cs.uiuc.edu
>>>> Sent: Tuesday, April 16, 2013 11:24:36 AM
>>>> Subject: [LLVMdev] alias analysis in backend
>>>> 
>>>> 
>>>> 
>>>> 
>>>> 
>>>> Hi,
>>>> 
>>>> 
>>>> 
>>>> I would like to implement alias analysis in my backend. I would
>>>> like
>>>> to for example get the result that two stack-accesses with
>>>> different
>>>> offsets (indexes), would return noAlias. However, I'm somewhat
>>>> confused as there is no notion of offset for the Location object.
>>>> 
>>>> 
>>>> 
>>>> I would also like to call ScheduleDAGInstr::buildSchedGraph()
>>>> with
>>>> this AliasAnalysis and have MIsNeedsChainEdge() return false in
>>>> this
>>>> case.
>>>> 
>>>> 
>>>> 
>>>> What should I do? Adding a MemoryOperand to such an instruction
>>>> seems
>>>> right, but it doesn't seem to fit quite. What Value would be
>>>> referenced?
>>> 
>>> I think that they should have pseudo-source values, see:
>>> include/llvm/CodeGen/PseudoSourceValue.h
>>> 
>>> I was under the impression that different pseudo source values from
>>> different frame indices already have this no-alias property. If
>>> they
>>> don't, then this seems like a nice general improvement that would
>>> benefit
>>> all backends.
>>> 
>>> -Hal
>>> 
>>>> BasicAliasAnalysis returns MustAlias for the same Value,
>>>> e g 'Stack'.
>>>> 
>>>> 
>>>> 
>>>> Should I implement a target AliasAnalysis, perhaps derived from
>>>> BasicAliasAnalysis, and make it required for my pass that will be
>>>> using it?
>>>> 
>>>> 
>>>> 
>>>> If not, could I make this work with BasicAliasAnalysis by adding
>>>> the
>>>> right memory operands?
>>>> 
>>>> 
>>>> 
>>>> Thanks,
>>>> 
>>>> 
>>>> 
>>>> Jonas Paulsson
>>>> 
>>>> 
>>>> 
>>>> 
>>>> 
>>>> 
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>> 
>> 
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev