<div dir="ltr"><div dir="ltr">Dear Matt,<div><br></div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Jul 10, 2020 at 4:43 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!<br>
<br>
On 7/10/2020 07:17, Shuai Wang wrote:<br>
> Hello!<br>
> <br>
> Thank you very much! Yes, that makes a lot of sense to me. However, just <br>
> want to point out two things that are still unclear:<br>
> <br>
> 1. The output contains a alias set of only one element, for instance:<br>
> "must alias, Mod Pointers: (i32* %y, LocationSize::precise(4))"<br>
> <br>
> This one really confused me. I would expect to have an alias set of at <br>
> least *two* elements (e.g., two pointers point to the same memory <br>
> region), otherwise for the above case, $y$ is aliased to whom? I <br>
> searched all outputs that are related to %y from <br>
> <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". <br>
> Overall, to understand why an alias set can have only one pointer looks <br>
> quite strange to me..<br>
<br>
This seems correct: Note that `int y` is a distinct object in memory, <br>
not a pointer, and shares no alias sets with anything (we happen to <br>
assign the int _value_ we obtain from pointer `x` by dereferencing it <br>
`*x`, but that bears no relevance to aliasing here). Perhaps this can <br>
help illustrate the scenario (assuming the URL doesn't get mangled):<br>
<a href="http://www.pythontutor.com/cpp.html#code=void%20MUSTALIAS%28void%20*p,%20void%20*q%29%20%7B%7D%0A%0Aint%20main%28%29%7B%0A%0A%20%20int%20**a,%20*b,%20*x%20,c%3B%0A%20%20c%20%3D%2010%3B%0A%20%20a%20%3D%20%26b%3B%0A%20%20b%20%3D%20%26c%3B%0A%20%20x%20%3D%20*a%3B%0A%20%20int%20y%20%3D%20*x%3B%0A%20%20MUSTALIAS%28x,%26c%29%3B%0A%20%20MUSTALIAS%28x,b%29%3B%0A%20%20return%200%3B%0A%7D&curInstr=12&mode=display&origin=opt-frontend.js&py=cpp&rawInputLstJSON=%5B%5D" rel="noreferrer" target="_blank">http://www.pythontutor.com/cpp.html#code=void%20MUSTALIAS%28void%20*p,%20void%20*q%29%20%7B%7D%0A%0Aint%20main%28%29%7B%0A%0A%20%20int%20**a,%20*b,%20*x%20,c%3B%0A%20%20c%20%3D%2010%3B%0A%20%20a%20%3D%20%26b%3B%0A%20%20b%20%3D%20%26c%3B%0A%20%20x%20%3D%20*a%3B%0A%20%20int%20y%20%3D%20*x%3B%0A%20%20MUSTALIAS%28x,%26c%29%3B%0A%20%20MUSTALIAS%28x,b%29%3B%0A%20%20return%200%3B%0A%7D&curInstr=12&mode=display&origin=opt-frontend.js&py=cpp&rawInputLstJSON=%5B%5D</a><br>
<br>
Note (in step 13 of 13) how `y` does not alias (it is just an `int` <br>
itself) anything (agreeing with NoAlias results you're getting).<br>
<br></blockquote><div><br></div><div>Yes, I think I fully understand that 'y' is not a pointer. However, again, what confuses me and seems incorrect is the output of LLVM alias analysis:</div><div><br></div><div>"<b>must alias, Mod</b> Pointers: (i32* %y, LocationSize::precise(4))"<br></div><div><br></div><div>Isn't it literally indicating that "i32* y", denoting a pointer, is <b>must alias</b> with some other pointers? </div><div><br></div><div>If so, then why does this set only have one pointer instead of at least two? If not (which makes more sense), then why is "i32* %y" reported and annotated as "<b>must alias, mod</b>"? Both ways do not make sense to me. </div><div><br></div><div>Best,</div><div>Shuai</div><div><br></div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
> <br>
> 2. For the following code chunks:<br>
> <br>
> b = &c;<br>
> x = *a;<br>
> int y = *x;<br>
> MUSTALIAS(x,&c);<br>
> MUSTALIAS(x,b);<br>
> <br>
> I don't get it why (quote from your previous email) "the desired <br>
> inference of "x and b are "must alias"" cannot be correct--these are not <br>
> the same objects in memory". x and b are both pointing to c, right? Am I <br>
> missing anything here?<br>
<br>
Correct, both `x` and `b` point to `c` (the pointers themselves are <br>
distinct, but after dereferencing what they point to is the same location).<br>
Consider the slice on the (first call) to `MUSTALIAS(x, &c);`: <br>
<a href="https://llvm.godbolt.org/z/YaW1Mb" rel="noreferrer" target="_blank">https://llvm.godbolt.org/z/YaW1Mb</a><br>
<br>
%a = alloca i32**, align 8<br>
%b = alloca i32*, align 8<br>
%x = alloca i32*, align 8<br>
%c = alloca i32, align 4<br>
. . .<br>
%0 = load i32**, i32*** %a, align 8<br>
%1 = load i32*, i32** %0, align 8<br>
. . .<br>
%4 = load i32*, i32** %x, align 8<br>
%5 = bitcast i32* %4 to i8*<br>
%6 = bitcast i32* %c to i8*<br>
; MUSTALIAS(x, &c);<br>
call void @MUSTALIAS(i8* %5, i8* %6)<br>
<br>
Notice the following results:<br>
NoAlias: i32* %4, i32** %x<br>
MayAlias: i32* %4, i32* %c<br>
MustAlias: i32* %4, i8* %5<br>
MayAlias: i32* %4, i8* %6<br>
. . .<br>
MayAlias: i32** %b, i8* %5<br>
NoAlias: i32** %x, i8* %5<br>
MayAlias: i32* %c, i8* %5<br>
MayAlias: i8* %5, i8* %6<br>
MustAlias: i32* %c, i8* %6<br>
. . .<br>
MustAlias: %4 = load i32*, i32** %x, align 8 <-> store i32* %1, <br>
i32** %x, align 8<br>
<br>
The location in memory of a pointer object `b` may alias location of the <br>
first argument `%5` but not the (other memory object) pointer `x`; <br>
however, `i32* %c` aliases second argument `i8* %6` (the same memory <br>
object) as well as may alias `i8* %5` (which we've obtained from loading <br>
the address from pointer `x`; the difference here being between the <br>
memory locations storing the pointers themselves, say, on the stack--not <br>
aliased, and the memory objects the addresses stored in the pointers <br>
refer to, i.e., i32** vs. i32* or i8*).<br>
<br>
Best,<br>
Matt<br>
<br>
> <br>
> Sorry for the potential trouble this may have caused.. And thank you <br>
> in advance!<br>
> <br>
> Best,<br>
> Shuai<br>
> <br>
> On Thu, Jul 9, 2020 at 9:58 PM Matt P. Dziubinski <<a href="mailto:matdzb@gmail.com" target="_blank">matdzb@gmail.com</a> <br>
> <mailto:<a href="mailto:matdzb@gmail.com" target="_blank">matdzb@gmail.com</a>>> wrote:<br>
> <br>
> 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>><br>
> > <mailto:<a href="mailto:wangshuai901@gmail.com" target="_blank">wangshuai901@gmail.com</a> <mailto:<a href="mailto:wangshuai901@gmail.com" target="_blank">wangshuai901@gmail.com</a>>>><br>
> 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<br>
> 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<br>
> correctly,<br>
> > the output indicates that we have an alias set of 4 pointers<br>
> which<br>
> > "potentially" point to the same memory region, correct? Then is<br>
> > there any more accurate analysis pass that I could use to<br>
> 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<br>
> 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<br>
> 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>
> <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<br>
> different<br>
> > outputs with my local opt (version 6.0). For opt (version<br>
> 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:<br>
> (i32** %x,<br>
> > LocationSize::precise(8))<br>
> > AliasSet[0x5584ab7e6020, 1] must alias, Mod Pointers:<br>
> (i32* %y,<br>
> > LocationSize::precise(4))<br>
> ><br>
> > It means we have two "must alias" sets, each of which contain<br>
> 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*<br>
> %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 =<br>
> 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<br>
> desired<br>
> inference of "x and b are "must alias"" cannot be correct--these are<br>
> not<br>
> the same objects in memory).<br>
> <br>
> Best,<br>
> Matt<br>
> <br>
</blockquote></div></div>