[IR][GlobalDCE] Extend !vcall_visibility to be able to specify an offset range that it applies to

[kubamracek]

Summary

As part of codesize optimization work for Swift, we'd like to add Virtual Function Elimination to Swift, very similarly to how GlobalDCE supports C++ VFE. This PR adds support to GlobalDCE for vtables containing references that are not virtual functions and should not participate in VFE. This is achieved by extending !vcall_visibility to be able to specify an offset range that it applies to.

[kubamracek]

https://reviews.llvm.org/D107645 [GlobalDCE] Handle relative pointers in VFE (for Swift vtables)

[fhahn]

As part of codesize optimization work for Swift, we'd like to add Virtual Function Elimination to Swift, very similarly to how GlobalDCE supports C++ VFE.

I think it would be good to drop this part from the description, as the change is not really related to swift; it just changes the code to ignore entries at slots without !type.

It seems sensible to me to ignore entries without corresponding !type metadata and this should be in line with the specification in langref. @pcc, @tejohnson Are there any issues you could think of?

llvm/lib/Transforms/IPO/GlobalDCE.cpp

133

It seems like it may be quite expensive to iterate over all types for a global, getting the pointer at the offsets and so on, possibly multiple times for the same GV. If that's the case, could we pre-compute the set of valid pointers in VTable and then just check against the set?

llvm/test/Transforms/GlobalDCE/virtual-functions-non-vfunc-entries.ll

2

Can you pre-commit this test and just include the diff with the changes caused by the patch?

[kubamracek]

llvm/lib/Transforms/IPO/GlobalDCE.cpp

133

Done.

llvm/test/Transforms/GlobalDCE/virtual-functions-non-vfunc-entries.ll

2

Done.

[tejohnson]

In D108741#2997844, @fhahn wrote:

As part of codesize optimization work for Swift, we'd like to add Virtual Function Elimination to Swift, very similarly to how GlobalDCE supports C++ VFE.

I think it would be good to drop this part from the description, as the change is not really related to swift; it just changes the code to ignore entries at slots without !type.

It seems sensible to me to ignore entries without corresponding !type metadata and this should be in line with the specification in langref. @pcc, @tejohnson Are there any issues you could think of?

Is this specified in the langref? I looked through the type metadata documentation but don't see it mentioned there that all vfuncs will have type metadata. Looks like that was added a bit later than the original type metadata, in D47567. I think what is specified in langref is that it has type metadata for the address point. Probably the documentation needs updating. But from what I can see, it looks like this should always be emitted now. @pcc ?

[kubamracek]

Updating TypeMetadata.rst to be explicit about what happens for vtable slots without a matching !type attachment.

[fhahn]

In D108741#2998705, @tejohnson wrote:

In D108741#2997844, @fhahn wrote:

As part of codesize optimization work for Swift, we'd like to add Virtual Function Elimination to Swift, very similarly to how GlobalDCE supports C++ VFE.

I think it would be good to drop this part from the description, as the change is not really related to swift; it just changes the code to ignore entries at slots without !type.

It seems sensible to me to ignore entries without corresponding !type metadata and this should be in line with the specification in langref. @pcc, @tejohnson Are there any issues you could think of?

Is this specified in the langref? I looked through the type metadata documentation but don't see it mentioned there that all vfuncs will have type metadata. Looks like that was added a bit later than the original type metadata, in D47567. I think what is specified in langref is that it has type metadata for the address point. Probably the documentation needs updating. But from what I can see, it looks like this should always be emitted now. @pcc ?

Thanks for checking! I think the update to the langref in the latest version should spell out things clearly.

llvm/docs/TypeMetadata.rst

289

Not sure about the rst syntax here. Does this render correctly as list?

llvm/lib/Transforms/IPO/GlobalDCE.cpp

140

nit: unrelated change

214

can we instead just declare VFuncs in the loop?

233

Does C being nullptr here indicate that the type id is invalid?

[kubamracek]

llvm/docs/TypeMetadata.rst

289

Fixed!

llvm/lib/Transforms/IPO/GlobalDCE.cpp

140

Removed.

214

Done.

233

Yes, it means the offset mentioned in the !type attachment isn't found in the vtable. I restructured this to avoid the ternary operator.

[fhahn]

LGTM with a few remaining nits. Please wait a couple of days in case there are additional comments.

llvm/lib/Transforms/IPO/GlobalDCE.cpp

134

nit: contains instead of count

135

coding standard recommends not using {} for single line statements https://llvm.org/docs/CodingStandards.html#don-t-use-braces-on-simple-single-statement-bodies-of-if-else-loop-statements

220

nit: .... also collect the set of virtual functions in the vtable.

235

coding standard recommends not using {} for single line statements https://llvm.org/docs/CodingStandards.html#don-t-use-braces-on-simple-single-statement-bodies-of-if-else-loop-statements

[kubamracek]

LGTM with a few remaining nits. Please wait a couple of days in case there are additional comments.

Addressed the format comments, will wait a couple of days. Thanks!

[pcc]

In D108741#3005803, @fhahn wrote:

In D108741#2998705, @tejohnson wrote:

In D108741#2997844, @fhahn wrote:

As part of codesize optimization work for Swift, we'd like to add Virtual Function Elimination to Swift, very similarly to how GlobalDCE supports C++ VFE.

I think it would be good to drop this part from the description, as the change is not really related to swift; it just changes the code to ignore entries at slots without !type.

It seems sensible to me to ignore entries without corresponding !type metadata and this should be in line with the specification in langref. @pcc, @tejohnson Are there any issues you could think of?

Is this specified in the langref? I looked through the type metadata documentation but don't see it mentioned there that all vfuncs will have type metadata. Looks like that was added a bit later than the original type metadata, in D47567. I think what is specified in langref is that it has type metadata for the address point. Probably the documentation needs updating. But from what I can see, it looks like this should always be emitted now. @pcc ?

Thanks for checking! I think the update to the langref in the latest version should spell out things clearly.

It isn't great that VFE apparently relies on the type metadata that we added to support member function pointer CFI in C++. I was unaware that this was the case, and it shouldn't be necessary for frontends that don't have something like C++'s peculiar member function pointer ABI (I assume that Swift doesn't?) It would be better if we designed an independent way of marking these entries as subject to VFE.

[kubamracek]

It isn't great that VFE apparently relies on the type metadata that we added to support member function pointer CFI in C++. I was unaware that this was the case, and it shouldn't be necessary for frontends that don't have something like C++'s peculiar member function pointer ABI (I assume that Swift doesn't?) It would be better if we designed an independent way of marking these entries as subject to VFE.

As far as I can tell, VFE was added via https://reviews.llvm.org/D63932 and it has since always used type metadata and the !type annotations on vtables. Are you asking for a reversal on how VFE is done at the IR level, including how it's done for C++ in Clang? I'd love to see more thought on that (and what exactly do you think the design should aim to do better), but it seems to me that that's out of scope for this particular small tweak that I'm pursuing.

[kubamracek]

@pcc, could I ask for some details about your last comment? I'm specifically wondering whether you're against proceeding with the change from this review.

[pcc]

In D108741#3011080, @kubamracek wrote:

It isn't great that VFE apparently relies on the type metadata that we added to support member function pointer CFI in C++. I was unaware that this was the case, and it shouldn't be necessary for frontends that don't have something like C++'s peculiar member function pointer ABI (I assume that Swift doesn't?) It would be better if we designed an independent way of marking these entries as subject to VFE.

As far as I can tell, VFE was added via https://reviews.llvm.org/D63932 and it has since always used type metadata and the !type annotations on vtables. Are you asking for a reversal on how VFE is done at the IR level, including how it's done for C++ in Clang? I'd love to see more thought on that (and what exactly do you think the design should aim to do better), but it seems to me that that's out of scope for this particular small tweak that I'm pursuing.

Sorry, I think I managed to confuse myself when I was trying to figure out what VFE actually relies on. It seems that VFE doesn't rely on what I thought it did. Although VFE relies on type metadata, it only relies on it to determine the locations of the address points, and not the locations of the VFE-eligible function slots.

Historically we've only ever used VFE with C++, which is fine with any virtual function slot being eligible for VFE. As such, we implemented it to make that assumption. What we should really be doing is have a way of marking slots as eligible, and we never got a chance to design that because it wasn't necessary. Now that you're proposing to use VFE with a language which presumably does have some non-VFE-eligible virtual function slots, I think we need to design such a mechanism.

In D108741#3021793, @kubamracek wrote:

@pcc, could I ask for some details about your last comment? I'm specifically wondering whether you're against proceeding with the change from this review.

Sorry, but I think I'm against it because the mechanism that you've chosen seems like an abuse of the !type metadata, since the metadata is meant to be used as a reference point for accesses relative to it, and not as a way of marking up specific fields by itself. As a more practical concern, it has no way of representing the situation where the pointer at the address point is not eligible for VFE.

Here's one alternative proposal: can we make it so that any vtable slots that are eligible for VFE are represented using a new type of Constant (similar to dso_local_equivalent)? This also has the advantage that frontends could also use it for global variables as well as functions.

[fhahn]

In D108741#3021933, @pcc wrote:

In D108741#3021793, @kubamracek wrote:

@pcc, could I ask for some details about your last comment? I'm specifically wondering whether you're against proceeding with the change from this review.

Sorry, but I think I'm against it because the mechanism that you've chosen seems like an abuse of the !type metadata, since the metadata is meant to be used as a reference point for accesses relative to it, and not as a way of marking up specific fields by itself. As a more practical concern, it has no way of representing the situation where the pointer at the address point is not eligible for VFE.

Here's one alternative proposal: can we make it so that any vtable slots that are eligible for VFE are represented using a new type of Constant (similar to dso_local_equivalent)? This also has the advantage that frontends could also use it for global variables as well as functions.

A potentially more lightweight solution may be providing a way to opt-in to the stricter interpretation. That way, we ensure no existing users are disturbed while not having to add more invasive changes. Do you think the additional complexity a new type of Constant carries its weight if it is only used to support the swift VFE case?

[pcc]

In D108741#3023267, @fhahn wrote:

In D108741#3021933, @pcc wrote:

In D108741#3021793, @kubamracek wrote:

@pcc, could I ask for some details about your last comment? I'm specifically wondering whether you're against proceeding with the change from this review.

Sorry, but I think I'm against it because the mechanism that you've chosen seems like an abuse of the !type metadata, since the metadata is meant to be used as a reference point for accesses relative to it, and not as a way of marking up specific fields by itself. As a more practical concern, it has no way of representing the situation where the pointer at the address point is not eligible for VFE.

Here's one alternative proposal: can we make it so that any vtable slots that are eligible for VFE are represented using a new type of Constant (similar to dso_local_equivalent)? This also has the advantage that frontends could also use it for global variables as well as functions.

A potentially more lightweight solution may be providing a way to opt-in to the stricter interpretation. That way, we ensure no existing users are disturbed while not having to add more invasive changes. Do you think the additional complexity a new type of Constant carries its weight if it is only used to support the swift VFE case?

Adding a new Constant type isn't very difficult, see e.g. D108478

We shouldn't be hesitant to extend the IR in order to model things correctly. And given that we're introducing all these new Constant types it may make sense to refactor to make adding new Constants easier (doesn't need to happen now though). In the end I think more complexity would result from an incorrect modelling (e.g. frontends would have to make up unnecessary type names to cause virtual function slots to be subject to VFE, and what if a frontend wants VFE for globals, or exempt its address points from VFE -- would we need another opt-in for those?).

[kubamracek]

Sorry, I think I managed to confuse myself when I was trying to figure out what VFE actually relies on. It seems that VFE doesn't rely on what I thought it did. Although VFE relies on type metadata, it only relies on it to determine the locations of the address points, and not the locations of the VFE-eligible function slots.

@pcc, I apologize I think I got confused the same way. I think I had the wrong understanding that if any slot in a vtable does not have a matching !type annotation (on the vtable global) with the right offset, it's basically trivially removable by VFE, but apparently, as you're pointing out, that's not the case -- it could still be used by a non-zero offset load via llvm.type.checked.load. In such a case, the slot at (vcall offset + vtable annotation offset) is actually being matched. So even if a vtable slot at offset X is never mentioned in any !type annotation, it could still be matched by any preceding !type type id with a non-zero offset at the call site.

Could you confirm that this understanding I just mentioned is actually correct now? Thanks :)

Here's one alternative proposal: can we make it so that any vtable slots that are eligible for VFE are represented using a new type of Constant (similar to dso_local_equivalent)? This also has the advantage that frontends could also use it for global variables as well as functions.

Just to make sure I understand this proposal, would we *require* frontends to mark all VFE eligible slots with this? I assume the only existing (publicly known) user of VFE is Clang, so as part of the change we'd fix Clang too? And the way this would look on a simple example would be something like the following?

@vtable = internal unnamed_addr constant ... {[
  i8* bitcast (void ()* vfe_eligible @vfunc1 to i8*),
  i8* bitcast (void ()* vfe_eligible @vfunc2 to i8*),
  i8* bitcast (void ()* @non_eligible to i8*)
]}, align 8, !type ...

And in the case of "relative pointers" that Swift uses in its data structures, the Constant would be present at the inner-most reference, like this?

@vtable = internal unnamed_addr constant { [2 x i32] } { [2 x i32] [
  i32 trunc (i64 sub (i64 ptrtoint (void ()* vfe_eligible @vfunc1 to i64), i64 ptrtoint ({ [2 x i32] }* @vtable to i64)) to i32),
  i32 trunc (i64 sub (i64 ptrtoint (void ()* vfe_eligible @vfunc2 to i64), i64 ptrtoint ({ [2 x i32] }* @vtable to i64)) to i32)
]}, align 8, !type ...

[pcc]

In D108741#3026318, @kubamracek wrote:

Sorry, I think I managed to confuse myself when I was trying to figure out what VFE actually relies on. It seems that VFE doesn't rely on what I thought it did. Although VFE relies on type metadata, it only relies on it to determine the locations of the address points, and not the locations of the VFE-eligible function slots.

@pcc, I apologize I think I got confused the same way. I think I had the wrong understanding that if any slot in a vtable does not have a matching !type annotation (on the vtable global) with the right offset, it's basically trivially removable by VFE, but apparently, as you're pointing out, that's not the case -- it could still be used by a non-zero offset load via llvm.type.checked.load. In such a case, the slot at (vcall offset + vtable annotation offset) is actually being matched. So even if a vtable slot at offset X is never mentioned in any !type annotation, it could still be matched by any preceding !type type id with a non-zero offset at the call site.

Could you confirm that this understanding I just mentioned is actually correct now? Thanks :)

Here's one alternative proposal: can we make it so that any vtable slots that are eligible for VFE are represented using a new type of Constant (similar to dso_local_equivalent)? This also has the advantage that frontends could also use it for global variables as well as functions.

Just to make sure I understand this proposal, would we *require* frontends to mark all VFE eligible slots with this? I assume the only existing (publicly known) user of VFE is Clang, so as part of the change we'd fix Clang too? And the way this would look on a simple example would be something like the following?

@vtable = internal unnamed_addr constant ... {[
  i8* bitcast (void ()* vfe_eligible @vfunc1 to i8*),
  i8* bitcast (void ()* vfe_eligible @vfunc2 to i8*),
  i8* bitcast (void ()* @non_eligible to i8*)
]}, align 8, !type ...

And in the case of "relative pointers" that Swift uses in its data structures, the Constant would be present at the inner-most reference, like this?

@vtable = internal unnamed_addr constant { [2 x i32] } { [2 x i32] [
  i32 trunc (i64 sub (i64 ptrtoint (void ()* vfe_eligible @vfunc1 to i64), i64 ptrtoint ({ [2 x i32] }* @vtable to i64)) to i32),
  i32 trunc (i64 sub (i64 ptrtoint (void ()* vfe_eligible @vfunc2 to i64), i64 ptrtoint ({ [2 x i32] }* @vtable to i64)) to i32)
]}, align 8, !type ...

Yes, that's what I was thinking. We'll need to fix Clang, but old bitcode should still work without the optimization because all slots will be considered non-eligible.

[kubamracek]

@pcc, I've updated the diff to introduce a new "vfe_eligible" constant and to also change Clang to start emiting that on vfuncs in vtables.

[fhahn]

In D108741#3025712, @pcc wrote:

In D108741#3023267, @fhahn wrote:

In D108741#3021933, @pcc wrote:

In D108741#3021793, @kubamracek wrote:

@pcc, could I ask for some details about your last comment? I'm specifically wondering whether you're against proceeding with the change from this review.

Sorry, but I think I'm against it because the mechanism that you've chosen seems like an abuse of the !type metadata, since the metadata is meant to be used as a reference point for accesses relative to it, and not as a way of marking up specific fields by itself. As a more practical concern, it has no way of representing the situation where the pointer at the address point is not eligible for VFE.

Here's one alternative proposal: can we make it so that any vtable slots that are eligible for VFE are represented using a new type of Constant (similar to dso_local_equivalent)? This also has the advantage that frontends could also use it for global variables as well as functions.

A potentially more lightweight solution may be providing a way to opt-in to the stricter interpretation. That way, we ensure no existing users are disturbed while not having to add more invasive changes. Do you think the additional complexity a new type of Constant carries its weight if it is only used to support the swift VFE case?

Adding a new Constant type isn't very difficult, see e.g. D108478

Ah right, that indeed looks much less work than I thought, thanks!

[fhahn]

llvm/docs/TypeMetadata.rst

294

IIUC the must here seems to be stronger than it needs to be. Pointers in the vtable *can* be wrapped as vie_eligible to consider them for virtual function elimination. But if they aren't, it is still a valid vtable, right?

[kubamracek]

llvm/docs/TypeMetadata.rst

294

Rephrased.

[kubamracek]

@pcc does this approach look good to you now? Can you review? Thanks :)

[fhahn]

Adding a few additional reviewers to reflect the expanded scope of the patch.

clang/lib/CodeGen/CGVTables.cpp

805 ↗

(On Diff #376989)

It might be better to explain *why* the function pointer is wrapped (to allow virtual function elimination), rather than just state the fact that it is wrapped (which can be seen in the code directly below)

llvm/docs/TypeMetadata.rst

294

Thanks. I think now this could even just be a follow-up paragraph, rather than a list. vfe_eligible is not really a rule to be followed, but something that enables additional optimizations.

llvm/include/llvm/AsmParser/LLParser.h

65 ↗

(On Diff #376989)

Why is this needed? Can this be handled in a similar fashion to how other constants are handled?

llvm/lib/Analysis/ModuleSummaryAnalysis.cpp

518 ↗

(On Diff #376989)

Does this need a new test or is this covered by the existing tests?

[kubamracek]

llvm/lib/Analysis/ModuleSummaryAnalysis.cpp

518 ↗

(On Diff #376989)

Yes, this is a fix because existing LTO tests that attempt VFE were failing after wrapping the vtable pointer in VFEEligibleValue.

[fhahn]

llvm/lib/Analysis/ModuleSummaryAnalysis.cpp

518 ↗

(On Diff #376989)

Hm, I guess what I am missing is where vfe_eligible is added to LTO tests. Looks like none are touched by this patch. Or is this a test involving Clang + LTO optimzations?

[kubamracek]

llvm/include/llvm/AsmParser/LLParser.h

65 ↗

(On Diff #376989)

I don't think it's really needed, I took this approach from https://reviews.llvm.org/D108478. I've just replaced it with the more "local" approach of handling everything in the lltok::kw_vfe_eligible case in LLParser::parseValID.

[kubamracek]

llvm/lib/Analysis/ModuleSummaryAnalysis.cpp

518 ↗

(On Diff #376989)

Exactly, existing Clang LTO tests that use -fvirtual-function-elimination, see CodeGenCXX/vcall-visibility-metadata.cpp in Clang.

[rjmccall]

I don't entirely understand the purpose of vfe_eligible. It sounds like it expresses that it's okay for this value to be replaced if we can prove that nothing ever uses it. Surely that's universally true, albeit usually extremely hard to prove. So maybe the right general approach is that we should be saying something about the v-table object: that we know certain fields in it are only accessed in specially blessed patterns, and then this !type metadata or whatever lets us prove that certain patterns don't exist. I don't know that a new constant is the best way to express that, as opposed to some sort of metadata on the v-table. At the very least, maybe that gives us some direction towards a more general name for the constant.

[kubamracek]

@rjmccall, please see the history of this review, what you're saying was proposed already, and then declined by @pcc, who IIUC was involved in the original design and implementation of VFE, and who's requesting that the right way to express this in the IR is via a new constant that wraps the function pointers. @pcc provided some rationale for that -- do you disagree with it?

[rjmccall]

I did skim the thread, and it seemed to me that Peter's objection was largely to the reuse of !type, which he feels wasn't meant to carry these semantics. Peter leapt to the idea of a new constant instead of a more general metadata, but I don't understand what that leap is meant to achieve, which is why I'm engaging with the thread.

My objection to the new constant is that it doesn't seem to have any independent meaning, it's just a way of identifying particular fields in a global initializer for the purposes of a specific optimization. If you end up with a use of this constant as an instruction operand, it's meaningless and has to be stripped. So I'm not really sure how it reinforces correctness.

As far as I understand it, your optimization is basically: certain global objects have their addresses escape in ways you can't directly reason about, but you know that certain fields of those objects can only be accessed by corresponding blessed operations, and you can sometimes prove that some blessed operations don't exist in the program, which means you can prove that those fields are irrelevant, which enables various optimizations. Within that setup, you really only have one correctness problem, which is that it's vitally important that *accesses* be reliably marked as blessed, which the constant does nothing to address: failing to mark a global object reliably just introduces a failure to optimize, which is not a correctness problem. You also have a *expressiveness* problem, which is that you're treating the entire object uniformly instead of tracking blessed operations field-by-field, which will create correctness problems if you try to apply the optimization to objects which don't restrict access to all the fields. But I don't see how the new constant actually helps there at all; really you need finer-grained "blessings", both on access sites and in the object definition, and the constant doesn't carry those annotations, so...

[kubamracek]

Thank you for the detailed response, @rjmccall ! Let me try to explain my ultimate motivation here :)

I want to implement Virtual Function Elimination (VFE) on methods in classes and subclasses in Swift code, and given that LLVM and Clang already support VFE for C++ and that there's a lot of existing infrastructure for that in LLVM, it seems like an reasonable strategy to reuse all the LLVM IR parts for recognizing vtables and vcall sites and for proving that vtable slots are unused, etc. We "just" need to change the Swift language frontend to mark vtables and vcall sites in the right way so that the existing LLVM VFE logic does the right thing.

This *almost* works, expect for the fact that the Swift frontend embeds pointers to vfunctions inside large data structures, namely nominal type descriptors and full type metadata structs -- i.e. there is no standalone vtable symbol per class (and changing the layout of this in not feasible because it's ABI). Instead, a part of a larger struct is used as a vtable, and the larger struct does actually contain function pointers that are irrelevant to VFE (they're not a vtable slot). But the existing implementation of VFE happily "proves" (incorrectly) that this non-vptr function pointer is unused and removes it.

What I'm concluding from that is that the problem I need to solve is that somehow I need to be able to express in LLVM IR that only the "vtable portion" of the struct should actually participate in VFE, and these vptr-irrelevant references should just not be touched at all when doing VFE. What would be your recommended approach to achieve that? So far, I think these were on the table:

• Reuse !type -- not correct, breaks VFE in C++, as @pcc pointed out.
• Have a new attribute on the global that changes the semantics of !type. I am not sure if this is (a variation of) what you've suggested?
• Use vfe_eligible constants to mark individual entries in the global. Then "not marked" references will not be touched by VFE. Current implementation in this diff.

Or do you think I'm solving the wrong problem? Note that I'm not trying to change anything about how VFE is done today for C++ code.

[rjmccall]

Okay. Thanks for the explanation, I think that was helpful.

I think I have two concerns about how we can use the existing infrastructure for VFE on Swift.

The first is that the existing infrastructure is definitely assuming that the emitted type-checked loads are to static offsets in the global constants you want to optimize. The only flexibility here is that the address point doesn't have to end up being offset zero in the global constant. In Swift, those conditions are only going to be true for pretty narrow cases: the caller needs to be able to lay out the class/protocol fully statically, and the emitter of the class/conformance needs to be emitting the metadata/wtable as a global object rather than an instantiation pattern, which generally means fully non-resilient and non-generic. There are important cases which do look like that, but it's pretty limiting.

The only way around that that I can see is to break the assumption of a static offset. You will need to tie the load to its loadee more symbolically, like by saying that you are conceptually accessing Foo.bar and annotating the field in the global as only accessed through loads tagged Foo.bar. That would get you a certain amount of the optimization, like when a virtual function is never used virtually in the program, and then you can find a way to add in hierarchy analysis to get to parity with what's done for C++ now.

The second is that !type and !vcall_visibility are surprisingly inexpressive. Do you really not to encode the inheritance hierarchy in !type metadata? All that's there right now is compatibility that happens to start at the same offset, which I'm surprised is enough. And !vcall_visibility applies to the entire global constant; you can't say that the parts of a v-table that correspond to a subclass are less visible.

If you don't need to worry about the non-static cases from the first point (which would require major changes), then I would solve your problem by tackling that last section and introducing new metadata which subsumes the information in !type and !vcall_visibility: list out all the regions in the global with explicit identities and address points, where identities describe their extents, super-identities, VFE-ability, and visibility of use.

[kubamracek]

The only way around that that I can see is to break the assumption of a static offset. You will need to tie the load to its loadee more symbolically, like by saying that you are conceptually accessing Foo.bar and annotating the field in the global as only accessed through loads tagged Foo.bar.

Yes, that is exactly the idea. I'm going to tag the loads and the slots with a name of the base class and name of the method (actually it'll be the mangled name of the base method).

That would get you a certain amount of the optimization, like when a virtual function is never used virtually in the program

This is exactly what I'm after, yes.

[kubamracek]

I have talked with @rjmccall offline, and I'm going to attempt to summarize his thought. @rjmccall, please correct me where I' wrong :)

• What feels weird about the current patch (adding the "vfe_eligible" constant) is the fact that in the IR we already have 2 "things" (!type and !vcall_visibility) that are needed for VFE correctness and effectivity, and we're now just adding a third one.

• It would be better to see some sort of consolidation so that *all* the information that VFE needs to know about a vtable is contained in a single "entity", perhaps a new piece of metadata, with a format that is extended to support all the features everyone (Clang, Swift) needs.

• There is at least one interesting opportunity that we should consider and make it expressible in IR: In C++, having a subclass with a more restricted vcall visibility than the base class should allow VFE to optimize a part of the vtable with more precise information. However, that's currently not expressible because there's only one !vcall_visibility on the global.

• The original problem I was trying to solve here can be generalized and tackled together with this C++ vtable expressivity issue: We could extend !vcall_visibility to allow specifying a "range" of offsets in the vtable that the visibility marker applies to, and also allow specifying multiple !vcall_visibility attributes on a single vtable. While this does not achieve the IR design "consolidation", we could perhaps consider that as a intermediate minimally-invasive step in the right direction.

Based on that, I would like to actually propose continuing the IR design discussion on llvm-dev (I'm going to start an email thread on that), while at the same time I'd like to pursue the change of extending !vcall_visibility (add "offset range" to it) to address the immediate problem I need solving for VFE on Swift code. Practically that means !vcall_visibility would accept two formats:

1. !vcall_visibility !{i64 2} -- visibility only
2. !vcall_visibility !{i64 2, i64 0, i64 32} -- visibility, range start, range end

The first form means there is an implicit range that covers the entire vtable.

@pcc, would you be okay with such a direction instead of the suggested vfe_eligible constant? I have changed the diff with an implementation of that.

[fhahn]

IMO this approach is preferable to adding a new type of constant, because it is much more lightweight. The use-case also seems to fit somewhat with the original goals of vcall_visibility, which we already use to determine of the *whole* vtable is safe for VFE. Extending it to also specify which functions are safe for VFE makes sense to me.

It restricts the eligible functions to a single range, which is not as powerful as the new constant approach. Just to double check, will this be sufficient for your use cases?

llvm/include/llvm/Transforms/IPO/GlobalDCE.h

52

Could this subsume VFESafeVTables? IIUC VFuncMap should only contain VTables that are safe for VFE together with the set of functions for which VFE is safe. Maybe also use a more descriptive name, like VFESafeVTablesAndFns.

llvm/lib/Transforms/IPO/GlobalDCE.cpp

126

nit: you can just use cast instead of dyn_cast and get rid of the assert; cast will assert if the result is null.

128

nit: just return VFuncMap[VTable].contains(VPtr)?

248

Is this callback here really necessary or could it be in FindVirtualFunctionsInVTable? It seems to make it harder to see what's going on when reading FindVirtualFunctionsInVTable in isolation.

llvm/test/Transforms/GlobalDCE/virtual-functions-non-vfunc-entries.ll

34

we should also have a test with a start offset different than 0.

[rjmccall]

@rjmccall, please correct me where I'm wrong :)

No, I think that accurately summarizes our conversation. Thanks!

[kubamracek]

It restricts the eligible functions to a single range, which is not as powerful as the new constant approach. Just to double check, will this be sufficient for your use cases?

Yes, I just double checked, all the data structures that Swift should apply VFE to do have a consecutive range that is "the vtable region" inside it, so being able to express a range in !vcall_visibility will cover the needs for the Swift compiler.

Could this subsume VFESafeVTables?

Updated diff to do that.

we should also have a test with a start offset different than 0.

Added.

[kubamracek]

Is this callback here really necessary or could it be in FindVirtualFunctionsInVTable? It seems to make it harder to see what's going on when reading FindVirtualFunctionsInVTable in isolation.

Removed the callback.

[fhahn]

llvm/docs/TypeMetadata.rst

296

might be good to spell out that the range is a half-open (< end)

llvm/include/llvm/IR/GlobalObject.h

141

nit: could just use std::pair?

llvm/include/llvm/Transforms/IPO/GlobalDCE.h

52

nit: I think it would be good to include some of the original wording, saying that contains global variables which are vtables for which we have enough information to safely do VFE, together with the functions in the vtable for which VFE is safe.

llvm/lib/IR/Metadata.cpp

1546

it would be good to have a the IR verifier check that the second and third operands are integer constants < UINT64_MAX.

1551

nit: consider using the more C++ like std::numeric_limits<uint64_t>::max()

llvm/lib/Transforms/IPO/GlobalDCE.cpp

129–130

nit: re-flow comment.

130–135

nit: should we use find to look up GVU here to avoid inserting new entries in the map?

169

nit: I think usually {} are omitted for single-line bodies.

184

could we use getPointerAtOffset here and below instead of recursing further? That way we would only add function pointers that fit the supported Vtable scheme and we should be able to avoid handling arbitrary constants by iterating over their operands, which might lead us to discover function pointers that are not valid VTable entries.

llvm/test/Transforms/GlobalDCE/virtual-functions-non-vfunc-entries.ll

6

It might be good to also have a test with a relative pointer vtable

[kubamracek]

Updated diff, should have all comments addressed, added a test for relative pointer vtable.

could we use getPointerAtOffset here and below instead of recursing further? That way we would only add function pointers that fit the supported Vtable scheme and we should be able to avoid handling arbitrary constants by iterating over their operands, which might lead us to discover function pointers that are not valid VTable entries.

This feels like a weird restriction, and also I think we do need to support arrays/structs in other arrays/structs, so recursing seem like the only option here? The case of a sub(@fn1, @fn2) expression seems like not worth protecting against (it's not a "reasonable" valid relative pointer, and arguably it's not even clear whether it should or shouldn't be considered for VFE).

[fhahn]

This approach LGTM and I think it should address the original concerns raised by @pcc.

Please wait with committing until next week, in case @pcc has additional concerns about the new approach.

llvm/lib/IR/Verifier.cpp

757

thanks for adding the verifier! It would be good to have a couple of tests for it too

llvm/lib/Transforms/IPO/GlobalDCE.cpp

237

nit: sink inside if?

[pcc]

Thanks, something like this seems reasonable to me and I don't have any major issues with it.

I would still like to take this opportunity to drop the special case for Functions. Can we make it so that !vcall_visibility with a single operand means that none of the constant has the given visibility, and teach Clang to emit the correct ranges? I think this will also require supporting more than one !vcall_visibility range per global (this could be done by accommodating more than one !vcall_visibility annotation, or allowing the single annotation to have 2n+1 operands).

[kubamracek]

I would still like to take this opportunity to drop the special case for Functions. Can we make it so that !vcall_visibility with a single operand means that none of the constant has the given visibility, and teach Clang to emit the correct ranges? I think this will also require supporting more than one !vcall_visibility range per global (this could be done by accommodating more than one !vcall_visibility annotation, or allowing the single annotation to have 2n+1 operands).

Could you expand on what you mean by "drop the special case for Functions"? Is my understanding that it's a *separate* request from Clang emitting correct ranges?

[rjmccall]

I think Peter is saying that if you can make Clang emit correct ranges for v-tables — specifically so that the ranges don't cover the type_info pointer, which we don't emit enough metadata to safely remove — then you can also go ahead and remove the special case where we only eliminate loads of function pointers. That's assuming we don't need to support old bitcode.

[kubamracek]

I think Peter is saying that if you can make Clang emit correct ranges for v-tables — specifically so that the ranges don't cover the type_info pointer, which we don't emit enough metadata to safely remove — then you can also go ahead and remove the special case where we only eliminate loads of function pointers. That's assuming we don't need to support old bitcode.

Makes sense, thanks for the explanation. @pcc, just to make sure I'm on the same page as you -- this special casing of Functions is already there in GlobalDCE today, correct? The patch as is right now is not adding a new restriction, or regressing the existing behavior, correct?

[fhahn]

In D108741#3098725, @rjmccall wrote:

I think Peter is saying that if you can make Clang emit correct ranges for v-tables — specifically so that the ranges don't cover the type_info pointer, which we don't emit enough metadata to safely remove — then you can also go ahead and remove the special case where we only eliminate loads of function pointers. That's assuming we don't need to support old bitcode.

Can we auto-upgrade the bitcode, moving the logic to detect the special case in the IR upgrader? IIUC the worst case would be that we won't be able to optimise old bitcode, so it wouldn't be the end of the world. But if we can auto-upgrade to vcall_visibility then we should do it I think.

But I don't think we should pull this into this particular patch. I saw @kubamracek already put up D112929 and I think the rest of the cleanups (removing the special handling for VFE) should be done as follow-up patches, to avoid making the patch at hand even bigger.

[kubamracek]

But I don't think we should pull this into this particular patch. I saw @kubamracek already put up D112929 and I think the rest of the cleanups (removing the special handling for VFE) should be done as follow-up patches, to avoid making the patch at hand even bigger.

Right, I was planning to submit all the remainders as separate patches, and hopefully merge individual parts as long as they don't regress anything (like this one).

[kubamracek]

• https://reviews.llvm.org/D112965 [GlobalDCE][IR] Allow and support multiple !vcall_visibility ranges
• https://reviews.llvm.org/D112929 [Clang] For VFE, emit vtable ranges in !vcall_visibility metadata
• https://reviews.llvm.org/D112967 [GlobalDCE] Precisely account for visibility when multiple !vcall_visibility ranges are present on vtables

[kubamracek]

@pcc , @rjmccall , @fhahn See the other phabricator links -- I assume it might take a while to review and iterate on this. Would it be reasonable to merge *this* change in the meantime?

llvm/docs/TypeMetadata.rst

* - 2
      - **Translation Unit**
            All virtual function calls which might use this vtable are in the
            current module.
 
 In addition, all function pointer loads from a vtable marked with the
 ``!vcall_visibility`` metadata (with a non-zero value) must be done using the
 :ref:`llvm.type.checked.load <type.checked.load>` intrinsic, so that virtual
 calls sites can be correlated with the vtables which they might load from.
 Other parts of the vtable (RTTI, offset-to-top, ...) can still be accessed with
 normal loads.
+
+Alternatively, the ``!vcall_visibility`` metadata attachment can have an
+extended format of a tuple with two additional integer values representing the
+begin and end offset (a half-open range, the begin offset is included, the end
+offset is excluded) within the vtable that the visibility applies to. When the
+range is missing, the meaning is the same as a range covering the entire vtable.
+Any part of the vtable that is not covered by the specified range is not
+eligible for elimination of virtual functions.

llvm/include/llvm/IR/GlobalObject.h

public:
   using Value::setMetadata;
 
   /// Copy metadata from Src, adjusting offsets by Offset.
   void copyMetadata(const GlobalObject *Src, unsigned Offset);
 
   void addTypeMetadata(unsigned Offset, Metadata *TypeID);
   void setVCallVisibilityMetadata(VCallVisibility Visibility);
   VCallVisibility getVCallVisibility() const;
+  std::pair<uint64_t, uint64_t> getVTableOffsetRange() const;
 
   /// Returns true if the alignment of the value can be unilaterally
   /// increased.
   ///
   /// Note that for functions this is the alignment of the code, not the
   /// alignment of a function pointer.
   bool canIncreaseAlignment() const;
 

llvm/include/llvm/Transforms/IPO/GlobalDCE.h

private:
 
   /// Comdat -> Globals in that Comdat section.
   std::unordered_multimap<Comdat *, GlobalValue *> ComdatMembers;
 
   /// !type metadata -> set of (vtable, offset) pairs
   DenseMap<Metadata *, SmallSet<std::pair<GlobalVariable *, uint64_t>, 4>>
       TypeIdMap;
 
-  // Global variables which are vtables, and which we have enough information
-  // about to safely do dead virtual function elimination.
-  SmallPtrSet<GlobalValue *, 32> VFESafeVTables;
+  /// VTable -> set of vfuncs. This only contains vtables for which we have
+  /// enough information to safely do dead virtual function elimination, and
+  /// only contains vfuncs that are within the range specified in
+  /// !vcall_visibility).
+  DenseMap<GlobalValue *, SmallPtrSet<GlobalValue *, 8>> VFESafeVTablesAndFns;
 
   void UpdateGVDependencies(GlobalValue &GV);
   void MarkLive(GlobalValue &GV,
                 SmallVectorImpl<GlobalValue *> *Updates = nullptr);
   bool RemoveUnusedGlobalValue(GlobalValue &GV);
 
   // Dead virtual function elimination.
   void AddVirtualFunctionDependencies(Module &M);

llvm/lib/IR/Metadata.cpp

uint64_t Val = cast<ConstantInt>(
                        cast<ConstantAsMetadata>(MD->getOperand(0))->getValue())
                        ->getZExtValue();
     assert(Val <= 2 && "unknown vcall visibility!");
     return (VCallVisibility)Val;
   }
   return VCallVisibility::VCallVisibilityPublic;
 }
 
+std::pair<uint64_t, uint64_t> GlobalObject::getVTableOffsetRange() const {
+  if (MDNode *MD = getMetadata(LLVMContext::MD_vcall_visibility)) {
+    if (MD->getNumOperands() >= 3) {
+      uint64_t RangeStart =
+          cast<ConstantInt>(
+              cast<ConstantAsMetadata>(MD->getOperand(1))->getValue())
+              ->getZExtValue();
+      uint64_t RangeEnd =
+          cast<ConstantInt>(
+              cast<ConstantAsMetadata>(MD->getOperand(2))->getValue())
+              ->getZExtValue();
+      return std::make_pair(RangeStart, RangeEnd);
+    }
+  }
+  return std::make_pair(0, std::numeric_limits<uint64_t>::max());
+}
+
 void Function::setSubprogram(DISubprogram *SP) {
   setMetadata(LLVMContext::MD_dbg, SP);
 }
 
 DISubprogram *Function::getSubprogram() const {
   return cast_or_null<DISubprogram>(getMetadata(LLVMContext::MD_dbg));
 }
 

llvm/lib/IR/Verifier.cpp

void Verifier::visitGlobalVariable(const GlobalVariable &GV) {
   for (auto *MD : MDs) {
     if (auto *GVE = dyn_cast<DIGlobalVariableExpression>(MD))
       visitDIGlobalVariableExpression(*GVE);
     else
       AssertDI(false, "!dbg attachment of global variable must be a "
                       "DIGlobalVariableExpression");
   }
 
+  MDs.clear();
+  GV.getMetadata(LLVMContext::MD_vcall_visibility, MDs);
+  for (auto *MD : MDs) {
+    Assert(MD->getNumOperands() >= 1, "bad !vcall_visibility attachment");
+    Assert(isa<ConstantAsMetadata>(MD->getOperand(0)),
+           "bad !vcall_visibility attachment");
+    auto *Op0Val = cast<ConstantAsMetadata>(MD->getOperand(0))->getValue();
+    Assert(isa<ConstantInt>(Op0Val), "bad !vcall_visibility attachment");
+    auto Op0Int = cast<ConstantInt>(Op0Val)->getValue();
+    Assert(Op0Int.uge(0) && Op0Int.ult(std::numeric_limits<uint64_t>::max()),
+           "bad !vcall_visibility attachment");
+    if (MD->getNumOperands() == 3) {
+      Assert(isa<ConstantAsMetadata>(MD->getOperand(1)),
+             "bad !vcall_visibility attachment");
+      auto *Op1Val = cast<ConstantAsMetadata>(MD->getOperand(1))->getValue();
+      Assert(isa<ConstantInt>(Op1Val), "bad !vcall_visibility attachment");
+      auto Op1Int = cast<ConstantInt>(Op1Val)->getValue();
+      Assert(Op1Int.uge(0) && Op1Int.ult(std::numeric_limits<uint64_t>::max()),
+             "bad !vcall_visibility attachment");
+
+      Assert(isa<ConstantAsMetadata>(MD->getOperand(2)),
+             "bad !vcall_visibility attachment");
+      auto *Op2Val = cast<ConstantAsMetadata>(MD->getOperand(2))->getValue();
+      Assert(isa<ConstantInt>(Op2Val), "bad !vcall_visibility attachment");
+      auto Op2Int = cast<ConstantInt>(Op2Val)->getValue();
+      Assert(Op2Int.uge(0) && Op2Int.ult(std::numeric_limits<uint64_t>::max()),
+             "bad !vcall_visibility attachment");
+
+      Assert(Op1Int.ule(Op2Int), "bad !vcall_visibility attachment");
+    } else {
+      Assert(MD->getNumOperands() == 1, "bad !vcall_visibility attachment");
+    }
+  }
+
   // Scalable vectors cannot be global variables, since we don't know
   // the runtime size. If the global is an array containing scalable vectors,
   // that will be caught by the isValidElementType methods in StructType or
   // ArrayType instead.
   Assert(!isa<ScalableVectorType>(GV.getValueType()),
          "Globals cannot contain scalable vectors", &GV);
 
   if (auto *STy = dyn_cast<StructType>(GV.getValueType()))

llvm/lib/Transforms/IPO/GlobalDCE.cpp

if (Where != ConstantDependenciesCache.end()) {
         ComputeDependencies(CEUser, LocalDeps);
       Deps.insert(LocalDeps.begin(), LocalDeps.end());
     }
   }
 }
 
 void GlobalDCEPass::UpdateGVDependencies(GlobalValue &GV) {
   SmallPtrSet<GlobalValue *, 8> Deps;
   for (User *User : GV.users())
     ComputeDependencies(User, Deps);
   Deps.erase(&GV); // Remove self-reference.
   for (GlobalValue *GVU : Deps) {
-    // If this is a dep from a vtable to a virtual function, and we have
-    // complete information about all virtual call sites which could call
-    // though this vtable, then skip it, because the call site information will
-    // be more precise.
-    if (VFESafeVTables.count(GVU) && isa<Function>(&GV)) {
+    // If this is a dep from a vtable to a virtual function, and it's within the
+    // range specified in !vcall_visibility, and we have complete information
+    // about all virtual call sites which could call though this vtable, then
+    // skip it, because the call site information will be more precise.
+    if (isa<Function>(&GV) && VFESafeVTablesAndFns.count(GVU) &&
+        VFESafeVTablesAndFns[GVU].contains(&GV)) {
       LLVM_DEBUG(dbgs() << "Ignoring dep " << GVU->getName() << " -> "
                         << GV.getName() << "\n");
       continue;
     }
     GVDependencies[GVU].insert(&GV);
   }
 }
 
 /// Mark Global value as Live
 void GlobalDCEPass::MarkLive(GlobalValue &GV,
                              SmallVectorImpl<GlobalValue *> *Updates) {
   auto const Ret = AliveGlobals.insert(&GV);
   if (!Ret.second)
     return;
 
   if (Updates)
     Updates->push_back(&GV);
   if (Comdat *C = GV.getComdat()) {
     for (auto &&CM : make_range(ComdatMembers.equal_range(C))) {
       MarkLive(*CM.second, Updates); // Recursion depth is only two because only
                                      // globals in the same comdat are visited.
     }
   }
 }
 
+/// Recursively iterate over the (sub-)constants in the vtable and look for
+/// vptrs, if their offset is within [RangeStart..RangeEnd), add them to VFuncs.
+static void FindVirtualFunctionsInVTable(Module &M, Constant *C,
+                                         uint64_t RangeStart, uint64_t RangeEnd,
+                                         SmallPtrSet<GlobalValue *, 8> *VFuncs,
+                                         uint64_t BaseOffset = 0) {
+  if (auto *GV = dyn_cast<GlobalValue>(C)) {
+    if (auto *F = dyn_cast<Function>(GV))
+      if (RangeStart <= BaseOffset && BaseOffset < RangeEnd)
+        VFuncs->insert(F);
+
+    // Do not recurse outside of the current global.
+    return;
+  }
+
+  if (auto *S = dyn_cast<ConstantStruct>(C)) {
+    StructType *STy = dyn_cast<StructType>(S->getType());
+    const StructLayout *SL = M.getDataLayout().getStructLayout(STy);
+    for (auto EI : llvm::enumerate(STy->elements())) {
+      auto Offset = SL->getElementOffset(EI.index());
+      unsigned Op = SL->getElementContainingOffset(Offset);
+      FindVirtualFunctionsInVTable(M, cast<Constant>(S->getOperand(Op)),
+                                   RangeStart, RangeEnd, VFuncs,
+                                   BaseOffset + Offset);
+    }
+  } else if (auto *A = dyn_cast<ConstantArray>(C)) {
+    ArrayType *ATy = A->getType();
+    auto EltSize = M.getDataLayout().getTypeAllocSize(ATy->getElementType());
+    for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) {
+      FindVirtualFunctionsInVTable(M, cast<Constant>(A->getOperand(i)),
+                                   RangeStart, RangeEnd, VFuncs,
+                                   BaseOffset + EltSize * i);
+    }
+  } else {
+    for (auto &Op : C->operands()) {
+      FindVirtualFunctionsInVTable(M, cast<Constant>(Op), RangeStart, RangeEnd,
+                                   VFuncs, BaseOffset);
+    }
+  }
+}
+
 void GlobalDCEPass::ScanVTables(Module &M) {
   SmallVector<MDNode *, 2> Types;
   LLVM_DEBUG(dbgs() << "Building type info -> vtable map\n");
 
   auto *LTOPostLinkMD =
       cast_or_null<ConstantAsMetadata>(M.getModuleFlag("LTOPostLink"));
   bool LTOPostLink =
       LTOPostLinkMD &&
       (cast<ConstantInt>(LTOPostLinkMD->getValue())->getZExtValue() != 0);
 
   for (GlobalVariable &GV : M.globals()) {
     Types.clear();
     GV.getMetadata(LLVMContext::MD_type, Types);
     if (GV.isDeclaration() || Types.empty())
       continue;
 
     // Use the typeid metadata on the vtable to build a mapping from typeids to
     // the list of (GV, offset) pairs which are the possible vtables for that
     // typeid.
     for (MDNode *Type : Types) {
       Metadata *TypeID = Type->getOperand(1).get();
 
       uint64_t Offset =
           cast<ConstantInt>(
               cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
               ->getZExtValue();
 
       TypeIdMap[TypeID].insert(std::make_pair(&GV, Offset));
     }
 
     // If the type corresponding to the vtable is private to this translation
     // unit, we know that we can see all virtual functions which might use it,
     // so VFE is safe.
     if (auto GO = dyn_cast<GlobalObject>(&GV)) {
       GlobalObject::VCallVisibility TypeVis = GO->getVCallVisibility();
       if (TypeVis == GlobalObject::VCallVisibilityTranslationUnit ||
           (LTOPostLink &&
            TypeVis == GlobalObject::VCallVisibilityLinkageUnit)) {
         LLVM_DEBUG(dbgs() << GV.getName() << " is safe for VFE\n");
-        VFESafeVTables.insert(&GV);
+
+        // Find and record all the vfunctions that are within the offset range
+        // specified in the !vcall_visibility attribute.
+        auto Range = GO->getVTableOffsetRange();
+        SmallPtrSet<GlobalValue *, 8> VFuncs;
+        FindVirtualFunctionsInVTable(M, GV.getInitializer(), std::get<0>(Range),
+                                     std::get<1>(Range), &VFuncs);
+        VFESafeVTablesAndFns[&GV] = VFuncs;
       }
     }
   }
 }
 
 void GlobalDCEPass::ScanVTableLoad(Function *Caller, Metadata *TypeId,
                                    uint64_t CallOffset) {
   for (auto &VTableInfo : TypeIdMap[TypeId]) {
     GlobalVariable *VTable = VTableInfo.first;
     uint64_t VTableOffset = VTableInfo.second;
 
     Constant *Ptr =
         getPointerAtOffset(VTable->getInitializer(), VTableOffset + CallOffset,
                            *Caller->getParent(), VTable);
     if (!Ptr) {
       LLVM_DEBUG(dbgs() << "can't find pointer in vtable!\n");
-      VFESafeVTables.erase(VTable);
+      VFESafeVTablesAndFns.erase(VTable);
       return;
     }
 
     auto Callee = dyn_cast<Function>(Ptr->stripPointerCasts());
     if (!Callee) {
       LLVM_DEBUG(dbgs() << "vtable entry is not function pointer!\n");
-      VFESafeVTables.erase(VTable);
+      VFESafeVTablesAndFns.erase(VTable);
       return;
     }
 
     LLVM_DEBUG(dbgs() << "vfunc dep " << Caller->getName() << " -> "
                       << Callee->getName() << "\n");
     GVDependencies[Caller].insert(Callee);
   }
 }
for (auto U : TypeCheckedLoadFunc->users()) {
     auto *TypeId = cast<MetadataAsValue>(TypeIdValue)->getMetadata();
 
     if (Offset) {
       ScanVTableLoad(CI->getFunction(), TypeId, Offset->getZExtValue());
     } else {
       // type.checked.load with a non-constant offset, so assume every entry in
       // every matching vtable is used.
       for (auto &VTableInfo : TypeIdMap[TypeId]) {
-        VFESafeVTables.erase(VTableInfo.first);
+        VFESafeVTablesAndFns.erase(VTableInfo.first);
       }
     }
   }
 }
 
 void GlobalDCEPass::AddVirtualFunctionDependencies(Module &M) {
   if (!ClEnableVFE)
     return;
 
   // If the Virtual Function Elim module flag is present and set to zero, then
   // the vcall_visibility metadata was inserted for another optimization (WPD)
   // and we may not have type checked loads on all accesses to the vtable.
   // Don't attempt VFE in that case.
   auto *Val = mdconst::dyn_extract_or_null<ConstantInt>(
       M.getModuleFlag("Virtual Function Elim"));
   if (!Val || Val->getZExtValue() == 0)
     return;
 
   ScanVTables(M);
 
-  if (VFESafeVTables.empty())
+  if (VFESafeVTablesAndFns.empty())
     return;
 
   ScanTypeCheckedLoadIntrinsics(M);
 
-  LLVM_DEBUG(
-    dbgs() << "VFE safe vtables:\n";
-    for (auto *VTable : VFESafeVTables)
-      dbgs() << "  " << VTable->getName() << "\n";
-  );
+  LLVM_DEBUG(dbgs() << "VFE safe vtables:\n";
+             for (auto &Entry
+                  : VFESafeVTablesAndFns) dbgs()
+             << "  " << Entry.first->getName() << "\n";);
 }
 
 PreservedAnalyses GlobalDCEPass::run(Module &M, ModuleAnalysisManager &MAM) {
   bool Changed = false;
 
   // The algorithm first computes the set L of global variables that are
   // trivially live.  Then it walks the initialization of these variables to
   // compute the globals used to initialize them, which effectively builds a
for (GlobalIFunc *GIF : DeadIFuncs)
     EraseUnusedGlobalValue(GIF);
 
   // Make sure that all memory is released
   AliveGlobals.clear();
   ConstantDependenciesCache.clear();
   GVDependencies.clear();
   ComdatMembers.clear();
   TypeIdMap.clear();
-  VFESafeVTables.clear();
+  VFESafeVTablesAndFns.clear();
 
   if (Changed)
     return PreservedAnalyses::none();
   return PreservedAnalyses::all();
 }
 
 // RemoveUnusedGlobalValue - Loop over all of the uses of the specified
 // GlobalValue, looking for the constant pointer ref that may be pointing to it.

llvm/test/Transforms/GlobalDCE/virtual-functions-non-vfunc-entries.ll

+; RUN: opt < %s -globaldce -S | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+declare { i8*, i1 } @llvm.type.checked.load(i8*, i32, metadata)
+
+; A vtable that contains a non-nfunc entry, @regular_non_virtual_funcA, but
+; without a range specific in !vcall_visibility, which means *all* function
+; pointers are eligible for VFE, so GlobalDCE will treat the
+; @regular_non_virtual_funcA slot as eligible for VFE, and remove it.
+@vtableA = internal unnamed_addr constant { [3 x i8*] } { [3 x i8*] [
+  i8* bitcast (void ()* @vfunc1_live to i8*),
+  i8* bitcast (void ()* @vfunc2_dead to i8*),
+  i8* bitcast (void ()* @regular_non_virtual_funcA to i8*)
+]}, align 8, !type !{i64 0, !"vfunc1.type"}, !type !{i64 8, !"vfunc2.type"}, !vcall_visibility !{i64 2}
+
+; CHECK:      @vtableA = internal unnamed_addr constant { [3 x i8*] } { [3 x i8*] [
+; CHECK-SAME:   i8* bitcast (void ()* @vfunc1_live to i8*),
+; CHECK-SAME:   i8* null,
+; CHECK-SAME:   i8* null
+; CHECK-SAME: ] }, align 8
+
+
+; A vtable that contains a non-nfunc entry, @regular_non_virtual_funcB, with a
+; range of [0,16) which means only the first two entries are eligible for VFE.
+; GlobalDCE should keep @regular_non_virtual_funcB in the vtable.
+@vtableB = internal unnamed_addr constant { [3 x i8*] } { [3 x i8*] [
+  i8* bitcast (void ()* @vfunc1_live to i8*),
+  i8* bitcast (void ()* @vfunc2_dead to i8*),
+  i8* bitcast (void ()* @regular_non_virtual_funcB to i8*)
+]}, align 8, !type !{i64 0, !"vfunc1.type"}, !type !{i64 8, !"vfunc2.type"}, !vcall_visibility !{i64 2, i64 0, i64 16}
+
+; CHECK:      @vtableB = internal unnamed_addr constant { [3 x i8*] } { [3 x i8*] [
+; CHECK-SAME:   i8* bitcast (void ()* @vfunc1_live to i8*),
+; CHECK-SAME:   i8* null,
+; CHECK-SAME:   i8* bitcast (void ()* @regular_non_virtual_funcB to i8*)
+; CHECK-SAME: ] }, align 8
+
+; A vtable that contains a non-nfunc entry, @regular_non_virtual_funcB, with a
+; range of [0,16) which means only the first two entries are eligible for VFE.
+; GlobalDCE should keep @regular_non_virtual_funcB in the vtable.
+@vtableC = internal unnamed_addr constant { [3 x i8*] } { [3 x i8*] [
+  i8* bitcast (void ()* @regular_non_virtual_funcC to i8*),
+  i8* bitcast (void ()* @vfunc1_live to i8*),
+  i8* bitcast (void ()* @vfunc2_dead to i8*)
+]}, align 8, !type !{i64 8, !"vfunc1.type"}, !type !{i64 16, !"vfunc2.type"}, !vcall_visibility !{i64 2, i64 8, i64 24}
+
+; CHECK:      @vtableC = internal unnamed_addr constant { [3 x i8*] } { [3 x i8*] [
+; CHECK-SAME:   i8* bitcast (void ()* @regular_non_virtual_funcC to i8*),
+; CHECK-SAME:   i8* bitcast (void ()* @vfunc1_live to i8*),
+; CHECK-SAME:   i8* null
+; CHECK-SAME: ] }, align 8
+
+; A vtable with "relative pointers"
+@vtableD = internal unnamed_addr constant { i32, i32, i8* } {
+  i32 trunc (i64 sub (i64 ptrtoint (void ()* @vfunc1_live              to i64), i64 ptrtoint ({ i32, i32, i8* }* @vtableD to i64)) to i32),
+  i32 trunc (i64 sub (i64 ptrtoint (void ()* @vfunc2_dead              to i64), i64 ptrtoint ({ i32, i32, i8* }* @vtableD to i64)) to i32),
+  i8* bitcast (void ()* @regular_non_virtual_funcD to i8*)
+}, align 8, !type !{i64 0, !"vfunc1.type"}, !type !{i64 4, !"vfunc2.type"}, !vcall_visibility !{i64 2, i64 0, i64 8}
+
+; CHECK:      @vtableD = internal unnamed_addr constant { i32, i32, i8* } {
+; CHECK-SAME:   i32 trunc (i64 sub (i64 ptrtoint (void ()* @vfunc1_live              to i64), i64 ptrtoint ({ i32, i32, i8* }* @vtableD to i64)) to i32),
+; CHECK-SAME:   i32 0,
+; CHECK-SAME:   i8* bitcast (void ()* @regular_non_virtual_funcD to i8*)
+; CHECK-SAME: }, align 8
+
+; (1) vfunc1_live is referenced from @main, stays alive
+define internal void @vfunc1_live() {
+  ; CHECK: define internal void @vfunc1_live(
+  ret void
+}
+
+; (2) vfunc2_dead is never referenced, gets removed and vtable slot is null'd
+define internal void @vfunc2_dead() {
+  ; CHECK-NOT: define internal void @vfunc2_dead(
+  ret void
+}
+
+; (3) not using a range in !vcall_visibility, global gets removed
+define internal void @regular_non_virtual_funcA() {
+  ; CHECK-NOT: define internal void @regular_non_virtual_funcA(
+  ret void
+}
+
+; (4) using a range in !vcall_visibility, pointer is outside of range, so should
+; stay alive
+define internal void @regular_non_virtual_funcB() {
+  ; CHECK: define internal void @regular_non_virtual_funcB(
+  ret void
+}
+
+; (5) using a range in !vcall_visibility, pointer is outside of range, so should
+; stay alive
+define internal void @regular_non_virtual_funcC() {
+  ; CHECK: define internal void @regular_non_virtual_funcC(
+  ret void
+}
+
+; (6) using a range in !vcall_visibility, pointer is outside of range, so should
+; stay alive
+define internal void @regular_non_virtual_funcD() {
+  ; CHECK: define internal void @regular_non_virtual_funcD(
+  ret void
+}
+
+define void @main() {
+  %1 = ptrtoint { [3 x i8*] }* @vtableA to i64 ; to keep @vtableA alive
+  %2 = ptrtoint { [3 x i8*] }* @vtableB to i64 ; to keep @vtableB alive
+  %3 = ptrtoint { [3 x i8*] }* @vtableC to i64 ; to keep @vtableC alive
+  %4 = ptrtoint { i32, i32, i8* }* @vtableD to i64 ; to keep @vtableD alive
+  %5 = tail call { i8*, i1 } @llvm.type.checked.load(i8* null, i32 0, metadata !"vfunc1.type")
+  ret void
+}
+
+!999 = !{i32 1, !"Virtual Function Elim", i32 1}
+!llvm.module.flags = !{!999}

llvm/test/Verifier/vcall-visibility.ll

+; RUN: not opt -S -verify < %s 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; vcall_visibility must have either 1 or 3 operands
+@vtableA = internal unnamed_addr constant { [1 x i8*] } { [1 x i8*] [i8* null]}, align 8, !vcall_visibility !{i64 2, i64 42}
+; CHECK: bad !vcall_visibility attachment
+
+; range start cannot be greater than range end
+@vtableB = internal unnamed_addr constant { [1 x i8*] } { [1 x i8*] [i8* null]}, align 8, !vcall_visibility !{i64 2, i64 10, i64 8}
+; CHECK: bad !vcall_visibility attachment
+
+; vcall_visibility range cannot be over 64 bits
+@vtableC = internal unnamed_addr constant { [1 x i8*] } { [1 x i8*] [i8* null]}, align 8, !vcall_visibility !{i64 2, i128 0, i128 9223372036854775808000}
+; CHECK: bad !vcall_visibility attachment
+
+; range must be two integers
+@vtableD = internal unnamed_addr constant { [1 x i8*] } { [1 x i8*] [i8* null]}, align 8, !vcall_visibility !{i64 2, i64 0, !"string"}
+; CHECK: bad !vcall_visibility attachment