Reland "[Support] Assert that DomTree nodes share parent" (#102782)

A dominance query of a block that is in a different function is
ill-defined, so assert that getNode() is only called for blocks t

Reland "[Support] Assert that DomTree nodes share parent" (#102782)

A dominance query of a block that is in a different function is
ill-defined, so assert that getNode() is only called for blocks that are
in the same function.

There are three cases, where this behavior did occur. LoopFuse didn't
explicitly do this, but didn't invalidate the SCEV block dispositions,
leaving dangling pointers to free'ed basic blocks behind, causing
use-after-free. We do, however, want to be able to dereference basic
blocks inside the dominator tree, so that we can refer to them by a
number stored inside the basic block.

Reverts #102780
Reland #101198
Fixes #102784

Co-authored-by: Alexis Engelke <engelke@in.tum.de>

show more ...

Revert "[Support] Assert that DomTree nodes share parent" (#102780)

Reverts llvm/llvm-project#101198

Breaks multiple bots:
https://lab.llvm.org/buildbot/#/builders/72/builds/2103
https://lab.ll

Revert "[Support] Assert that DomTree nodes share parent" (#102780)

Reverts llvm/llvm-project#101198

Breaks multiple bots:
https://lab.llvm.org/buildbot/#/builders/72/builds/2103
https://lab.llvm.org/buildbot/#/builders/164/builds/1909
https://lab.llvm.org/buildbot/#/builders/66/builds/2706

show more ...

[Support] Assert that DomTree nodes share parent (#101198)

A dominance query of a block that is in a different function is
ill-defined, so assert that getNode() is only called for blocks that are

[Support] Assert that DomTree nodes share parent (#101198)

A dominance query of a block that is in a different function is
ill-defined, so assert that getNode() is only called for blocks that are
in the same function.

There are two cases, where this behavior did occur. LoopFuse didn't
explicitly do this, but didn't invalidate the SCEV block dispositions,
leaving dangling pointers to free'ed basic blocks behind, causing
use-after-free. We do, however, want to be able to dereference basic
blocks inside the dominator tree, so that we can refer to them by a
number stored inside the basic block.

show more ...

Reapply "[llvm] Teach GlobalDCE about dso_local_equivalent"

Also reapply "[llvm] Teach whole program devirtualization about
relative vtables"

This reverts commit 1c604a9780fcfe92a99d539913553f0835b

Reapply "[llvm] Teach GlobalDCE about dso_local_equivalent"

Also reapply "[llvm] Teach whole program devirtualization about
relative vtables"

This reverts commit 1c604a9780fcfe92a99d539913553f0835b81de3 and
474f5efebed24547e76d022f0c5ffcc9db97ce6f.

show more ...

Revert "Reapply "[llvm] Teach whole program devirtualization about relative vtables""

This reverts commit 09c3bfe9b3eb47a2af0c10531b25f90cfb5fa9f4.

Reapply "[llvm] Teach whole program devirtualization about relative vtables"

This reverts commit 474f5efebed24547e76d022f0c5ffcc9db97ce6f.

[CallPromotionUtil] See through function alias when devirtualizing a virtual call on an alloca. (#80736)

- Extract utility function from
`DevirtModule::tryFindVirtualCallTargets` [1], which sees th

[CallPromotionUtil] See through function alias when devirtualizing a virtual call on an alloca. (#80736)

- Extract utility function from
`DevirtModule::tryFindVirtualCallTargets` [1], which sees through an alias to a function. Call this utility function in
the WPD callsite.
- For type profiling work, this helper function will be used by indirect-call-promotion pass to find the function pointer at a specified vtable offset (an example in [2])

[1] https://github.com/llvm/llvm-project/blob/b99163fe8feeacba7797d5479bbcd5d8f327dd2d/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp#L1069-L1082
[2] https://github.com/minglotus-6/llvm-project/blob/77a0ef12de82d11f448f7f9de6f2dcf87d9b74af/llvm/lib/Transforms/Instrumentation/IndirectCallPromotion.cpp#L347

show more ...

Add a type_checked_load_relative to support relative function pointer tables

This adds a type_checked_load_relative intrinsic whose semantics it is to
load a relative function pointer.

A relative f

Add a type_checked_load_relative to support relative function pointer tables

This adds a type_checked_load_relative intrinsic whose semantics it is to
load a relative function pointer.

A relative function pointer is a pointer to a 32bit value that when
added to its address yields the address of the function.

Differential Revision: https://reviews.llvm.org/D143204

show more ...

Revert "[llvm] Teach GlobalDCE about dso_local_equivalent"

This reverts commit 86dbcafd0cdc88ae85896c6f12ecaa6006aeba54.

Reverting since this depends on db288184765c0b4010060ebea1f6de3ac1f66445
whi

Revert "[llvm] Teach GlobalDCE about dso_local_equivalent"

This reverts commit 86dbcafd0cdc88ae85896c6f12ecaa6006aeba54.

Reverting since this depends on db288184765c0b4010060ebea1f6de3ac1f66445
which broke our lto builders reported by fxbug.dev/12380.

show more ...

Revert "[llvm] Teach whole program devirtualization about relative vtables"

This reverts commit db288184765c0b4010060ebea1f6de3ac1f66445.

Reverting since it broke our lto builders reported by fxbug

Revert "[llvm] Teach whole program devirtualization about relative vtables"

This reverts commit db288184765c0b4010060ebea1f6de3ac1f66445.

Reverting since it broke our lto builders reported by fxbug.dev/123807.

show more ...

[llvm] Use ConstantInt::{isZero,isOne} (NFC)

[llvm] Teach GlobalDCE about dso_local_equivalent

This way, C++ relative-vtables can also participate in GlobalDCE. This
depends on some TypeMetadataUtils.cpp bits in D134320, but that
dependency ca

[llvm] Teach GlobalDCE about dso_local_equivalent

This way, C++ relative-vtables can also participate in GlobalDCE. This
depends on some TypeMetadataUtils.cpp bits in D134320, but that
dependency can be removed and included here if necessary.

Differential Revision: https://reviews.llvm.org/D135928

show more ...

[llvm] Teach whole program devirtualization about relative vtables

Prior to this patch, WPD was not acting on relative-vtables in C++. This
involves teaching WPD about these things:

- llvm.load.rel

[llvm] Teach whole program devirtualization about relative vtables

Prior to this patch, WPD was not acting on relative-vtables in C++. This
involves teaching WPD about these things:

- llvm.load.relative which is how relative-vtables are indexed (instead of GEP)
- dso_local_equivalent which is used in the vtable itself when taking the
offset between a virtual function and vtable
- Update llvm/test/ThinLTO/X86/devirt.ll to use opaque pointers and add
equivalent tests for RV

Differential Revision: https://reviews.llvm.org/D134320

show more ...

[NFC]] Use llvm::all_of instead of std::all_of

Reviewed By: kazu

Differential Revision: https://reviews.llvm.org/D131886

[WPD] Use new llvm.public.type.test intrinsic for potentially publicly visible classes

Turning on opaque pointers has uncovered an issue with WPD where we currently pattern match away `assume(type.t

[WPD] Use new llvm.public.type.test intrinsic for potentially publicly visible classes

Turning on opaque pointers has uncovered an issue with WPD where we currently pattern match away `assume(type.test)` in WPD so that a later LTT doesn't resolve the type test to undef and introduce an `assume(false)`. The pattern matching can fail in cases where we transform two `assume(type.test)`s into `assume(phi(type.test.1, type.test.2))`.

Currently we create `assume(type.test)` for all virtual calls that might be devirtualized. This is to support `-Wl,--lto-whole-program-visibility`.

To prevent this, all virtual calls that may not be in the same LTO module instead use a new `llvm.public.type.test` intrinsic in place of the `llvm.type.test`. Then when we know if `-Wl,--lto-whole-program-visibility` is passed or not, we can either replace all `llvm.public.type.test` with `llvm.type.test`, or replace all `llvm.public.type.test` with `true`. This prevents WPD from trying to pattern match away `assume(type.test)` for public virtual calls when failing the pattern matching will result in miscompiles.

Reviewed By: tejohnson

Differential Revision: https://reviews.llvm.org/D128955

show more ...

Cleanup includes: LLVMAnalysis

Number of lines output by preprocessor:
before: 1065940348
after: 1065307662

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Diff

Cleanup includes: LLVMAnalysis

Number of lines output by preprocessor:
before: 1065940348
after: 1065307662

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D120659

show more ...

[GlobalDCE] In VFE, replace the whole 'sub' expression of unused relative-pointer-based vtable slots

Differential Revision: https://reviews.llvm.org/D109114

[GlobalDCE] In VFE support for relative pointers, allow GEP references to the base symbol

This is for Swift VFE support. In some vtable forms that Swift emits, the "base" of a relative pointer is no

[GlobalDCE] In VFE support for relative pointers, allow GEP references to the base symbol

This is for Swift VFE support. In some vtable forms that Swift emits, the "base" of a relative pointer is not the global symbol itself directly, but a GEP into it -- so the pointer is relative to a particular field in the global. So getPointerAtOffset() needs to be able to see through the GEP and allow it in a SUB expression, to correctly recognize the offset as a vtable slot.

Differential Revision: https://reviews.llvm.org/D109169

show more ...

[GlobalDCE] Handle relative pointers in VFE (for Swift vtables)

To support Virtual Function Elimination to Swift, this PR adds support for Swift
vtables which contain "relative pointers" instead of

[GlobalDCE] Handle relative pointers in VFE (for Swift vtables)

To support Virtual Function Elimination to Swift, this PR adds support for Swift
vtables which contain "relative pointers" instead of direct pointer references.
These are in the form of:

@symbol = ... {
i32 trunc (i64 sub (i64 ptrtoint (<type> @target to i64), i64 ptrtoint (... @symbol to i64)) to i32)
}

The PR extends GlobalDCE's way of looking up a vtable offset into a dependency
to be able to see through this expression and find the target symbol.

Differential Revision: https://reviews.llvm.org/D107645

show more ...

Revert "Allow invokable sub-classes of IntrinsicInst"

This reverts commit d87b9b81ccb95217181ce75515c6c68bbb408ca4.

Post commit review raised concerns, reverting while discussion happens.

Allow invokable sub-classes of IntrinsicInst

It used to be that all of our intrinsics were call instructions, but over time, we've added more and more invokable intrinsics. According to the verifier

Allow invokable sub-classes of IntrinsicInst

It used to be that all of our intrinsics were call instructions, but over time, we've added more and more invokable intrinsics. According to the verifier, we're up to 8 right now. As IntrinsicInst is a sub-class of CallInst, this puts us in an awkward spot where the idiomatic means to check for intrinsic has a false negative if the intrinsic is invoked.

This change switches IntrinsicInst from being a sub-class of CallInst to being a subclass of CallBase. This allows invoked intrinsics to be instances of IntrinsicInst, at the cost of requiring a few more casts to CallInst in places where the intrinsic really is known to be a call, not an invoke.

After this lands and has baked for a couple days, planned cleanups:
Make GCStatepointInst a IntrinsicInst subclass.
Merge intrinsic handling in InstCombine and use idiomatic visitIntrinsicInst entry point for InstVisitor.
Do the same in SelectionDAG.
Do the same in FastISEL.

Differential Revision: https://reviews.llvm.org/D99976

show more ...

Use AssumeInst in a few more places [nfc]

Follow up to a6d2a8d6f5. These were found by simply grepping for "::assume", and are the subset of that result which looked cleaner to me using the isa/dyn

Use AssumeInst in a few more places [nfc]

Follow up to a6d2a8d6f5. These were found by simply grepping for "::assume", and are the subset of that result which looked cleaner to me using the isa/dyn_cast patterns.

show more ...

TypeMetadataUtils.h - reduce Instructions.h include to forward declaration. NFC.

Move implicit include dependencies down to source file.

[llvm][NFC][CallSite] Remove CallSite from TypeMetadataUtils & related

Reviewers: craig.topper, dblaikie

Subscribers: hiraditya, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.ll

[llvm][NFC][CallSite] Remove CallSite from TypeMetadataUtils & related

Reviewers: craig.topper, dblaikie

Subscribers: hiraditya, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D78666

show more ...

Reland: Dead Virtual Function Elimination

Remove dead virtual functions from vtables with
replaceNonMetadataUsesWith, so that CGProfile metadata gets cleaned up
correctly.

Original commit message:

Reland: Dead Virtual Function Elimination

Remove dead virtual functions from vtables with
replaceNonMetadataUsesWith, so that CGProfile metadata gets cleaned up
correctly.

Original commit message:

Currently, it is hard for the compiler to remove unused C++ virtual
functions, because they are all referenced from vtables, which are referenced
by constructors. This means that if the constructor is called from any live
code, then we keep every virtual function in the final link, even if there
are no call sites which can use it.

This patch allows unused virtual functions to be removed during LTO (and
regular compilation in limited circumstances) by using type metadata to match
virtual function call sites to the vtable slots they might load from. This
information can then be used in the global dead code elimination pass instead
of the references from vtables to virtual functions, to more accurately
determine which functions are reachable.

To make this transformation safe, I have changed clang's code-generation to
always load virtual function pointers using the llvm.type.checked.load
intrinsic, instead of regular load instructions. I originally tried writing
this using clang's existing code-generation, which uses the llvm.type.test
and llvm.assume intrinsics after doing a normal load. However, it is possible
for optimisations to obscure the relationship between the GEP, load and
llvm.type.test, causing GlobalDCE to fail to find virtual function call
sites.

The existing linkage and visibility types don't accurately describe the scope
in which a virtual call could be made which uses a given vtable. This is
wider than the visibility of the type itself, because a virtual function call
could be made using a more-visible base class. I've added a new
!vcall_visibility metadata type to represent this, described in
TypeMetadata.rst. The internalization pass and libLTO have been updated to
change this metadata when linking is performed.

This doesn't currently work with ThinLTO, because it needs to see every call
to llvm.type.checked.load in the linkage unit. It might be possible to
extend this optimisation to be able to use the ThinLTO summary, as was done
for devirtualization, but until then that combination is rejected in the
clang driver.

To test this, I've written a fuzzer which generates random C++ programs with
complex class inheritance graphs, and virtual functions called through object
and function pointers of different types. The programs are spread across
multiple translation units and DSOs to test the different visibility
restrictions.

I've also tried doing bootstrap builds of LLVM to test this. This isn't
ideal, because only classes in anonymous namespaces can be optimised with
-fvisibility=default, and some parts of LLVM (plugins and bugpoint) do not
work correctly with -fvisibility=hidden. However, there are only 12 test
failures when building with -fvisibility=hidden (and an unmodified compiler),
and this change does not cause any new failures for either value of
-fvisibility.

On the 7 C++ sub-benchmarks of SPEC2006, this gives a geomean code-size
reduction of ~6%, over a baseline compiled with "-O2 -flto
-fvisibility=hidden -fwhole-program-vtables". The best cases are reductions
of ~14% in 450.soplex and 483.xalancbmk, and there are no code size
increases.

I've also run this on a set of 8 mbed-os examples compiled for Armv7M, which
show a geomean size reduction of ~3%, again with no size increases.

I had hoped that this would have no effect on performance, which would allow
it to awlays be enabled (when using -fwhole-program-vtables). However, the
changes in clang to use the llvm.type.checked.load intrinsic are causing ~1%
performance regression in the C++ parts of SPEC2006. It should be possible to
recover some of this perf loss by teaching optimisations about the
llvm.type.checked.load intrinsic, which would make it worth turning this on
by default (though it's still dependent on -fwhole-program-vtables).

Differential revision: https://reviews.llvm.org/D63932

llvm-svn: 375094

show more ...