[WPD][LLD] Add option to validate RTTI is enabled on all native types and prevent devirtualization on types with native RTTI

[modimo]

Summary

Discussion about this approach: https://discourse.llvm.org/t/rfc-safer-whole-program-class-hierarchy-analysis/65144/18

When enabling WPD in an environment where native binaries are present, types we want to optimize can be derived from inside these native files and devirtualizing them can lead to correctness issues. RTTI can be used as a way to determine all such types in native files and exclude them from WPD providing a safe checked way to enable WPD.

The approach is:

1. In the linker, identify if RTTI is available for all native types. If not, under --lto-validate-all-vtables-have-type-infos --lto-whole-program-visibility is automatically disabled. This is done by examining all .symtab symbols in object files and .dynsym symbols in DSOs for vtable (_ZTV) and typeinfo (_ZTI) symbols and ensuring there's always a match for every vtable symbol.
2. During thinlink, if --lto-validate-all-vtables-have-type-infos is set and RTTI is available for all native types, identify all typename (_ZTS) symbols via their corresponding typeinfo (_ZTI) symbols that are used natively or outside of our summary and exclude them from WPD.

Testing:
ninja check-all
large Meta service that uses boost, glog and libstdc++.so runs successfully with WPD via --lto-whole-program-visibility. Previously, native types in boost caused incorrect devirtualization that led to crashes.

[modimo]

Add devirt_validate_vtable_typeinfos_mixed_lto.ll, minor test changes

[tejohnson]

lld/test/ELF/lto/devirt_validate_vtable_typeinfos_mixed_lto.ll

118

Both this and the CHECK-SUMMARY-IR case below are incorrect devirtualizations, right? Is this another case that we are not doing correctly without the validation options in this patch?

124

I think we only get the vtable summary from the regular LTO object because it doesn't have the EnableSplitLTOUnit module flag set in the IR here. Normally, this is added by clang when building -flto. And this currently prevents vtable summaries being added to the LTO summary (https://github.com/llvm/llvm-project/blob/8a15bdb5e637f81041591d97bea0267b5f053f16/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp#L734-L736).

When I added that guard, it was because I didn't think we needed these summaries when splitting was enabled, as I was thinking of either the everything-is-regular LTO case or the -fsplit-lto-unit case that you get by default with -flto=thin -fwhole-program-vtables, where all the vtables are placed in the regular LTO split modules. It's possible that we could remove that guard, but with it I think this case would do the wrong thing if the regular IR was built from clang with -flto.

[modimo]

Headed out on PTO and will be back on the 24th, will pick this back up then!

lld/test/ELF/lto/devirt_validate_vtable_typeinfos_mixed_lto.ll

124

I see, so the BASE scenario being tested here is already guarded by EnableSplitLTOUnit since ThinLTO would have EnableSplitLTOUnit=0 and RegularLTO would have EnableSplitLTOUnit=1. Is this the scenario described in the previous comment?

RegularLTO summaries are added to the combined index used by ThinLTO, but it looks like the vtable summaries aren't currently created for them. I think you are right in that there is a potential hole here for ThinLTO WPD if linked with a regular LTO object containing an override. Can you test this case to confirm? If that is an issue, then I guess we do need another GlobalRes field. Maybe VisibleOutsideLTOUnit or something like that?

The mixed case then would be RegularLTO combined with ThinLTO + -split-lto-unit where neither generate typeidCompatibleVTable and all the analysis is done on the combined RegularLTO module.

[modimo]

Looking at https://github.com/llvm/llvm-project/blob/9b6b6bb/clang/lib/CodeGen/BackendUtil.cpp#L170-L173, RegularLTO will have a summary attached through Clang by default except for ld64 targets. The mixed case then reduces to RegularLTO+Summary and ThinLTO+Split since EnableSplitLTOUnit must be consistent so everything is done by DevirtModule::run and there's no mixture with DevirtIndex::run. The mechanism for IsVisibleToRegularObj for RegularLTO also ends up being identical to that of ThinLTO since all symbols will be present in the combined summary.

For ld64 targets there is a potential hole mixing RegularLTO+NoSummary with ThinLTO which would be caught with the current validation scheme. However, the validation functionality is only for the lld ELF target so the ld64 targets are unchanged.

[modimo]

Change mixed scenario to RegularLTO+Summary and ThinLTO+Split. Modify other tests to have RegularLTO+Summary.

[modimo]

lld/test/ELF/lto/devirt_validate_vtable_typeinfos.ll

7

Appending module flags so RegularLTO correctly generates it's summary without typeidCompatibleVTable means the test can be re-used. However I think duplicating the tests is reasonable as well and could be cleaner, WDYT?

[modimo]

Set EnableSplitLTOUnit=1 for RegularLTO tests as well

[tejohnson]

lgtm with a couple comments/suggestions below. Thanks!

In D155659#4618301, @modimo wrote:

Looking at https://github.com/llvm/llvm-project/blob/9b6b6bb/clang/lib/CodeGen/BackendUtil.cpp#L170-L173, RegularLTO will have a summary attached through Clang by default except for ld64 targets. The mixed case then reduces to RegularLTO+Summary and ThinLTO+Split since EnableSplitLTOUnit must be consistent so everything is done by DevirtModule::run and there's no mixture with DevirtIndex::run. The mechanism for IsVisibleToRegularObj for RegularLTO also ends up being identical to that of ThinLTO since all symbols will be present in the combined summary.

Ok, yes - I think the scenario I was worried about is caught by the existing verification that EnableSplitLTOUnit is set consistently.

lld/test/ELF/lto/devirt_validate_vtable_typeinfos.ll

7

Do we need these module flags for correct operation of this test (ditto for the similar no_rtti one later)? If not, then probably don't bother adding in these tests (I think these may only be needed in practice for the hybrid testing). If they are now needed for correct operation of the regular LTO testing, then I am ok with the approach here as I think it is probably better to reduce duplication of nearly identical IR tests (and I see this approach used in other tests too).

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

893

nit: the braces can be removed from the for loop

[MaskRay]

Thanks for the patch. Will try to read through this :)

[modimo]

Fix nit: braces

[modimo]

Thanks for the review!

lld/test/ELF/lto/devirt_validate_vtable_typeinfos.ll

7

Do we need these module flags for correct operation of this test (ditto for the similar no_rtti one later)?

Yeah, to trigger summary generation but on the RegularLTO pipeline requires these module flags.

If they are now needed for correct operation of the regular LTO testing, then I am ok with the approach here as I think it is probably better to reduce duplication of nearly identical IR tests (and I see this approach used in other tests too).

Sounds good, I'll leave it as is.

[MaskRay]

Will study...

lld/ELF/Driver.cpp

1114

This long list here makes me nervous. Will try to learn it.

lld/ELF/Options.td

607

New options use EEq to disallow single-dash long options, to not conflict with -l.

lld/test/ELF/lto/Inputs/devirt_validate_vtable_typeinfos.ll

5

grtev4 => unknown

llvm/tools/opt/opt.cpp

573

The prevailing and recommended style liked by clang-format and clang-tidy is

/*WholeProgramVisibilityEnabledInLTO=*/false

[modimo]

Review Feedback

[modimo]

lld/ELF/Driver.cpp

1114

Taking a look again I don't think these names need special exclusion. They're defined in libstdc++/libc++abi and the release packages in my scenarios have RTTI enabled meaning their type info symbols are present during linking. Testing E2E linking on some of our large services with these removed succeeds.

If RTTI is disabled on these libraries considerably more symbols would not have matching type infos and --lto-whole-program-visibility should be disabled. Looking back I think these exclusions came about when I was only examining the .symtab/.dynsym of individual object/shared files which didn't take into account that these symbols would be resolved by libstdc++/libc++abi.

[modimo]

Remove explicit knownSafeVtableNames entries

[modimo]

Gentle ping @MaskRay

[MaskRay]

In D155659#4640159, @modimo wrote:

Gentle ping @MaskRay

Sorry for the delay. (There were Phabricator issues to handle beside work...)

I will need to re-read https://discourse.llvm.org/t/rfc-safer-whole-program-class-hierarchy-analysis/65144 and an internal discussion in May 2022 when I was thinking about _ZTI.

-frtti is discouraged by https://google.github.io/styleguide/cppguide.html#Run-Time_Type_Information__RTTI_ , so I think it may not benefit us... but this feature is still useful. I need to read these discussions...

lld/ELF/Driver.cpp

1046

omit braces for single-line single-statement body

1076

drop the two nested braces

1080

1083

If not starting with _ZTV, consider reporting an error?

[MaskRay]

I wonder why the following example is still incorrect. I haven't carefully studied the LTO part of code. It seems that you do handle isUsedInRegularObj.

cat > a.h <<'eof'
struct A { virtual int foo(); };
int bar(A *a);
eof
cat > a.cc <<'eof'
#include "a.h"
int A::foo() { return 1; }
int bar(A *a) { return a->foo(); }
eof
cat > b.cc <<'eof'
#include "a.h"
struct B : A { int foo() { return 2; } };
int baz() { B b; return bar(&b); }
eof
cat > main.cc <<'eof'
#include "a.h"
#include <stdio.h>
extern int baz();
int main() {
  A a;
  printf("%d %d\n", bar(&a), baz());
}
eof

clang++ -c -flto=thin -fwhole-program-vtables -O main.cc a.cc b.cc
clang++ -c -O b.cc -o b0.o

% clang++ -flto=thin -Wl,--lto-whole-program-visibility -fuse-ld=lld main.o a.o b.o && ./a.out
1 2
% clang++ -Wl,--lto-validate-all-vtables-have-type-infos -flto=thin -Wl,--lto-whole-program-visibility -fuse-ld=lld main.o a.o b0.o && ./a.out
1 1

lld/ELF/Config.h

251

Move ltoAllVtablesHaveTypeInfos (not an option) to Ctx

lld/ELF/Driver.cpp

1055

getGlobalELFSyms to skip local symbols

1087

and delete the assignment below

2879

lld/test/ELF/lto/devirt_validate_vtable_typeinfos.ll

14

You can remove the relocation-model=static object file as there is no testable difference.

Then, consider renaming %t2_pic.o to %t2.o

85

; VALIDATE-NOT: single-impl:
; VALIDATE:     single-impl: devirtualized a call to _ZN1D1mEi
; VALIDATE-NOT: single-impl:

164

Consider pasting the source code as well for readability and upgradability?

I haven't carefully studied the tests yet...

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

795

typo: will will

Add a period.

888

typo: will will

append a period.

893

delete braces in this nested case when the only body has just one line.

[MaskRay]

lld/ELF/Driver.cpp

1089

the order is not guaranteed to be deterministic. Consider a SmallSetVector with inline size=0.

auto & => StringRef

[tejohnson]

In D155659#4640392, @MaskRay wrote:

In D155659#4640159, @modimo wrote:

Gentle ping @MaskRay

Sorry for the delay. (There were Phabricator issues to handle beside work...)

I will need to re-read https://discourse.llvm.org/t/rfc-safer-whole-program-class-hierarchy-analysis/65144 and an internal discussion in May 2022 when I was thinking about _ZTI.

-frtti is discouraged by https://google.github.io/styleguide/cppguide.html#Run-Time_Type_Information__RTTI_ , so I think it may not benefit us... but this feature is still useful. I need to read these discussions...

I looked at this more closely after this patch was mailed. While use of RTTI is discouraged, building with -fno-rtti isn't specifically encouraged afaict, and when I built a large number of important binaries internally with this patch in validation mode, it turned out that there were only a few objects/symbols affected, and we could allowlist them to enable WPD. See my earlier comment from July 25:

I cranked through a bunch of builds with this change and thankfully while they all do have at least one vtable from an -fno-rtti native object, there are only a handful of unique symbols (which all appear safe), so we could consider using --lto-known-safe-vtables to allowlist them.

I wonder why the following example is still incorrect.

Hmm, that seems like exactly the case that should be caught and handled automatically by this patch. Oh, I just compiled the same source code to a native object and nm shows a reference to the typeinfo for A, but no type name for A (_ZTS1A):

$ nm b.o
                 U _Z3barP1A
0000000000000000 T _Z3bazv
0000000000000000 W _ZN1B3fooEv
                 U _ZTI1A
0000000000000000 V _ZTI1B
0000000000000000 V _ZTS1B
0000000000000000 V _ZTV1B
                 U _ZTVN10__cxxabiv120__si_class_type_infoE

The _ZTS symbol is the one referenced by the type metadata, and what this patch is going to look for being referenced in native objects. Not familiar with the rules around when that symbol ends up being used, but if it isn't consistently referenced from native objects then this solution isn't going to work as well as hoped. Should it be looking for either the type name or the corresponding type info?

[modimo]

Good catch with the example! Looks like this is an interaction with the class A having a key function (https://lld.llvm.org/missingkeyfunction.html) defined in a.cc so b.cc doesn't generate a vtable symbol for class A and RTTI only emits a reference to _ZTI1A. The Itanium C++ ABI mandates type name as a field for every type info (https://itanium-cxx-abi.github.io/cxx-abi/abi.html#rtti) but because we only get a reference _ZTS1A doesn't come along for the ride. The vtable for class A being defined only inside the LTO Unit then means there's no native reference to key off of.

I think this means native symbol lookup should be keyed off the type info symbol corresponding to the type name we have in metadata. The layout of RTTI guarantees we'll have the base type info symbol(s) but as seen here not necessarily the type name symbol. WDYT?

[modimo]

Review Feedback

[tejohnson]

In D155659#4641354, @modimo wrote:

Good catch with the example! Looks like this is an interaction with the class A not having a key function (https://lld.llvm.org/missingkeyfunction.html) so b.cc doesn't generate a vtable symbol for class A and RTTI only emits a reference to _ZTI1A. The Itanium C++ ABI mandates type name as a field for every type info (https://itanium-cxx-abi.github.io/cxx-abi/abi.html#rtti) but because we only get a reference _ZTS1A doesn't come along for the ride. The vtable for class A being defined only inside the LTO Unit then means there's no native reference to key off of.

I think this means native symbol lookup should be keyed off the type info symbol corresponding to the type name we have in metadata. The layout of RTTI guarantees we'll have the base type info symbol(s) but as seen here not necessarily the type name symbol. WDYT?

This seems ok to me - there is already code in the lld part of this patch that maps _ZTV to _ZTI, so mapping _ZTS to _ZTI is not significantly different. Can you also add this as a test case (suggest including the original c++ code in a comment).

[modimo]

lld/test/ELF/lto/devirt_validate_vtable_typeinfos.ll

164

I pulled the base IR from lld/test/ELF/lto/devirt_vcall_vis_export_dynamic.ll and modified it so no direct source.

The test case is effectively:

struct A {
  virtual void f(int) = 0;
  virtual void n(int) { return 0; }
};

struct B {
  virtual void f(int) { return 0; }
};

struct C {
  virtual void f(int) { return 0; }
};

namespace {
  struct D {
    virtual void int m(int) { return 0; }
  };
}

int _start(A *obj, D* obj2, int a) {
  call = obj->n(a); // single implementation in A, devirtualize unless a native type derives from A
  call2 = obj->f(call); // multiple implementation in B and C, never devirtualize
  call3 = obj2->m(call2); // local type, always devirtualize
  return call3;
}

[modimo]

Key off of type info (_ZTI) symbols, add test case

[modimo]

Move symbol check to common function

[modimo]

Gentle ping @MaskRay

[MaskRay]

Looks great with some nits! Checking _ZTS in TypeIDVisibleToRegularObj (switch to typeIDVisibleToRegularObj) looks good to me. Sorry for the delay.
There are a number of resolved comments you may want to mark as done.

lld/ELF/Driver.cpp

1042

The conventional style in lld/ omits llvm:: for DenseSet.

1051

1073

This still relies on the iteration order of DenseSet vtableSymbols. We need SetVector for vtableSymbols as well.

auto &s => StringRef s

2879

Not done.

lld/ELF/Options.td

607

When --lto-validate-all-vtables-have-type-infos is enabled, skip validation on these vtables (_ZTV symbols)

llvm/lib/LTO/LTO.cpp

1282

redundant hash table lookup here.

Better to use find(name) with slightly more code

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

785

Perhaps we should fix these functions to follow https://llvm.org/docs/CodingStandards.html#use-namespace-qualifiers-to-implement-previously-declared-functions . Pushed b4d4146db3b9a29773259c8b8a6cb7c98da90e73 and you'll need a rebase.

796

Use consume_front here to avoid consume_front below.

805

to avoid constructing a possibly heap-allocated std::string twice.

809

skipUpdateDueToValidation

[MaskRay]

lld/ELF/Config.h

481

We need ltoAllVtablesHaveTypeInfos = false in reset

[modimo]

In D155659#4647141, @MaskRay wrote:

Looks great with some nits! Checking _ZTS in TypeIDVisibleToRegularObj (switch to typeIDVisibleToRegularObj) looks good to me. Sorry for the delay.
There are a number of resolved comments you may want to mark as done.

Appreciate the thorough review! Good callout on the resolved comments, keeping those up to date keeps the context clearer for everyone involved--will keep them updated in the future.

llvm/lib/LTO/LTO.cpp

1282

Good call, other places here also use the find pattern.

llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp

785

Sounds good, I'll follow up with the correct style on the rebase

[modimo]

Review Feedback

[modimo]

Rebase