[llvm-dev] TBAA for struct fields
Oliver Stannard via llvm-dev
llvm-dev at lists.llvm.org
Wed Mar 4 06:22:33 PST 2020
I think that's a limitation of LLVM's current implementation of TBAA - it
does not handle arrays inside structs, so must be conservative and return
may-alias.
Oliver
On Wed, 4 Mar 2020 at 09:52, Tiwary, Siddharth <Siddharth.Tiwary at amd.com>
wrote:
> [AMD Public Use]
>
>
>
> Hi Oliver,
>
>
>
> Thanks for the clarification, but please consider the following:
>
>
>
> For your point “TBAA doesn't have to consider overlap between different
> fields, because different fields are not allowed to overlap”. Basically,
> TBBA
>
> is aggressive in ignoring alias between different field types of a struct.
> Now, consider below:
>
>
>
> #######################################################
>
> struct P {
>
> float f1;
>
> float f2;
>
> float f3[3];
>
> float f4;
>
> };
>
>
>
> *void foo(struct P* p1, struct P* p2) {*
>
> * p1->f1 = 1.2;*
>
> * p2->f3[0] = 3.7;*
>
> *}*
>
>
>
> int callFoo() {
>
> struct P p;
>
> foo(&p, &p);
>
> return 0;
>
> }
>
> #######################################################
>
>
>
> Using the TBAA for the above program yields the alias-set for *foo*:
>
>
>
> *AliasSet[0x559a412391f0, 2] may alias, Mod Pointers: (float* %f1,
> LocationSize::precise(4)), (float* %arrayidx, LocationSize::precise(4))*
>
>
>
> that is, there exists a may-alias between f1 and f3[] fields between two
> pointers to same structure type.
>
>
>
> It is observed that when a struct-field(scalar-field) of type T and
> another struct-field(array) of type T[] are accessed, LLVM’s Type based
> Alias Analysis
>
> returns a may-alias. The field in the above context are f1 and
> f3[someIndx]. However, it does resolve aliasing between accesses to two
> scalar
>
> struct-fields (scalars of type T, say f1 and f4), provided there is no
> access to the same struct’s field which is an array of same type(of type
> T[] here, say f3).
>
>
>
> Note that f3 is a static array in struct P and hence non-re-assignable, so
> p1->f3[anyIndex] can never alias with p1->f1. But TBAA becomes conservative
> here.
>
>
>
> Upon inferring that the two stores are to two different field
> types(static-array and scalar), shouldn’t TBAA rule out the aliasing?
>
>
>
> Thanks,
>
> Siddharth
>
>
>
> *From:* Oliver Stannard <oliver.stannard at linaro.org>
> *Sent:* Tuesday, March 3, 2020 7:06 PM
> *To:* Tiwary, Siddharth <Siddharth.Tiwary at amd.com>
> *Cc:* llvm-dev at lists.llvm.org
> *Subject:* Re: [llvm-dev] TBAA for struct fields
>
>
>
> [CAUTION: External Email]
>
> > I get rid of the warnings by explicitly type-casting it to struct*, and
> still get similar results.
>
>
>
> Adding the explicit cast suppresses the warning, but the behaviour of the
> code is still undefined according to the C (and C++) standard.
>
>
>
> > Shouldn’t any alias analysis(including TBAA) be conservative in
> interprocedural context, and consider all aliasing possibilities between
> different fields?
>
>
>
> TBAA doesn't have to consider overlap between different fields, because
> different fields are not allowed to overlap.
>
>
>
> > *For Clang, O1 onwards results are wrong!*
>
>
>
> Since the behaviour of the source code is undefined, a compiler can
> generate any code it wants to, and be correct.
>
>
>
> If you really want to write code like this (though I'd strongly advise you
> not to, since it's not correct portable C), you can disable type-based
> alias analysis with the -fno-strict-aliasing clang option.
>
>
>
> Oliver
>
>
>
> On Tue, 3 Mar 2020 at 05:30, Tiwary, Siddharth <Siddharth.Tiwary at amd.com>
> wrote:
>
> [AMD Public Use]
>
>
>
> Hi Oliver,
>
>
>
> I get rid of the warnings by explicitly type-casting it to struct*, and
> still get similar results.
>
>
>
> #######################################################
>
> struct P {
>
> float f1;
>
> float f2;
>
> float f3[3];
>
> float f4;
>
> };
>
>
>
> void foo(struct P* p1, struct P* p2) {
>
> p1->f2 = 1.2;
>
> p2->f1 = 3.7;
>
> }
>
>
>
> int callFoo() {
>
> struct P p;
>
> foo(&p, (struct P*)(&(p.f2)));
>
> return 0;
>
> }
>
> #######################################################
>
>
>
> Shouldn’t any alias analysis(including TBAA) be conservative in
> interprocedural context, and consider all aliasing possibilities between
> different fields?
>
> As mentioned before, if instead of the above, p1->f2 and p2->f2 are the
> ones being accessed, then p1->f2 and p2->f2 are returned in same alias-sets.
>
> So, in second case, it is indeed conservative. This too is in
> interprocedural context!
>
>
>
> I ask this because as a result of the above, following happens:
>
>
>
> ##########################################
>
> struct P {
>
> float f1;
>
> float f2;
>
> float f3[3];
>
> float f4;
>
> };
>
>
>
> float foo(struct P* p1, struct P* p2) {
>
> float sum = 0;
>
> for( int i = 0; i < 1000; i++) {
>
> sum += p1->f2;
>
> p2->f1 += i*7;
>
> }
>
> return sum;
>
> }
>
>
>
> int callFoo() {
>
> struct P p;
>
> p.f1 = 3.0;
>
> p.f2 = 7.0;
>
> printf("foo = %f\n", foo(&p, (struct P*)&(p.f2)));
>
> return 0;
>
> }
>
>
>
> int main() {
>
> callFoo();
>
> return 0;
>
> }
>
>
>
> ###########################################
>
>
>
> Clang O0 and gcc O0/O1/O2 give the same expected result.
>
>
>
> *For Clang, O1 onwards results are wrong!* This is because the load and
> store get
>
> hoisted and sinked in the loop in foo, respectively. That happens even
> though
>
> load(p1->f2) and store(p2->f1) are same address, but LLVM doesn’t find it.
>
>
>
> Thanks,
>
> Siddharth
>
>
> ------------------------------
>
> *From:* Oliver Stannard <oliver.stannard at linaro.org>
> *Sent:* Friday, February 28, 2020 4:55 PM
> *To:* Tiwary, Siddharth <Siddharth.Tiwary at amd.com>
> *Cc:* llvm-dev at lists.llvm.org <llvm-dev at lists.llvm.org>
> *Subject:* Re: [llvm-dev] TBAA for struct fields
>
>
>
> [CAUTION: External Email]
>
> This is happening because there is undefined behaviour in your example. In
> C, a `struct P*` must point to the start of a `struct P`, so the compiler
> can assume references to two different members do not alias. In your
> example, you've constructed `p2` to point to the second member of the
> struct, which is not correct.
>
>
>
> Clang reports this as a warning:
>
>
>
> *######################################################*
>
> $ /work/llvm/build/bin/clang -fsyntax-only -c test.c
> test.c:15:11: warning: incompatible pointer types passing 'float *' to
> parameter of type 'struct P *' [-Wincompatible-pointer-types]
> foo(&p, &(p.f2));
> ^~~~~~~
> test.c:8:34: note: passing argument to parameter 'p2' here
> void foo(struct P *p1, struct P *p2) {
> ^
> test.c:16:1: warning: non-void function does not return a value
> [-Wreturn-type]
> }
> ^
> 2 warnings generated.
>
> *######################################################*
>
>
>
> Oliver
>
>
>
> On Fri, 28 Feb 2020 at 06:18, Tiwary, Siddharth via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
> [AMD Official Use Only - Internal Distribution Only]
>
>
>
> Hi,
>
>
>
> Following issue is observed with Type Based Alias Analysis(TBAA).
>
>
>
> #######################################################
>
> *struct P {*
>
> * float f1;*
>
> * float f2;*
>
> * float f3[3];*
>
> * float f4;*
>
> *};*
>
>
>
> *void foo(struct P* p1, struct P* p2) {*
>
> * p1->f2 = 1.2;*
>
> * p2->f1 = 3.7;*
>
> *}*
>
>
>
> *int callFoo() {*
>
> * struct P p;*
>
> * foo(&p, &(p.f2));*
>
> *}*
>
> *######################################################*
>
>
>
> Printing alias-sets using commands:
>
>
>
> * clang -O1 -S -emit-llvm struct_tbaa.c*
>
> * opt -basicaa -tbaa -print-alias-sets -disable-output struct_tbaa.ll*
>
>
>
> yields:
>
>
>
> *Alias sets for function 'foo':*
>
> *Alias Set Tracker: 2 alias sets for 2 pointer values.*
>
> * AliasSet[0x563d8f6a8bd0, 1] must alias, Mod Pointers: (i32* %f2,
> LocationSize::precise(4))*
>
> * AliasSet[0x563d8f6bc080, 1] must alias, Mod Pointers: (float*
> %f1, LocationSize::precise(4))*
>
>
>
> IR of foo:
>
>
>
> *; Function Attrs: nofree norecurse nounwind uwtable writeonly*
>
> *define dso_local void @foo(%struct.P* nocapture %p1, %struct.P* nocapture
> %p2) local_unnamed_addr #0 {*
>
> *entry:*
>
> * %f2 = getelementptr inbounds %struct.P, %struct.P* %p1, i64 0, i32 1*
>
> * store float 0x3FF3333340000000, float* %f2, align 4, !tbaa !2*
>
> * %f1 = getelementptr inbounds %struct.P, %struct.P* %p2, i64 0, i32 0*
>
> * store float 0x400D9999A0000000, float* %f1, align 4, !tbaa !7*
>
> * ret void*
>
> *}*
>
> *!2 = !{!3, !4, i64 4}*
>
> *!3 = !{!"P", !4, i64 0, !4, i64 4, !5, i64 8, !4, i64 20}*
>
> *!4 = !{!"float", !5, i64 0}*
>
> *!5 = !{!"omnipotent char", !6, i64 0}*
>
> *!6 = !{!"Simple C/C++ TBAA"}*
>
> *!7 = !{!3, !4, i64 0}*
>
>
>
> TBAA returns p1->f2 and p2->f1 in different alias-sets. But p1->f2 and
> p2->f1 do actually have the same address! Shouldn't the alias result be
> conservative while doing TBAA, especially when it needs interprocedural
> analysis?
>
> If instead of the above, p1->f2 and p2->f2 are the ones being accessed,
> then p1->f2 and p2->f2 are returned in same alias-sets. So, in second case,
> it is indeed conservative!
>
>
>
> Could someone please explain the rationale behind above behavior?
>
>
>
> Thanks,
>
> Siddharth
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> <https://nam11.safelinks.protection.outlook.com/?url=https%3A%2F%2Flists.llvm.org%2Fcgi-bin%2Fmailman%2Flistinfo%2Fllvm-dev&data=02%7C01%7CSiddharth.Tiwary%40amd.com%7Ccfa64e3992be42b6641508d7bf77e497%7C3dd8961fe4884e608e11a82d994e183d%7C0%7C0%7C637188393972992227&sdata=RULMER98bPM2w73vOtMGRl415KmyqE9oyfb6gnnEQkQ%3D&reserved=0>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200304/64942bc8/attachment.html>
More information about the llvm-dev
mailing list