<div dir="ltr">Hi Daniel,<div><br></div><div>I see your point about LLVM and C/C++ type agnostic. I think TBAA was invented to partially cover this gap and give optimization opportunities when LLVM types are not sufficient but C/C++ types have required information.</div><div><br></div><div>What do you think about following example:</div><div><div><div>struct S {</div><div> int a[10];</div><div> int b;</div><div>};</div><div><br></div><div>int foo(struct S *ps, int i) {</div><div> ps->a[i] = 1;</div><div> ps->b = 2;</div><div> return ps->a[0];</div><div>}</div></div></div><div><div><br></div><div>define i32 @foo(%struct.S* nocapture %ps, i32 %i) #0 {</div><div>entry:</div><div> %idxprom = sext i32 %i to i64</div><div> %arrayidx = getelementptr inbounds %struct.S, %struct.S* %ps, i64 0, i32 0, i64 %idxprom</div><div> store i32 1, i32* %arrayidx, align 4, !tbaa !1</div><div> %b = getelementptr inbounds %struct.S, %struct.S* %ps, i64 0, i32 1</div><div> store i32 2, i32* %b, align 4, !tbaa !5</div><div> %arrayidx2 = getelementptr inbounds %struct.S, %struct.S* %ps, i64 0, i32 0, i64 0</div><div> %0 = load i32, i32* %arrayidx2, align 4, !tbaa !1</div><div> ret i32 %0</div><div>}</div><div><br></div><div>!1 = !{!2, !2, i64 0}<br></div><div>!2 = !{!"int", !3, i64 0}</div><div>!3 = !{!"omnipotent char", !4, i64 0}</div><div>!4 = !{!"Simple C/C++ TBAA"}</div><div>!5 = !{!6, !2, i64 40}</div><div>!6 = !{!"S", !3, i64 0, !2, i64 40}</div></div><div><br></div><div>Missing information here is the range inside struct S that could be accessed. Also as you can see array member of struct in TBAA is presented as omnipotent char not as an array of int.</div><div><br></div><div>Arrays in struct in TBAA can be represented something like this:</div><div>!6 = !{!"S", !7, i64 0, !2, i64 40}<br></div><div><div>!7 = !{!"<unique id of int[10]>", !2, i64 0}</div></div><div><br></div><div>And 'ps->a[i]' could have TBAA like this:</div><div>!8 = !{!6, !7, i64 0}</div><div><br></div><div>As far as I can see if struct is enclosed in another struct, information about inner struct get lost only offset present. But I think for arrays it is better to keep array type in TBAA for the struct and element accesses.</div><div><br></div><div> Dmitry</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Dec 8, 2015 at 6:44 PM, Daniel Berlin <span dir="ltr"><<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Just remember that to LLVM, TBAA info doesn't tell it about types.<br><div><br></div><div>So when you say "<span style="font-size:12.8px"> </span><span style="font-size:12.8px">Differentiating array subscripts also seems like out of the scope of TBAA but adding type information that this memory assess accessing array not a random object of given type could be useful."</span></div><div><span style="font-size:12.8px"><br></span></div><div>Remember that LLVM has no notion of C/C++ types.</div><div><br></div><div>It doesn't know about them, it doesn't care about them.</div><div><br></div><div>What TBAA is telling it is that certain memory locations are disjoint.</div><div>It will *never* understand that what is being accessed is "a C++ struct containing an array of shorts", because the type system doesn't know what a "C struct" is, or a "C array" or a "C short".</div><div><br></div><div>Thus, while helpful, TBAA info in LLVM tells it *nothing* about the types, it only tells it that "if i am accessing this offset, it is disjoint with accessing this other offset".</div><div><br></div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Dec 8, 2015 at 3:38 AM, Dmitry Polukhin <span dir="ltr"><<a href="mailto:dmitry.polukhin@gmail.com" target="_blank">dmitry.polukhin@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Jeroen, thank you for very useful link with the context. Indeed union cases are very complicated and I see places in code when TBAA gives up.<br><div><br></div><div>Daniel, I completely agree that TBAA has limited power and can solve relatively simple cases only. So anything more complicated that involves intermediate variables that points to struct or array elements cannot be solved by TBAA alone. Differentiating array subscripts also seems like out of the scope of TBAA but adding type information that this memory assess accessing array not a random object of given type could be useful. Therefore TBAA can compliment points-to analysis and sometimes help in cases when points-to may not have enough information.</div></div><div><div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Dec 7, 2015 at 7:43 PM, Daniel Berlin <span dir="ltr"><<a href="mailto:dberlin@dberlin.org" target="_blank">dberlin@dberlin.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">TBAA is about types, not accesses.<div>TBAA "struct path data" is about access paths and types that are the end of access paths, for the most part.</div><div><br></div><div>It has no notion of access size, etc, only offset.</div><div><br></div><div>It is possible to extend it and handle *very basic* cases in the frontend (IE structs not containing unions anywhere, with constant accesses, etc)</div><div>But it would degrade quite quickly (you would likely need a sane way to say "this is an access to an unknown offset into this type")</div><div><br></div><div>Generally, rather than just try to produce metadata in the frontend, most compilers perform field-sensitive points-to or something similar for fields, and then rely on data dependence for differentiating array subscripts.</div><div><br></div><div>(This is what GCC does, LLVM has CFL-AA, but it's not field sensitive yet)</div><div><br></div><div>So handling .size vs .a[] is probably possible in the frontend.</div><div><br></div><div>Doing array subscript analysis in general, probably not something you want in the frontend.</div><div>Handling tricky cases of what pointers to structs point to, probably the domain of field-sensitive points-to </div></div><div><div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Dec 7, 2015 at 7:13 AM, Dmitry Polukhin via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">BTW, I have found why it doesn't work for arrays. TBAA information propagation is not implemented in CodeGenFunction::EmitArraySubscriptExpr with "TODO: Preserve/extend path TBAA metadata?".</div><div><div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Dec 4, 2015 at 1:38 PM, Dmitry Polukhin <span dir="ltr"><<a href="mailto:dmitry.polukhin@gmail.com" target="_blank">dmitry.polukhin@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">As far as I can see it is specifics of arrays inside structs. Current TBAA does distinguish non-array members with path sensitive TBAA (see !1 and !6 in my example below, TBAA has reference to struct !2 and offset). As for arrays information that it was member of some struct get lost completely (!7 has nothing about struct !2).<div><br></div><div><div>struct S {</div><div> int a;</div><div> int b;</div><div> int c[3];</div><div>};</div><div><br></div><div>void foo(struct S* p) {</div><div> p->a = 1;</div><div> p->b = 2;</div><div> p->c[0] = 3;</div><div> p->c[1] = 4;</div><div>}</div></div><div><br></div><div><div>define void @foo(%struct.S* nocapture %p) #0 {</div><div>entry:</div><div> %a = getelementptr inbounds %struct.S, %struct.S* %p, i64 0, i32 0</div><div> store i32 1, i32* %a, align 4, !tbaa !1</div><div> %b = getelementptr inbounds %struct.S, %struct.S* %p, i64 0, i32 1</div><div> store i32 2, i32* %b, align 4, !tbaa !6</div><div> %arrayidx = getelementptr inbounds %struct.S, %struct.S* %p, i64 0, i32 2, i64 0</div><div> store i32 3, i32* %arrayidx, align 4, !tbaa !7</div><div> %arrayidx2 = getelementptr inbounds %struct.S, %struct.S* %p, i64 0, i32 2, i64 1</div><div> store i32 4, i32* %arrayidx2, align 4, !tbaa !7</div><div> ret void</div><div>}</div><div><br></div><div>!0 = !{!"clang version 3.8.0 "}<br></div><div>!1 = !{!2, !3, i64 0}</div><div>!2 = !{!"S", !3, i64 0, !3, i64 4, !4, i64 8}</div><div>!3 = !{!"int", !4, i64 0}</div><div>!4 = !{!"omnipotent char", !5, i64 0}</div><div>!5 = !{!"Simple C/C++ TBAA"}</div><div>!6 = !{!2, !3, i64 4}</div><div>!7 = !{!3, !3, i64 0}</div></div><div><br></div><div>I'm just start learning how TBAA in clang works so I don't know why it was implemented this way.</div></div><div class="gmail_extra"><br><div class="gmail_quote"><div><div>On Fri, Dec 4, 2015 at 11:06 AM, Vaivaswatha Nagaraj via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span> wrote:<br></div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div><div dir="ltr"><div><div><div>Hi, <br><br></div>I'm trying to optimize a simple C code and came across a situation where invariant code is not being moved out:<br><br></div>On an -O3 compilation, I noticed that the "load" for the loop bounds (which remain invariant throughout) happens on each iteration of both the loops, even though it is not modified anywhere in the function "bigLoop". It seems that alias analysis is not able to say that the writes to one field in the structure does not impact the other field, leading to LICM being ineffective.<br><br></div>Do any of the alias analyses currently have some kind of field sensitivity that can help in this case?<br><div><div><div><div><div><br></div><div>------------------------- test case ------------------------------------<br></div><div>#include <stdlib.h><br>#include <stdio.h><br><br>#define SIZE 100<br><br>struct AS {<br> int a[SIZE+4];<br> int size;<br>} A;<br><br>void bigLoop(void)<br>{<br> unsigned i, j;<br><br> for (i = 0; i < A.size; i++) {<br> A.a[i+2] += A.a[i];<br> }<br> for (i = 0; i < A.size; i++) {<br> A.a[i+2] *= A.a[i];<br> }<br>}<br><br>int main()<br>{<br> A.size = random()%SIZE;<br> for (unsigned i = 0; i < A.size; i++) {<br> A.a[i] = random()%23;<br> }<br> bigLoop();<br> return 0;<br>}<br><br></div><div>Thanks,<br></div><div><br clear="all"><div><div><div dir="ltr"> - Vaivaswatha<br></div></div></div>
</div></div></div></div></div></div>
<br></div></div>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div><br></div>
</blockquote></div><br></div>
</div></div><br>_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
<br></blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>