<div dir="ltr">Hello! <div><br></div><div>Thank you very much! Yes, that makes a lot of sense to me. However, just want to point out two things that are still unclear:</div><div><br></div><div>1. The output contains a alias set of only one element, for instance: <br>"must alias, Mod Pointers: (i32* %y, LocationSize::precise(4))"</div><div><br></div><div>This one really confused me. I would expect to have an alias set of at least <b>two</b> elements (e.g., two pointers point to the same memory region), otherwise for the above case, $y$ is aliased to whom? I searched all outputs that are related to %y from <a href="https://llvm.godbolt.org/z/9njGqx" rel="noreferrer" target="_blank">https://llvm.godbolt.org/z/9njGqx</a> but all I can find is "NoAlias". Overall, to understand why an alias set can have only one pointer looks quite strange to me.. </div><div><br></div><div>2. For the following code chunks:</div><div><br></div><div> b = &c;<br> x = *a;<br> int y = *x;<br> MUSTALIAS(x,&c);<br> MUSTALIAS(x,b);<br></div><div><br></div><div>I don't get it why (quote from your previous email) "the desired inference of "x and b are "must alias"" cannot be correct--these are not the same objects in memory". x and b are both pointing to c, right? Am I missing anything here?<br></div><div><br></div><div>Sorry for the potential trouble this may have caused.. And thank you in advance! </div><div><br></div><div>Best,</div><div>Shuai</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Jul 9, 2020 at 9:58 PM Matt P. Dziubinski <<a href="mailto:matdzb@gmail.com">matdzb@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi again!<br>
<br>
Replying in chronological order:<br>
<br>
> On Thu, Jul 9, 2020 at 6:51 PM Shuai Wang <<a href="mailto:wangshuai901@gmail.com" target="_blank">wangshuai901@gmail.com</a> <br>
> <mailto:<a href="mailto:wangshuai901@gmail.com" target="_blank">wangshuai901@gmail.com</a>>> wrote:<br>
> <br>
> Hey Matt,<br>
> <br>
> That's awesome. Thank you very much for all the information and<br>
> clarification! Just a few follow up questions. Could you kindly shed<br>
> some lights on it? Thank you!<br>
> <br>
> 1. I tried to tweak the code in the following way: [...]<br>
> <br>
> I am trying to interpret the outputs, so if I understand correctly,<br>
> the output indicates that we have an alias set of 4 pointers which<br>
> "potentially" point to the same memory region, correct? Then is<br>
> there any more accurate analysis pass that I could use to somewhat<br>
> infer that "there are two must alias sets, each set has two<br>
> pointers"? Correct me if I was wrong here.. Using my local opt<br>
> (version 6.0), I tried to iterate all feasible alias analysis passes<br>
> but the results are not changed.<br>
<br>
Seems correct, I don't think you'll get more precise results out of the <br>
basic-aa pass, note that it has limited context sensitivity:<br>
<a href="https://llvm.org/docs/AliasAnalysis.html#the-basic-aa-pass" rel="noreferrer" target="_blank">https://llvm.org/docs/AliasAnalysis.html#the-basic-aa-pass</a><br>
<br>
Compare the results for `test_simple`, `test_in_array`, and <br>
`test_same_underlying_object_different_indices`:<br>
<a href="https://github.com/llvm/llvm-project/blob/release/10.x/llvm/test/Analysis/BasicAA/struct-geps.ll" rel="noreferrer" target="_blank">https://github.com/llvm/llvm-project/blob/release/10.x/llvm/test/Analysis/BasicAA/struct-geps.ll</a><br>
<br>
> Also, what is the "must alias, Mod/Ref forwarding to 0x563faa6c6260"?<br>
<br>
If alias sets have been merged, you'll get the attached node forwarding <br>
to the root node; note the comment for `getForwardedTarget` making a <br>
reference to union-find:<br>
<a href="https://github.com/llvm/llvm-project/blob/release/10.x/llvm/include/llvm/Analysis/AliasSetTracker.h#L281" rel="noreferrer" target="_blank">https://github.com/llvm/llvm-project/blob/release/10.x/llvm/include/llvm/Analysis/AliasSetTracker.h#L281</a><br>
(with "merge" corresponding to the union-find collapsing for "union", <br>
<a href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Union" rel="noreferrer" target="_blank">https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Union</a>).<br>
<br>
You can see how `AliasSet::mergeSetIn` (called, e.g., by <br>
`AliasSetTracker::mergeAliasSetsForPointer`) sets up forwarding for <br>
`AS.Forward`: <br>
<a href="https://github.com/llvm/llvm-project/blob/release/10.x/llvm/lib/Analysis/AliasSetTracker.cpp#L51" rel="noreferrer" target="_blank">https://github.com/llvm/llvm-project/blob/release/10.x/llvm/lib/Analysis/AliasSetTracker.cpp#L51</a>, <br>
<a href="https://github.com/llvm/llvm-project/blob/release/10.x/llvm/lib/Analysis/AliasSetTracker.cpp#L301" rel="noreferrer" target="_blank">https://github.com/llvm/llvm-project/blob/release/10.x/llvm/lib/Analysis/AliasSetTracker.cpp#L301</a><br>
FWIW, you can use a tracer or manually step through `opt` in a debugger <br>
to follow the function calls.<br>
<br>
> And how to interpret that we have "2 must alias responses"? Where<br>
> does it come from? And why do we have "0 may alias response"? I<br>
> would expect to have at least "4 may alias responses" as well?<br>
<br>
No, "MayAlias" and "MustAlias" are distinct elements in the lattice, cf.<br>
<a href="https://llvm.org/docs/AliasAnalysis.html#must-may-or-no" rel="noreferrer" target="_blank">https://llvm.org/docs/AliasAnalysis.html#must-may-or-no</a><br>
There's a good explanation of the alias analysis queries and responses <br>
in the following talk (particularly the part starting with "AA Query" <br>
around the 22 min. mark):<br>
“Pointers, Alias & ModRef Analyses” (2018 EuroLLVM Developers’ Meeting: <br>
A. Sbirlea & N. Lopes)<br>
<a href="https://www.youtube.com/watch?v=r0XVS4Atl3U" rel="noreferrer" target="_blank">https://www.youtube.com/watch?v=r0XVS4Atl3U</a><br>
<br>
When you return `AliasResult` from your analysis you choose one:<br>
<a href="https://llvm.org/doxygen/namespacellvm.html#ae1738272abcf2ac638b97e7dc6360cfd" rel="noreferrer" target="_blank">https://llvm.org/doxygen/namespacellvm.html#ae1738272abcf2ac638b97e7dc6360cfd</a><br>
<br>
You can see a simple example here (`TARAAResult::alias`): <br>
<a href="https://blog.tartanllama.xyz/llvm-alias-analysis/" rel="noreferrer" target="_blank">https://blog.tartanllama.xyz/llvm-alias-analysis/</a><br>
<br>
> 2. I note that using the latest opt (version 11.0?) gives different<br>
> outputs with my local opt (version 6.0). For opt (version 6.0), it<br>
> reports: 2 alias sets for 2 pointer values.<br>
> <br>
> More importantly, can I expect to get generally better alias<br>
> analysis results when switching to version 11.0?<br>
<br>
I'd assume that generally it shouldn't get worse :-)<br>
<br>
> <br>
> Thank you very much!<br>
<br>
On 7/9/2020 13:24, Shuai Wang wrote:<br>
> And another case:<br>
><br>
> - Clang [-> LLVM-IR]: <a href="https://llvm.godbolt.org/z/SGeJZw" rel="noreferrer" target="_blank">https://llvm.godbolt.org/z/SGeJZw</a><br>
> - [LLVM-IR ->] opt: <a href="https://llvm.godbolt.org/z/dNi-k2" rel="noreferrer" target="_blank">https://llvm.godbolt.org/z/dNi-k2</a><br>
><br>
> Is there any chance that we can smoothly infer that:<br>
> - x and &c are "must alias"<br>
> - x and b are "must alias"<br>
><br>
> I don't know how to interpret the current results, in particular the<br>
> following outputs:<br>
><br>
> AliasSet[0x5584ab7e5f30, 1] must alias, Mod/Ref Pointers: (i32** %x,<br>
> LocationSize::precise(8))<br>
> AliasSet[0x5584ab7e6020, 1] must alias, Mod Pointers: (i32* %y,<br>
> LocationSize::precise(4))<br>
><br>
> It means we have two "must alias" sets, each of which contain only one<br>
> pointer? That seems quite confusing to me..<br>
<br>
You can add -print-all-alias-modref-info for more detailed information: <br>
<a href="https://llvm.godbolt.org/z/9njGqx" rel="noreferrer" target="_blank">https://llvm.godbolt.org/z/9njGqx</a> -- you'll notice "MustAlias: i32* %c, <br>
i8* %6".<br>
<br>
Adding `-evaluate-aa-metadata` for `load` and `store` instructions, <br>
<a href="https://llvm.godbolt.org/z/YaW1Mb" rel="noreferrer" target="_blank">https://llvm.godbolt.org/z/YaW1Mb</a>, you'll notice "MustAlias: %0 = load <br>
i32**, i32*** %a, align 8 <-> store i32** %b, i32*** %a, align 8"<br>
<br>
However, from your results we can already note:<br>
<br>
AliasSet[0x5584ab7e5d00, 5] may alias, Mod/Ref Pointers: (i32* %c, <br>
LocationSize::precise(4)), (i32** %b, LocationSize::precise(8)), (i32** <br>
%0, LocationSize::precise(8)), (i32* %2, LocationSize::precise(4))<br>
<br>
Note how in the C source code pointer `b` points to int `c` (`b = &c;`) <br>
corresponding to the memory locations (same object in memory when <br>
loading from `c` or `*b`). However, pointers `x` and `y` are distinct <br>
objects in memory themselves. In general, remember not to confuse <br>
pointers with what they point to--here also distinct, since `x` points <br>
`b` but `y` points to `c` (I mention this specifically since the desired <br>
inference of "x and b are "must alias"" cannot be correct--these are not <br>
the same objects in memory).<br>
<br>
Best,<br>
Matt<br>
<br>
</blockquote></div>