Page MenuHomePhabricator

[LangRef] tbaa: type names can be used as hints to optimizations
AbandonedPublic

Authored by aqjune on Apr 23 2021, 10:33 AM.

Details

Summary

As discussed in D100717, this patch states that if TBAA metadata node's type name is e.g.,
any pointer or vtable pointer, it can be used as a hint to drive further optimizations/passes.

Diff Detail

Unit TestsFailed

TimeTest
2,170 msx64 debian > libarcher.races::lock-unrelated.c
Script: -- : 'RUN: at line 13'; /mnt/disks/ssd0/agent/llvm-project/build/./bin/clang -fopenmp -pthread -fno-experimental-isel -g -O1 -fsanitize=thread -I /mnt/disks/ssd0/agent/llvm-project/openmp/tools/archer/tests -I /mnt/disks/ssd0/agent/llvm-project/build/projects/openmp/runtime/src -L /mnt/disks/ssd0/agent/llvm-project/build/lib -Wl,-rpath,/mnt/disks/ssd0/agent/llvm-project/build/lib /mnt/disks/ssd0/agent/llvm-project/openmp/tools/archer/tests/races/lock-unrelated.c -o /mnt/disks/ssd0/agent/llvm-project/build/projects/openmp/tools/archer/tests/races/Output/lock-unrelated.c.tmp -latomic && env TSAN_OPTIONS='ignore_noninstrumented_modules=0:ignore_noninstrumented_modules=1' /mnt/disks/ssd0/agent/llvm-project/openmp/tools/archer/tests/deflake.bash /mnt/disks/ssd0/agent/llvm-project/build/projects/openmp/tools/archer/tests/races/Output/lock-unrelated.c.tmp 2>&1 | tee /mnt/disks/ssd0/agent/llvm-project/build/projects/openmp/tools/archer/tests/races/Output/lock-unrelated.c.tmp.log | /mnt/disks/ssd0/agent/llvm-project/build/./bin/FileCheck /mnt/disks/ssd0/agent/llvm-project/openmp/tools/archer/tests/races/lock-unrelated.c

Event Timeline

aqjune created this revision.Apr 23 2021, 10:33 AM
aqjune requested review of this revision.Apr 23 2021, 10:33 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 23 2021, 10:33 AM
aqjune added inline comments.Apr 23 2021, 10:41 AM
llvm/docs/LangRef.rst
5794

This sentence ('LLVM does not assign ... an `MDString`') became a separate paragraph (line 5807) and the explanation is added.
Similarly for the analogous sentence in the next paragraph as well.

jdoerfert added inline comments.Apr 23 2021, 10:42 AM
llvm/docs/LangRef.rst
5807–5810

I think we should make it open ended right away, and stress that it is for heuristics, not correctness.

aqjune updated this revision to Diff 340110.Apr 23 2021, 10:51 AM

Address jdoerfert's comment

aqjune marked an inline comment as done.Apr 23 2021, 10:52 AM

As suggested in D100717, I'll send a mail to llvm-dev for visibility.

aqjune retitled this revision from [LangRef] tbaa: 'any pointer' and 'vtable pointer' type names can be used to [LangRef] tbaa: type names can be used as hints to optimizations.Apr 23 2021, 11:07 AM
aqjune edited the summary of this revision. (Show Details)
penzn added a subscriber: penzn.Apr 23 2021, 12:41 PM

I am somewhat confused on performance vs correctness - D100717 refers to a miscompile, would adding this behavior also clear miscompiles?

+1 from me.

I am somewhat confused on performance vs correctness - D100717 refers to a miscompile, would adding this behavior also clear miscompiles?

Having this will allow instcombine to produce less patterns that the miscompiling fold is folding away,
thus moving towards potentially being able to remove the miscompiling fold one day.
So no, not really, this in itself won't do anything about those miscompiles.

lebedev.ri accepted this revision.Apr 26 2021, 6:44 AM

If no one objects by friday (in next 5 days), i think we can proceed here?

This revision is now accepted and ready to land.Apr 26 2021, 6:44 AM
jdoerfert accepted this revision.Apr 26 2021, 7:58 AM
fhahn added a subscriber: fhahn.Apr 26 2021, 8:56 AM

On a high level, encoding more Clang specifics into the tbaa spec and using it as heuristics seems a bit unfortunate to me, as it may pessimize frontends that for various reasons cannot use tbaa, especially because the additional information does not seem tbaa specific to me.

I understand it is very convenient to use tbaa in this case, but I am worried about non-Clang frontends once this heuristic becomes important for performance. What will we suggest to frontends that want to opt-in to the optimizations (but tbaa in general is not suitable for them)?

llvm/docs/LangRef.rst
5811

I think from that formulation it is still not clear *what* kind of meaning is assigned to those special strings.

Unless I am missing something, it is still not clear *where* and *how* frontends should use/emit those special names. I think it would be good if the description would be clear on how new frontends should use the special names.

On a high level, encoding more Clang specifics into the tbaa spec and using it as heuristics seems a bit unfortunate to me, as it may pessimize frontends that for various reasons cannot use tbaa, especially because the additional information does not seem tbaa specific to me.

I understand it is very convenient to use tbaa in this case, but I am worried about non-Clang frontends once this heuristic becomes important for performance. What will we suggest to frontends that want to opt-in to the optimizations (but tbaa in general is not suitable for them)?

We could introduce something like !tb.struct which point to the similar structured information as !tbaa.struct. When that is present, that information could also be used to expand llvm.memcpy, but without enforcing the type based aliasing implications.

nikic added a comment.May 1 2021, 2:25 AM

On a high level, encoding more Clang specifics into the tbaa spec and using it as heuristics seems a bit unfortunate to me, as it may pessimize frontends that for various reasons cannot use tbaa, especially because the additional information does not seem tbaa specific to me.

I understand it is very convenient to use tbaa in this case, but I am worried about non-Clang frontends once this heuristic becomes important for performance. What will we suggest to frontends that want to opt-in to the optimizations (but tbaa in general is not suitable for them)?

This is also my concern. It would be very helpful is somebody familiar with TBAA could clarify whether there is any way to add the necessary metadata without having an effect on aliasing. I don't think it's possibly to just disable the TBAA analysis, because the optimization pipeline is generally not under your control (in cross-language linker-plugin LTO scenarios).

From my reading of LangRef, it might be possible to have a type hierarchy of "Root" <- "Dummy" <- "any pointer", where "any pointer" is used to annotate pointer types and "Dummy" for anything else. Then aliasing checks between "Dummy" and "any pointer" will always report aliasing, as it's reachable in one direction. More generally, as long as the type "hierarchy" is a linear chain, no useful aliasing information can be derived. Is that correct? Would this work in practice without causing other complications?

I do think what @jeroen.dobbelaere suggests would be the right way to approach this. This doesn't even have to be in addition to !tbaa.struct, but can be a replacement for it. In particular, I'm thinking that instead of having an {offset, size, tbaa} encoding, it could be {offset, size, type, tbaa}, where type is some well-defined type indicator to use for this optimization, while tbaa is an optional TBAA reference for the member. Frontends with type-based aliasing models would populate the last element, frontends without it wouldn't.

From my reading of LangRef, it might be possible to have a type hierarchy of "Root" <- "Dummy" <- "any pointer", where "any pointer" is used to annotate pointer types and "Dummy" for anything else. Then aliasing checks between "Dummy" and "any pointer" will always report aliasing, as it's reachable in one direction. More generally, as long as the type "hierarchy" is a linear chain, no useful aliasing information can be derived. Is that correct? Would this work in practice without causing other complications?

That will indeed work today. One thing that I find annoying with it, is that it feels like 'fighting to not use tbaa', but it is valid and it will have the intended effect.

I do think what @jeroen.dobbelaere suggests would be the right way to approach this. This doesn't even have to be in addition to !tbaa.struct, but can be a replacement for it. In particular, I'm thinking that instead of having an {offset, size, tbaa} encoding, it could be {offset, size, type, tbaa}, where type is some well-defined type indicator to use for this optimization, while tbaa is an optional TBAA reference for the member. Frontends with type-based aliasing models would populate the last element, frontends without it wouldn't.

Something like that would also work.

FWIW, in the AA call we concluded that we should go away from "tbaa" metadata towards "type" metadata that is resuable. "tbaa" could be a subset, maybe identified with a flag, which will allow TBAA to use it.

aqjune added a comment.May 5 2021, 9:21 PM

Thank you for the inputs as well!
Nuno and I had discussion as well and determined that uses of tbaa might not be good for this purpose as well.
I will revisit this and D100717 when I have enough bandwidth.

Matt added a subscriber: Matt.May 6 2021, 7:31 AM
aqjune abandoned this revision.Tue, Jul 27, 5:38 PM