[TBAA] Emit distinct TBAA tags for pointers with different depths,types.

[fhahn]

Summary

This patch extends Clang's TBAA generation code to emit distinct tags
for incompatible pointer types.

Pointers with different element types are incompatible if the pointee
types are also incompatible (modulo sugar/modifiers).

Express this in TBAA by generating different tags for pointers based
on the pointer depth and pointee type. To get the TBAA tag for the
pointee type it uses getTypeInfoHelper on the pointee type.

I'd appreciate a careful review, because this is probably quite easy to
get subtly wrong.

[rjmccall]

Hmm. We know that the big picture here, distinguishing pointers by pointee type, is going to be disruptive and will probably need a specific enabling/disabling option. I'm not sure that distinguishing only by pointer depth is a minor enough step that it shouldn't be treated the same way; in particular, it's going to start treating void * as incompatible with e.g. char **.

[efriedma]

I'm a little skeptical about making TBAA more aggressive. In most situations, we're probably talking about tiny performance gains, and currently there's no good way to check whether a codebase suffers from type punning issues (either with compile-time analysis or runtime instrumentation). Probably LLVM itself does, but we have no way of knowing.

[xbolva00]

Can you provide some flag?

Or -fstrict-aliasing controls this generation?

[fhahn]

In D122573#3412109, @rjmccall wrote:

Hmm. We know that the big picture here, distinguishing pointers by pointee type, is going to be disruptive and will probably need a specific enabling/disabling option. I'm not sure that distinguishing only by pointer depth is a minor enough step that it shouldn't be treated the same way; in particular, it's going to start treating void * as incompatible with e.g. char **.

@rjmccall do you have any suggestions how to further reduce the initial step?

In D122573#3413445, @xbolva00 wrote:

Can you provide some flag?

It should be controlled by the existing -fno-strict-aliasing flag, but there should probably be a dedicated flag as well to opt in the additional annotations.

In D122573#3412233, @efriedma wrote:

I'm a little skeptical about making TBAA more aggressive. In most situations, we're probably talking about tiny performance gains, and currently there's no good way to check whether a codebase suffers from type punning issues (either with compile-time analysis or runtime instrumentation). Probably LLVM itself does, but we have no way of knowing.

Agreed, strict aliasing violations are already a problem with the current level of TBAA support and we regularly see mis-compiles when new optimizations get enabled due to violations in projects. Improving precision of TBAA annotation is likely to expose more violations But there are cases where the additional guarantees could make a difference and other compiler implementations make use of them, so I think it would be worthwhile to work towards improving TBAA. I think we've also been through other disruptive transitions, like more aggressively adding mustprogress, but those were probably on a somewhat smaller scale.

Maybe we should try improve our tooling to detect violations in parallel to the effort in this patch? I am planning on trying to resurrect the type-sanitizer patches. I've also been playing around with a simple tool that's inserting assertions to check 2 pointers are not equal if TBAA claims they are no alias. The latter seems to surface a few violations in code in llvm-test-suite and also in tablegen. That is even without the current patch applied.

[xbolva00]

Maybe we should try improve our tooling to detect violations in parallel to the effort in this patch? I am planning on trying to resurrect the type-sanitizer patches. I've also been playing around with a simple tool that's inserting assertions to check 2 pointers are not equal if TBAA claims they are no alias. The latter seems to surface a few violations in code in llvm-test-suite and also in tablegen. That is even without the current patch applied.

Amazing!

Even your simple tool could be very useful, this functionality could be mapped to something like gcc’s -Wstrict-aliasing.

[efriedma]

Maybe we should try improve our tooling to detect violations in parallel to the effort in this patch? I am planning on trying to resurrect the type-sanitizer patches. I've also been playing around with a simple tool that's inserting assertions to check 2 pointers are not equal if TBAA claims they are no alias. The latter seems to surface a few violations in code in llvm-test-suite and also in tablegen. That is even without the current patch applied.

I'd be more comfortable if we had tooling, yes. The current state of "only a compiler expert can figure out if your code has undefined behavior" is the most scary part.

[rjmccall]

In D122573#3414357, @fhahn wrote:

In D122573#3412109, @rjmccall wrote:

Hmm. We know that the big picture here, distinguishing pointers by pointee type, is going to be disruptive and will probably need a specific enabling/disabling option. I'm not sure that distinguishing only by pointer depth is a minor enough step that it shouldn't be treated the same way; in particular, it's going to start treating void * as incompatible with e.g. char **.

@rjmccall do you have any suggestions how to further reduce the initial step?

Well, if you can find a solution to the void* <-> T** problem, that might make it tractable. Or you can introduce a flag to control whether we do this — I guess on some level -fstrict-aliasing ought to be the full language model, so this would mean introducing a -fless-strict-aliasing or something like it.

I agree that better tooling seems necessary.

[jcranmer-intel]

Apologies for the drive-by comment, but I happened to be searching for TBAA reviews after lamenting the current documentation and this popped up.

Agreed, strict aliasing violations are already a problem with the current level of TBAA support and we regularly see mis-compiles when new optimizations get enabled due to violations in projects. Improving precision of TBAA annotation is likely to expose more violations But there are cases where the additional guarantees could make a difference and other compiler implementations make use of them, so I think it would be worthwhile to work towards improving TBAA. I think we've also been through other disruptive transitions, like more aggressively adding mustprogress, but those were probably on a somewhat smaller scale.

Maybe we should try improve our tooling to detect violations in parallel to the effort in this patch? I am planning on trying to resurrect the type-sanitizer patches. I've also been playing around with a simple tool that's inserting assertions to check 2 pointers are not equal if TBAA claims they are no alias. The latter seems to surface a few violations in code in llvm-test-suite and also in tablegen. That is even without the current patch applied.

I think better tooling for TBAA in general is needed, although I'm not sure if this is a "in parallel" or "as a prerequisite step." One of the things I started doing myself is building a DOT output for TBAA metadata so that it's easier to understand the TBAA type tree without having to stare too hard at all of the metadata numbers. I don't want to derail this patch with too much discussion, but since it's slightly relevant here, one more comment:

clang/lib/CodeGen/CodeGenTBAA.cpp

200–203

Seeing this code reminds me that in a few other contexts, it would be useful to have access to the TBAA wrapper helpers in llvm/lib/Analysis/TypeBasedAliasAnalysis.cpp, so it would be worthwhile at some point to start fronting those types into header files to simplify some of the queries, especially in cases where you want to support both old and new TBAA formats. I'd imagine your tbaa-checker tool would also want access to this information as well, for example; I know the helper I started writing wanted it.

[rui.zhang]

Well, if you can find a solution to the void* <-> T** problem, that might make it tractable. Or you can introduce a flag to control whether we do this — I guess on some level -fstrict-aliasing ought to be the full language model, so this would mean introducing a -fless-strict-aliasing or something like it.

Is it helpful if we only track pointers to user defined types so that void * or char * is not in the picture?

[rui.zhang]

I like the direction where this change is leading to and hope there is some way to land it incrementally. Since BuiltinType has the above mentioned concern on void *, how about we focus on RecordType pointers as a first step instead? Are there any pitfalls if we distinguish RecordType pointers by depth?

[fhahn]

Rebased on current main

In D122573#3630767, @rui.zhang wrote:

I like the direction where this change is leading to and hope there is some way to land it incrementally. Since BuiltinType has the above mentioned concern on void *, how about we focus on RecordType pointers as a first step instead? Are there any pitfalls if we distinguish RecordType pointers by depth?

An initial restriction like that sounds reasonable to me. @jcranmer-intel @efriedma @rjmccall WDYT?

I also updated the type sanitizer patches and posted https://discourse.llvm.org/t/reviving-typesanitizer-a-sanitizer-to-catch-type-based-aliasing-violations/66092 to discuss ways to move forward with the sanitizer.

[rui.zhang]

In D122573#3872138, @fhahn wrote:

Rebased on current main

In D122573#3630767, @rui.zhang wrote:

I like the direction where this change is leading to and hope there is some way to land it incrementally. Since BuiltinType has the above mentioned concern on void *, how about we focus on RecordType pointers as a first step instead? Are there any pitfalls if we distinguish RecordType pointers by depth?

An initial restriction like that sounds reasonable to me. @jcranmer-intel @efriedma @rjmccall WDYT?

I also updated the type sanitizer patches and posted https://discourse.llvm.org/t/reviving-typesanitizer-a-sanitizer-to-catch-type-based-aliasing-violations/66092 to discuss ways to move forward with the sanitizer.

@craig.topper @mcberg2021 FYI

[bipmis]

@fhahn We are also observing scenarios where this maybe necessary. A couple of points on where it may be missing

1. createScalarTypeNode(OutName, AnyPtr, Size) -> This will generate different Base type. However the accessTy being "any pointer" , the check "access to the base object is through a field of the subobject's type" will return alias as we traverse from BaseTag Node until we reach Root or we find a SubobjectTag BaseType. In this case the match would be true on "any pointer". Can this be potentially be thought of as createScalarTypeNode(OutName, getChar(), Size) as a pointer type can edge to char?

2. The pointer type is restricted to isa<BuiltinType>(Ty). There can be potential scenarios where we may want pointer to struct or class.

I can provide some examples if that would be helpful. Thanks.

[xbolva00]

@fhahn do you plan to continue with this change?

[fhahn]

In D122573#4125641, @bipmis wrote:

@fhahn We are also observing scenarios where this maybe necessary. A couple of points on where it may be missing

1. createScalarTypeNode(OutName, AnyPtr, Size) -> This will generate different Base type. However the accessTy being "any pointer" , the check "access to the base object is through a field of the subobject's type" will return alias as we traverse from BaseTag Node until we reach Root or we find a SubobjectTag BaseType. In this case the match would be true on "any pointer". Can this be potentially be thought of as createScalarTypeNode(OutName, getChar(), Size) as a pointer type can edge to char?

2. The pointer type is restricted to isa<BuiltinType>(Ty). There can be potential scenarios where we may want pointer to struct or class.

I can provide some examples if that would be helpful. Thanks.

Please share examples if you can. The initial implementation is limited in scope intentionally and can be extended later. Staggering the change helps adopters with tracking down mis-compiles.

In D122573#4253837, @xbolva00 wrote:

@fhahn do you plan to continue with this change?

On my side yes, but it is still not clear what checkers need to be in place before strengthening TBAA.