[llvm-dev] TBAA for struct fields

Tiwary, Siddharth via llvm-dev llvm-dev at lists.llvm.org
Wed Mar 4 01:52:46 PST 2020


[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<mailto: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<mailto:oliver.stannard at linaro.org>>
Sent: Friday, February 28, 2020 4:55 PM
To: Tiwary, Siddharth <Siddharth.Tiwary at amd.com<mailto:Siddharth.Tiwary at amd.com>>
Cc: llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org> <llvm-dev at lists.llvm.org<mailto: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<mailto: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<mailto: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/3cf98aa1/attachment.html>


More information about the llvm-dev mailing list