<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Dec 9, 2015 at 2:33 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:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><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></div></blockquote><div><br></div><div>I'm not entirely sure why TBAA is necessary to disambiguate ps->a from ps->b, it looks like basicaa should already be able to say they don't overlap.</div><div>Does this not happen?<br><br></div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><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. </div></div></blockquote><div><br></div><div>What do you mean by "could be accessed".  Do you mean "valid to access in C"?</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div>Also as you can see array member of struct in TBAA is presented as omnipotent char not as an array of int.</div></div></blockquote><div><br></div><div>Agreed.</div><div> </div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div></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></blockquote><div><br></div><div><br></div><div>Yes. This should likely work. Note that size, while nice, is harder.</div><div><br></div><div>One thing that is sadly still common (at least in C) is to do this:<br><br></div><div><div>struct S {</div><div>  int b;<br></div><div>  int a[0]; // or 1</div><div>};</div></div><div><br></div><div>and malloc it at (sizeof S + 40 * sizeof (int)), then write into a[1...39].</div><div><br></div><div><br></div><div>If we want to break that, it is likely a lot of stuff gets broken (at one point when we did it in gcc, we broke 80% of all the packages in a given linux distro ....)</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><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></blockquote><div><br></div><div>Don't get me wrong, i think that it would be nice to have offset and size, and gcc does indeed track this info on it's own.</div><div><br></div><div>I'm just trying to understand where you think it will provide better info.</div><div><br></div><div>Because once you get into cases like:<br><br></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>  *i = 3;</div><div>  return ps->b;<br></div><div>}</div></div><div><br></div><div><br></div><div>You have no guarantee, for example, that *i and *(ps->b) are not the same memory.</div><div><br></div><div></div></div></div></div></div>