wrong results with union and strict-aliasing

[brunodefraine]

Bugzilla Link	21725
Version	3.4
OS	Linux
CC	@aelovikov-intel,@compnerd,@hfinkel,@kosarev,@dobbelaj-snps,@sunfishcode,@RalfJung,@regehr,@zygoloid,@sanjoy,@seanm

Extended Description

The following testcase produces wrong results with '-O1' and higher (tested with llvm-3.4 and llvm-3.5).

#include <stdio.h>

union U {
	short s;
	int i;
} u;

int v = 987;
union U* up = &u;

int main()
{
	for (int i = 0; i < 2; ++i) {
		u.s = v;         // 987
		up->i = 123;     // 123
	}
	printf("%d\n", up->i);   // 123     clang: 123
	printf("%d\n", u.i);     // 123     clang: 987 ******
	printf("%d\n", up->i);   // 123     clang: 987 ******
	printf("%d\n", u.i);     // 123     clang: 987 ******
	return 0;
}

Disabling 'strict-aliasing' makes the problem go away.
We do believe that the behavior should be the same with and without strict-aliasing.

It seems that initially, the write to 'u.s' is moved out of the loop.
(more exactly, after the loop)
Later on the loop is removed, with only the write to 'up->i' remaining.
As the store to 'u.s' is still following, the end result is not what we expect to see.

[zygoloid]

Surprisingly, this is a question about union aliasing on which the C standard is actually clear. C's effective type rules say that this program is valid and is required to print 123 four times (and more generally you can't reorder a store past a store with a different type unless you can prove that one of the stores is to an object with a fixed effective type[1] or that the stores refer to disjoint storage).

There's a separate question of whether we should follow what C says here (or come up with some saner rules), but I think whatever we do, the attached testcase should behave as intended.

[1] You get a fixed effective type if the object was created by a declaration rather than by (say) malloc.

[hfinkel]

It seems as though the way of handling this, to adhere to the standard, is only to use TBAA for (read <-> write) aliasing queries, not (write <-> write) queries, because for (write <-> write) queries, the writes could be changing the effective type of the underlying storage.

This would not apply to objects with fixed effective type. Perhaps for such objects, we could tag the alloca or global with the TBAA metadata directly? Then if we had a (write <-> write) query, and we could see that the underlying objects had fixed effective type, we could continue to use TBAA to answer the AA query.

[llvmbot]

So,

1. I agree this is completely valid and should print 123 4 times
2. (I can debug it myself, but figure i'd ask if someone has looked)

Is this failing due to the struct path queries, or just the regular low level TBAA queries.

I can see how the former would happen, i have trouble seeing how the latter happens.

[llvmbot]

As a side note,

Looking at the output, the TBAA tree from clang and how it gets used is very different than what gcc does. I'm pretty sure what clang produces is wrong.

GCC produces a TBAA tree for the union type, and makes int and short descendents.

IE

 union
  /   \
 /     \
int    short

clang produces a tree that has an anonymous type for the union.
But it never has int and short as descendents

This is true even if you try to force it by making a union copy in main.
( by doing

  union U f;
     f = u;

)

Instead, the tree clang gives is:

        char
 /       |      \
union   int      short

This is, IMHO, clearly wrong for the union.

int and short should be descendants of the union

That way, any access to int is considered a possible read/write to the union (which is right), and any access to the union is considered a possible read/write to the int.

I do not know if this is causing this bug, but it seems very wrong to me.

(maybe someone smarter can explain what i'm missing here :P)

[dobbelaj-snps]

*** Bug #12338 has been marked as a duplicate of this bug. ***

[dobbelaj-snps]

Proposed fix
This patch enables 'tbaa path' for union member access at the clang side. It resolves the described issue, without triggering testcase regressions.

Does this look good ? Or is there a path in the core llvm where these changes will have unexpected effects ?
If this is the way forward, I can create a unittest to track this behavior.
(similar to clang/test/CodeGen/tbaa-struct.cpp)

[llvmbot]

Created attachment 13970 [details]
Proposed fix

This patch enables 'tbaa path' for union member access at the clang side. It
resolves the described issue, without triggering testcase regressions.

Does this look good ? Or is there a path in the core llvm where these
changes will have unexpected effects ?
If this is the way forward, I can create a unittest to track this behavior.
(similar to clang/test/CodeGen/tbaa-struct.cpp)

Can you paste what metadata looks like with this patch?

[dobbelaj-snps]

Output for 'clang -g -O1 --emit-llvm'. Without the change

[dobbelaj-snps]

Output for 'clang -g -O1 --emit-llvm'. With the change
The main difference is that we now (with the patch) have a member access (to !39):

!37 = !{!"int", !32, i64 0}
!39 = !{#40, !41, i64 0}
!40 = !{!"U", !41, i64 0, !37, i64 0}
!41 = !{!"short", !32, i64 0}


in stead of basic type access (to !41) that we had before (without the patch):
!41 = !{#42, !42, i64 0}
!42 = !{!"short", !32, i64 0}

[llvmbot]

So the after metadata looks correct after, so i'm on board with this.

I think it's the right path.

I don't know if there are other bugs lurking that caused this disablement in the first place though.

(I also think Chris is correct in the bug that was duped to this one. There is nothing you can do in the general case, because you can always play games with where the union occurs. But this will at least get us "as right as other compilers generally are" :P)

[hfinkel]

Sounds good. Jeroen, can you make a patch with a test case (or just add it to test/CodeGen/tbaa-struct.cpp) and send it to the cfe-commits list for review?

[hfinkel]

Sounds good. Jeroen, can you make a patch with a test case (or just add it
to test/CodeGen/tbaa-struct.cpp) and send it to the cfe-commits list for
review?

This was posted to https://reviews.llvm.org/D8056 but then abandoned because of other bugs uncovered. Please see this thread for more information: http://lists.llvm.org/pipermail/cfe-dev/2015-March/042015.html

[hfinkel]

Sounds good. Jeroen, can you make a patch with a test case (or just add it
to test/CodeGen/tbaa-struct.cpp) and send it to the cfe-commits list for
review?

This was posted to https://reviews.llvm.org/D8056 but then abandoned because of other bugs uncovered. Please see this thread for more information: http://lists.llvm.org/pipermail/cfe-dev/2015-March/042015.html

[llvmbot]

The original testcase seems to be fixed now but replacing the union by allocated memory makes the problem come back.

Source code:

#include <stdlib.h>
#include <stdio.h>

int v = 987;

void test(short *ps, int *pi, int *pi2)
{
  for (int i = 0; i < 2; ++i) {
    *ps = v;
    *pi = 123;
  }
  printf("%d\n", *pi);
  printf("%d\n", *pi2);
  printf("%d\n", *pi);
  printf("%d\n", *pi2);
}

int main()
{
  void *p = malloc(10);

  test(p, p, p);
}

Results:

$ clang -std=c11 -Wall -O3 test.c && ./a.out
123
987
987
987

clang version: clang version 6.0.0 (https://llvm.org/git/clang.git f027325999d75572cbdb4dda2e475bd27bcc74da) (https://llvm.org/git/llvm.git f7bb38c)

[kosarev]

It's not really fixed, just "pessimized" accesses to union members. See

https://reviews.llvm.org/D33328

for more details. I would suggest that we do not close any bug reports of this kind until we have a proper solution.

As your modified example, it seems there is no practical way for TBAA to support such cases. If we permit accesses of different types to alias, then there is no work to do for TBAA.