[llvm-dev] Understand alias-analysis results

Thu Jul 9 06:58:24 PDT 2020

Hi again!

Replying in chronological order:

> On Thu, Jul 9, 2020 at 6:51 PM Shuai Wang <wangshuai901 at gmail.com 
> <mailto:wangshuai901 at gmail.com>> wrote:
> 
>     Hey Matt,
> 
>     That's awesome. Thank you very much for all the information and
>     clarification! Just a few follow up questions. Could you kindly shed
>     some lights on it? Thank you!
> 
>     1. I tried to tweak the code in the following way: [...]
> 
>     I am trying to interpret the outputs, so if I understand correctly,
>     the output indicates that we have an alias set of 4 pointers which
>     "potentially" point to the same memory region, correct? Then is
>     there any more accurate analysis pass that I could use to somewhat
>     infer that "there are two must alias sets, each set has two
>     pointers"? Correct me if I was wrong here.. Using my local opt
>     (version 6.0), I tried to iterate all feasible alias analysis passes
>     but the results are not changed.

Seems correct, I don't think you'll get more precise results out of the 
basic-aa pass, note that it has limited context sensitivity:
https://llvm.org/docs/AliasAnalysis.html#the-basic-aa-pass

Compare the results for `test_simple`, `test_in_array`, and 
`test_same_underlying_object_different_indices`:
https://github.com/llvm/llvm-project/blob/release/10.x/llvm/test/Analysis/BasicAA/struct-geps.ll

>     Also, what is the "must alias, Mod/Ref forwarding to 0x563faa6c6260"?

If alias sets have been merged, you'll get the attached node forwarding 
to the root node; note the comment for `getForwardedTarget` making a 
reference to union-find:
https://github.com/llvm/llvm-project/blob/release/10.x/llvm/include/llvm/Analysis/AliasSetTracker.h#L281
(with "merge" corresponding to the union-find collapsing for "union", 
https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Union).

You can see how `AliasSet::mergeSetIn` (called, e.g., by 
`AliasSetTracker::mergeAliasSetsForPointer`) sets up forwarding for 
`AS.Forward`: 
https://github.com/llvm/llvm-project/blob/release/10.x/llvm/lib/Analysis/AliasSetTracker.cpp#L51, 
https://github.com/llvm/llvm-project/blob/release/10.x/llvm/lib/Analysis/AliasSetTracker.cpp#L301
FWIW, you can use a tracer or manually step through `opt` in a debugger 
to follow the function calls.

>     And how to interpret that we have "2 must alias responses"? Where
>     does it come from? And why do we have "0 may alias response"? I
>     would expect to have at least "4 may alias responses" as well?

No, "MayAlias" and "MustAlias" are distinct elements in the lattice, cf.
https://llvm.org/docs/AliasAnalysis.html#must-may-or-no
There's a good explanation of the alias analysis queries and responses 
in the following talk (particularly the part starting with "AA Query" 
around the 22 min. mark):
“Pointers, Alias & ModRef Analyses” (2018 EuroLLVM Developers’ Meeting: 
A. Sbirlea & N. Lopes)
https://www.youtube.com/watch?v=r0XVS4Atl3U

When you return `AliasResult` from your analysis you choose one:
https://llvm.org/doxygen/namespacellvm.html#ae1738272abcf2ac638b97e7dc6360cfd

You can see a simple example here (`TARAAResult::alias`): 
https://blog.tartanllama.xyz/llvm-alias-analysis/

>     2. I note that using the latest opt (version 11.0?) gives different
>     outputs with my local opt (version 6.0). For opt (version 6.0), it
>     reports: 2 alias sets for 2 pointer values.
> 
>     More importantly, can I expect to get generally better alias
>     analysis results when switching to version 11.0?

I'd assume that generally it shouldn't get worse :-)

> 
>     Thank you very much!

On 7/9/2020 13:24, Shuai Wang wrote:
 > And another case:
 >
 > - Clang [-> LLVM-IR]: https://llvm.godbolt.org/z/SGeJZw
 > - [LLVM-IR ->] opt: https://llvm.godbolt.org/z/dNi-k2
 >
 > Is there any chance that we can smoothly infer that:
 > - x and &c are "must alias"
 > - x and b are "must alias"
 >
 > I don't know how to interpret the current results, in particular the
 > following outputs:
 >
 > AliasSet[0x5584ab7e5f30, 1] must alias, Mod/Ref   Pointers: (i32** %x,
 > LocationSize::precise(8))
 > AliasSet[0x5584ab7e6020, 1] must alias, Mod       Pointers: (i32* %y,
 > LocationSize::precise(4))
 >
 > It means we have two "must alias" sets, each of which contain only one
 > pointer? That seems quite confusing to me..

You can add -print-all-alias-modref-info for more detailed information: 
https://llvm.godbolt.org/z/9njGqx -- you'll notice "MustAlias:	i32* %c, 
i8* %6".

Adding `-evaluate-aa-metadata` for `load` and `store` instructions, 
https://llvm.godbolt.org/z/YaW1Mb, you'll notice "MustAlias:   %0 = load 
i32**, i32*** %a, align 8 <->   store i32** %b, i32*** %a, align 8"

However, from your results we can already note:

AliasSet[0x5584ab7e5d00, 5] may alias, Mod/Ref   Pointers: (i32* %c, 
LocationSize::precise(4)), (i32** %b, LocationSize::precise(8)), (i32** 
%0, LocationSize::precise(8)), (i32* %2, LocationSize::precise(4))

Note how in the C source code pointer `b` points to int `c` (`b = &c;`) 
corresponding to the memory locations (same object in memory when 
loading from `c` or `*b`). However, pointers `x` and `y` are distinct 
objects in memory themselves. In general, remember not to confuse 
pointers with what they point to--here also distinct, since `x` points 
`b` but `y` points to `c` (I mention this specifically since the desired 
inference of "x and b are "must alias"" cannot be correct--these are not 
the same objects in memory).

Best,
Matt