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

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

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

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

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