[LLVMdev] alias analysis in backend

[Andrew Trick]

On Apr 18, 2013, at 6:42 AM, Hal Finkel <hfinkel at anl.gov> wrote:

> ----- Original Message -----
>> From: "Andrew Trick" <atrick at apple.com>
>> To: "Hal Finkel" <hfinkel at anl.gov>
>> Cc: "Jonas Paulsson" <jonas.paulsson at ericsson.com>, llvmdev at cs.uiuc.edu
>> Sent: Thursday, April 18, 2013 2:33:52 AM
>> Subject: Re: [LLVMdev] alias analysis in backend
>> 
>> 
>> 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.
> 
> Thanks, I did not understand that. I thought that each different stack slot had its own frame index, or does that only apply to callee-saved and spill slots?

They certainly have their own index. I think the question is where we disambiguate those slots.

I know others have worked on the inverse of this problem (PR12205). Akira? They may remember the details.

I don't normally see raw frame or stack indices since I'm scheduling before regalloc and PEI. Things from the stack are usually arguments or allocas, so they naturally have distinct values.

Jonas, it might help to post a test case and/or file a bug.

-Andy

>> 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130418/5acca6f6/attachment.html>