llvm dev - Oct 2012 - [LLVMdev] A question about pointer aliasing rules in LLVM

On 10/25/2012 5:36 PM, Dan Gohman wrote:
>
> First, yes, it is wrong for AliasAnalysis implementations to trust LLVM
> IR types, for the most part. There's nothing in LLVM IR which would
> prevent you from having two myStruct instances which overlap here,
> sharing 4 bytes. Because of that, next really could be equal to &prev.
>
> In theory, you could help this situation by using TBAA; you could give
> next and prev fields different TBAA tags to say that a store to a next
> field never stores to a prev field.
In practice this is impossible to guarantee.  The only safe way of 
disambiguating the two objects is to prove that the pointers are different.

-Krzysztof

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation

On Thu, Oct 25, 2012 at 5:32 PM, Krzysztof Parzyszek <
kparzysz at codeaurora.org> wrote:
> On 10/25/2012 5:36 PM, Dan Gohman wrote:
>
>>
>> First, yes, it is wrong for AliasAnalysis implementations to trust LLVM
>> IR types, for the most part. There's nothing in LLVM IR which would
>> prevent you from having two myStruct instances which overlap here,
>> sharing 4 bytes. Because of that, next really could be equal to
&prev.
>>
>> In theory, you could help this situation by using TBAA; you could give
>> next and prev fields different TBAA tags to say that a store to a next
>> field never stores to a prev field.
>>
>
> In practice this is impossible to guarantee.  The only safe way of
> disambiguating the two objects is to prove that the pointers are different.
>
It may be impossible to guarantee if the input language is C (depending on
how you interpret it).

However, the point of LLVM's TBAA system is to let front-ends make
statements about aliasing that are difficult or impossible to prove from
the IR alone. Front-ends for more restrictive source languages may actually
be able to make guarantees about how linked list pointers are used. LLVM's
TBAA tags are a way for them to describe at least some of those guarantees
to optimizers.

Unless you're objecting to the fact that while LLVM says that metadata
*may* be stripped at any time, there are no rules for when it *must* be
stripped, and that arbitrary valid transformations can theoretically cause
valid TBAA and other metadata to become invalid. This is true. This is an
area where LLVM's preference for practicality over absolute correctness may
be observed.

Dan
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20121026/bcf5d8d2/attachment.html>

On 10/26/2012 10:35 AM, Dan Gohman wrote:
>
> It may be impossible to guarantee if the input language is C (depending
> on how you interpret it).
>
> However, the point of LLVM's TBAA system is to let front-ends make
> statements about aliasing that are difficult or impossible to prove from
> the IR alone. Front-ends for more restrictive source languages may
> actually be able to make guarantees about how linked list pointers are
> used. LLVM's TBAA tags are a way for them to describe at least some of
> those guarantees to optimizers.
>
> Unless you're objecting to the fact that while LLVM says that metadata
> *may* be stripped at any time, there are no rules for when it *must* be
> stripped, and that arbitrary valid transformations can theoretically
> cause valid TBAA and other metadata to become invalid. This is true.
> This is an area where LLVM's preference for practicality over absolute
> correctness may be observed.
I was writing with the C/C++ language in mind (since that was the 
language from the original post).

I didn't think of the last point you're making, but it actually does 
seem like a concern.  If metadata is there to provide extra information 
allowing the compiler to perform otherwise unsafe optimizations, the 
possibility that it may become outdates poses a real risk.


-Krzysztof


-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation