llvm dev - Feb 2019 - Precise meaning of must alias?

I find myself needing to ask a very basic question. Specifically, what 
do we expect "must alias" to mean in practice?

Consider a simple example:

load i64, i64* %p
%p.i32 = bitcast i64* %p to i32*
load i32, i32* %p.i32

Given two memory locations which describe the two memory accesses of 
these loads, do we expect that alias analysis returns MustAlias?  That 
is, when we have two accesses to the same pointer, but *different* 
sizes, does that result in MustAlias?

(Just to be clear, MayAlias is clearly a valid answer.  I'm really 
asking if we can legally return MustAlias for these.)

I would have said up until recently, that the correct result would be a 
PartialAlias, not a MustAlias.  However, we seem to be quite consistent 
about returning MustAlias in cases where we know the base of the access 
is common, but don't know the sizes are equal or even non-zero.

I can see four possible meanings of must alias:

 1. A must alias result indicates that the exact same bits in memory are
    accessed by both.  (This requires both pointer and size to be equal
    at runtime.)
 2. A must alias result indicates that *at least one* bit in memory is
    accessed by both.  (This allows unequal pointers, and unequal sizes,
    but not zero sizes.)
 3. A must alias result indicates that the two pointers must be equal
    when accessed at runtime.  (This allows unequal sizes, and zero
    sizes, but restricts the pointers to be equal.)
 4. A must alias result indicates that *at least one* bit in memory is
    accessed by both, unless one of the two accesses has size 0 at
    runtime.  (This is the weakest.)

I'd always thought that (1) was the correct answer, but now I find 
myself wondering.  From the code, (3) seems to be the closest match to 
what we actually implement, but we're not entirely consistent there 
either.  What do others think?

Philip


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190211/06331f2d/attachment.html>

Yep, the typical answer is MustAlias here.  You can see this because BasicAA
looks through pointer bitcasts, and eventually returns MustAlias when the
Value*’s are the same.

-Chris
> On Feb 11, 2019, at 3:14 PM, Philip Reames via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> I find myself needing to ask a very basic question.  Specifically, what do
we expect "must alias" to mean in practice?
> 
> Consider a simple example:
> 
> load i64, i64* %p
> %p.i32 = bitcast i64* %p to i32*
> load i32, i32* %p.i32
> 
> Given two memory locations which describe the two memory accesses of these
loads, do we expect that alias analysis returns MustAlias?  That is, when we
have two accesses to the same pointer, but *different* sizes, does that result
in MustAlias?
> 
> (Just to be clear, MayAlias is clearly a valid answer.  I'm really
asking if we can legally return MustAlias for these.)
> I would have said up until recently, that the correct result would be a
PartialAlias, not a MustAlias.  However, we seem to be quite consistent about
returning MustAlias in cases where we know the base of the access is common, but
don't know the sizes are equal or even non-zero.
> I can see four possible meanings of must alias:
> A must alias result indicates that the exact same bits in memory are
accessed by both.  (This requires both pointer and size to be equal at runtime.)
> A must alias result indicates that *at least one* bit in memory is accessed
by both.  (This allows unequal pointers, and unequal sizes, but not zero sizes.)
> A must alias result indicates that the two pointers must be equal when
accessed at runtime.  (This allows unequal sizes, and         zero sizes, but
restricts the pointers to be equal.)
> A must alias result indicates that *at least one* bit in memory is accessed
by both, unless one of the two accesses has size 0 at runtime.  (This is the
weakest.)
> I'd always thought that (1) was the correct answer, but now I find
myself wondering.  From the code, (3) seems to be the closest match to what we
actually implement, but we're not entirely consistent there either.  What do
others think?
> 
> Philip
> 
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190213/1c609439/attachment.html>

On 2/13/19 2:55 AM, Chris Lattner via llvm-dev wrote:
Yep, the typical answer is MustAlias here.  You can see this because BasicAA
looks through pointer bitcasts, and eventually returns MustAlias when the
Value*’s are the same.


At the IR level, the sizes of the types on the pointers aren't really
semantically meaningful. They are meaningful for ModRef queries, for which we do
now also have 'Must' answers, and there we might also want to check the
size?

 -Hal

-Chris

On Feb 11, 2019, at 3:14 PM, Philip Reames via llvm-dev <llvm-dev at
lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:


I find myself needing to ask a very basic question.  Specifically, what do we
expect "must alias" to mean in practice?

Consider a simple example:

load i64, i64* %p
%p.i32 = bitcast i64* %p to i32*
load i32, i32* %p.i32

Given two memory locations which describe the two memory accesses of these
loads, do we expect that alias analysis returns MustAlias?  That is, when we
have two accesses to the same pointer, but *different* sizes, does that result
in MustAlias?

(Just to be clear, MayAlias is clearly a valid answer.  I'm really asking if
we can legally return MustAlias for these.)

I would have said up until recently, that the correct result would be a
PartialAlias, not a MustAlias.  However, we seem to be quite consistent about
returning MustAlias in cases where we know the base of the access is common, but
don't know the sizes are equal or even non-zero.

I can see four possible meanings of must alias:

  1.  A must alias result indicates that the exact same bits in memory are
accessed by both.  (This requires both pointer and size to be equal at runtime.)
  2.  A must alias result indicates that *at least one* bit in memory is
accessed by both.  (This allows unequal pointers, and unequal sizes, but not
zero sizes.)
  3.  A must alias result indicates that the two pointers must be equal when
accessed at runtime.  (This allows unequal sizes, and zero sizes, but restricts
the pointers to be equal.)
  4.  A must alias result indicates that *at least one* bit in memory is
accessed by both, unless one of the two accesses has size 0 at runtime.  (This
is the weakest.)

I'd always thought that (1) was the correct answer, but now I find myself
wondering.  From the code, (3) seems to be the closest match to what we actually
implement, but we're not entirely consistent there either.  What do others
think?

Philip


_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev




_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190213/c5967d1d/attachment.html>

A slight clarification to this and Chris's response just so that it
doesn't
cause confusion in the future (it isn't relevant to your example):

On Mon, Feb 11, 2019 at 1:15 PM Philip Reames via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> I can see four possible meanings of must alias:
>
>    1. A must alias result indicates that the exact same bits in memory
>    are accessed by both.  (This requires both pointer and size to be equal
at
>    runtime.)
>    2. A must alias result indicates that *at least one* bit in memory is
>    accessed by both.  (This allows unequal pointers, and unequal sizes, but
>    not zero sizes.)
>    3. A must alias result indicates that the two pointers must be equal
>    when accessed at runtime.  (This allows unequal sizes, and zero sizes,
but
>    restricts the pointers to be equal.)
>    4. A must alias result indicates that *at least one* bit in memory is
>    accessed by both, unless one of the two accesses has size 0 at runtime.
>    (This is the weakest.)
>
> I'd always thought that (1) was the correct answer, but now I find
myself
> wondering.  From the code, (3) seems to be the closest match to what we
> actually implement, but we're not entirely consistent there either. 
What
> do others think?
>
I agree that the intent is #3, but there is a gotcha IMO: the pointers need
not be the *same*, but merely equivalent for the purpose of loading and
storing to memory.

I don't believe that it would be correct to CSE the pointer values as I
understand the definition of aliasing. Aliasing is a property of the
underlying *memory* and not fundamentally of the pointer itself.

Perhaps this never comes up with MustAlias, but it absolutely comes up with
NoAlias where the pointers may in fact be equal bit patterns. I would find
it very confusing for them to be defined differently.

(And again, this obviously is not relevant to your example IR where they
are literally the same pointer as BasicAA resolves the query, precisely as
Chris said.)
-Chandler
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190218/edf205de/attachment.html>

> On Feb 18, 2019, at 7:02 PM, Chandler Carruth via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
> A slight clarification to this and Chris's response just so that it
doesn't cause confusion in the future (it isn't relevant to your
example):
> 
> On Mon, Feb 11, 2019 at 1:15 PM Philip Reames via llvm-dev <llvm-dev at
lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
> I can see four possible meanings of must alias:
> A must alias result indicates that the exact same bits in memory are
accessed by both.  (This requires both pointer and size to be equal at runtime.)
> A must alias result indicates that *at least one* bit in memory is accessed
by both.  (This allows unequal pointers, and unequal sizes, but not zero sizes.)
> A must alias result indicates that the two pointers must be equal when
accessed at runtime.  (This allows unequal sizes, and zero sizes, but restricts
the pointers to be equal.)
> A must alias result indicates that *at least one* bit in memory is accessed
by both, unless one of the two accesses has size 0 at runtime.  (This is the
weakest.)
> I'd always thought that (1) was the correct answer, but now I find
myself wondering.  From the code, (3) seems to be the closest match to what we
actually implement, but we're not entirely consistent there either.  What do
others think?
> 
> I agree that the intent is #3, but there is a gotcha IMO: the pointers need
not be the *same*, but merely equivalent for the purpose of loading and storing
to memory.
> 
> I don't believe that it would be correct to CSE the pointer values as I
understand the definition of aliasing. Aliasing is a property of the underlying
*memory* and not fundamentally of the pointer itself.
Absolutely right.  A “must alias” result isn’t enough to RAUW one pointer with
another.  They could have different LLVM types, they might not dominate each
other, etc.

-Chris


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20190219/48c3e4df/attachment.html>