Devirtualize a call on alloca without waiting for post inline cleanup and next DevirtSCCRepeatedPass iteration.

[hjyamauchi]

Summary

This aims to fix a missed inlining case.

If there's a virtual call in the callee on an alloca (stack allocated object) in
the caller, and the callee is inlined into the caller, the post-inline cleanup
would devirtualize the virtual call, but if the next iteration of
DevirtSCCRepeatedPass doesn't happen (under the new pass manager), which is
based on a heuristic to determine whether to reiterate, we may miss inlining the
devirtualized call.

This enables inlining in clang/test/CodeGenCXX/member-function-pointer-calls.cpp.

[hjyamauchi]

https://godbolt.org/z/c3mhnQ

[davidxl]

In this case (shown in godbot), why does PM decides to not iterate another round?

[hjyamauchi]

In D69591#1728018, @davidxl wrote:

In this case (shown in godbot), why does PM decides to not iterate another round?

DevirtSCCRepeatedPass uses the following heuristic to decide whether to reiterate:

1. It memorizes the indirect calls in the function body before one iteration. After the iteration, check if any of those indirect calls became direct. If so, reiterate.
2. It counts the numbers of the direct calls and the indirect calls before one iteration. After the iteration, count gain. If the number of indirect calls decreased and the number of direct calls increased, reiterate.

Neither applies here because

1. The virtual call in question isn't seen as a virtual call by DevirtSCCRepeatedPass because it appears after inlining and gets devirtualized during cleanup right after. DevirtSCCRepeatedPass only looks at the code before and after the whole inlining + cleanup pipeline.

2. Also, the numbers of direct/indirect calls in this case are 2/0 before and 2/0 after. So, it doesn't kick in, either.

[hjyamauchi]

An old mailing list thread about a related issue: http://lists.llvm.org/pipermail/llvm-dev/2017-December/thread.html#119598. I checked that this patch also fixes the example cited there: https://godbolt.org/z/BP0jGT

An alternative idea from there is "to pass the value handles to the inliner through CGSCCUpdateResult and let the inliner augment it as the caller gets indirect calls due to inlining."
I think that would work. We can add to the list of indirect calls as we inline and find indirect calls (where this patch calls tryPromoteCall()) and then DevirtSCCRepeatedPass would check if any of the indirect call has become direct after the iteration. This would be a more general and yet precise approach to these cases.

Another from there is to repeat DevirtSCCRepeatedPass until a fix point. I think that would fix these cases, but as the DevirtSCCRepeatedPass termination is based on a heuristic (described above) and currently likely not repeated to a fix point, it may have other broader impact like potentially inlining a lot more, and increasing compile time. To detect a fix point, we'd need some way to communicate that sort of like the above CGSCCUpdateResult approach.

[hjyamauchi]

It turned out the approach of "to pass the value handles to the inliner through CGSCCUpdateResult and let the inliner augment it as the caller gets indirect calls due to inlining" won't work because the instcombine that turns the indirect call into a direct call creates a new call instruction rather than updating the existing call instruction, which the value handle can't keep track of.

https://reviews.llvm.org/D70147 attempts to implement the approach that repeats DevirtSCCRepeatedPass as long as new inlining happens (up to the existing max count).

[davidxl]

llvm/lib/Analysis/Loads.cpp

458 ↗

(On Diff #226982)

what is the change intended for? If it fixes some bugs, it should be split out.

llvm/lib/Transforms/IPO/Inliner.cpp

897

The pattern recognition part can be extracted as a utility/helper function and put int perhaps IndirectCallPromotionAnalysis.h|cpp file.

[hjyamauchi]

llvm/lib/Analysis/Loads.cpp

458 ↗

(On Diff #226982)

If AA were available (not null), this code wouldn't be necessary as it can handle the general AA. However, in the new code in Inliner.cpp, we currently call this function (FindAvailableLoadedValue) with a null AA as AA appears to be unavailable in the inliner. I may be confused but I am under the impression that AA is too expensive to recompute or update during inlining (inlining involves relatively a large amount of transformation of code) or that AA may be stateless in reality, but its interface doesn't give that guarantee and not to be relied upon. This code here attempts to handle a simple/special case of AA for stores/loads with different constant offsets off the same base pointer in the absence of AA, in the spirit of the code just above (lines 450-453). This is important for the targeted missed inlining case because it's about a virtual call on a stacked allocated object where it's quite likely some other fields of the object may be stored into besides the vtable pointer in the constructor. Without this code or AA, this function wouldn't go far enough through loads/stores to reach the vtable pointer store in the constructor and the target function pointer in it, and it wouldn't work.

llvm/lib/Transforms/IPO/Inliner.cpp

897

Will try.

[hjyamauchi]

Moved tryPromoteCall to CallPromotionUtils.h/cpp.

[hjyamauchi]

llvm/lib/Transforms/IPO/Inliner.cpp

897

Done.

[hjyamauchi]

Split the utility code into D71307 and D71308.

[davidxl]

Use AAManager (include/llvm/Analysis/AliasAnalysis.h) by registering only BasicAA ?

[hjyamauchi]

In D69591#1793020, @davidxl wrote:

Use AAManager (include/llvm/Analysis/AliasAnalysis.h) by registering only BasicAA ?

How do you mean?

It seems that what type of AA is used is up to how the pass manager is set up (eg. PassBuilder::buildDefaultAAPipeline), not up to an individual pass like the inline pass or a utility function like this.

[hjyamauchi]

Rebase.

[hjyamauchi]

Update clang/test/CodeGenCXX/member-function-pointer-calls.cpp which this change
combined with D71308 enables inlining/simplification.

Add a new test that's derived from
clang/test/CodeGenCXX/member-function-pointer-calls.cpp.

[davidxl]

llvm/test/Transforms/Inline/devirtualize-4.ll

3

typo ? UN:

[hjyamauchi]

Fix typo.

[hjyamauchi]

Rebase past D71308. PTAL.

[davidxl]

LGTM

[hjyamauchi]

Committed as https://reviews.llvm.org/rG59fb9cde7a4a

[hjyamauchi]

This was reverted due to some internal compilation crashes as https://github.com/llvm/llvm-project/commit/4569b3a86f8a4b1b8ad28fe2321f936f9d7ffd43

[hjyamauchi]

Here's a fix: https://reviews.llvm.org/D75307

clang/test/CodeGenCXX/member-function-pointer-calls.cpp

 // RUN: %clang_cc1 %s -triple=x86_64-apple-darwin10 -emit-llvm -O3 -fno-experimental-new-pass-manager  -o - | FileCheck %s --check-prefixes=CHECK,CHECK-LEGACY
 // RUN: %clang_cc1 %s -triple=x86_64-apple-darwin10 -emit-llvm -O3 -fexperimental-new-pass-manager  -o - | FileCheck %s --check-prefixes=CHECK,CHECK-NEWPM
 // RUN: %clang_cc1 %s -triple=x86_64-windows-gnu -emit-llvm -o - | FileCheck %s -check-prefix MINGW64
 struct A {
   virtual int vf1() { return 1; }
   virtual int vf2() { return 2; }
 };
 
 int f(A* a, int (A::*fp)()) {
   return (a->*fp)();
 }
 
 // CHECK-LABEL: define i32 @_Z2g1v()
-// CHECK-LEGACY: ret i32 1
-// CHECK-NEWPM: [[A:%.*]] = alloca %struct.A, align 8
-// CHECK-NEWPM: [[TMP:%.*]] = getelementptr inbounds %struct.A, %struct.A* %a, i64 0, i32 0
-// CHECK-NEWPM: store i32 (...)** bitcast (i8** getelementptr inbounds ({ [4 x i8*] }, { [4 x i8*] }* @_ZTV1A, i64 0, inrange i32 0, i64 2) to i32 (...)**), i32 (...)*** [[TMP]], align 8
-// CHECK-NEWPM: [[RET:%.*]] = call i32 @_ZN1A3vf1Ev(%struct.A* nonnull %a) #2
-// CHECK-NEWPM: ret i32 [[RET]]
+// CHECK-NOT: }
+// CHECK: ret i32 1
 // MINGW64-LABEL: define dso_local i32 @_Z2g1v()
 // MINGW64: call i32 @_Z1fP1AMS_FivE(%struct.A* %{{.*}}, { i64, i64 }* %{{.*}})
 int g1() {
   A a;
   return f(&a, &A::vf1);
 }
 
 // CHECK-LABEL: define i32 @_Z2g2v()
+// CHECK-NOT: }
 // CHECK: ret i32 2
 // MINGW64-LABEL: define dso_local i32 @_Z2g2v()
 // MINGW64: call i32 @_Z1fP1AMS_FivE(%struct.A* %{{.*}}, { i64, i64 }* %{{.*}})
 int g2() {
   A a;
   return f(&a, &A::vf2);
 }

llvm/lib/Transforms/IPO/Inliner.cpp

 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Transforms/Utils/CallPromotionUtils.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Function.h"
if (!ImportedFunctionsStats &&
     ImportedFunctionsStats =
         std::make_unique<ImportedFunctionsInliningStatistics>();
     ImportedFunctionsStats->setModuleInfo(M);
   }
 
   // We use a single common worklist for calls across the entire SCC. We
   // process these in-order and append new calls introduced during inlining to
   // the end.
   //
   // Note that this particular order of processing is actually critical to
   // avoid very bad behaviors. Consider *highly connected* call graphs where
   // each function contains a small amonut of code and a couple of calls to
   // other functions. Because the LLVM inliner is fundamentally a bottom-up
   // inliner, it can handle gracefully the fact that these all appear to be
   // reasonable inlining candidates as it will flatten things until they become
   // too big to inline, and then move on and flatten another batch.
   //
for (; i < (int)Calls.size() && Calls[i].first.getCaller() == &F; ++i) {
       ++NumInlined;
 
       emit_inlined_into(ORE, DLoc, Block, Callee, F, *OIC);
 
       // Add any new callsites to defined functions to the worklist.
       if (!IFI.InlinedCallSites.empty()) {
         int NewHistoryID = InlineHistory.size();
         InlineHistory.push_back({&Callee, InlineHistoryID});
-        for (CallSite &CS : reverse(IFI.InlinedCallSites))
-          if (Function *NewCallee = CS.getCalledFunction())
+        for (CallSite &CS : reverse(IFI.InlinedCallSites)) {
+          Function *NewCallee = CS.getCalledFunction();
+          if (!NewCallee) {
+            // Try to promote an indirect (virtual) call without waiting for the
+            // post-inline cleanup and the next DevirtSCCRepeatedPass iteration
+            // because the next iteration may not happen and we may miss
+            // inlining it.
+            if (tryPromoteCall(CS))
+              NewCallee = CS.getCalledFunction();
+          }
+          if (NewCallee)
             if (!NewCallee->isDeclaration())
               Calls.push_back({CS, NewHistoryID});
         }
+      }
 
       if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No)
         ImportedFunctionsStats->recordInline(F, Callee);
 
       // Merge the attributes based on the inlining.
       AttributeFuncs::mergeAttributesForInlining(F, Callee);
 
       // For local functions, check whether this makes the callee trivially

llvm/test/Transforms/Inline/devirtualize-4.ll

+; RUN: opt < %s -passes='cgscc(devirt<4>(inline)),function(sroa,early-cse)' -S | FileCheck %s
+; RUN: opt < %s -passes='default<O3>' -S | FileCheck %s
+
+; Check that DoNotOptimize is inlined into Test.
+; CHECK: @_Z4Testv()
+; CHECK-NOT: ret void
+; CHECK: call void asm
+; CHECK: ret void
+
+;template <class T>
+;void DoNotOptimize(const T& var) {
+;  asm volatile("" : "+m"(const_cast<T&>(var)));
+;}
+;
+;class Interface {
+; public:
+;  virtual void Run() = 0;
+;};
+;
+;class Impl : public Interface {
+; public:
+;  Impl() : f(3) {}
+;  void Run() { DoNotOptimize(this); }
+;
+; private:
+;  int f;
+;};
+;
+;static void IndirectRun(Interface& o) { o.Run(); }
+;
+;void Test() {
+;  Impl o;
+;  IndirectRun(o);
+;}
+
+%class.Impl = type <{ %class.Interface, i32, [4 x i8] }>
+%class.Interface = type { i32 (...)** }
+
+@_ZTV4Impl = linkonce_odr dso_local unnamed_addr constant { [3 x i8*] } { [3 x i8*] [i8* null, i8* bitcast ({ i8*, i8*, i8* }* @_ZTI4Impl to i8*), i8* bitcast (void (%class.Impl*)* @_ZN4Impl3RunEv to i8*)] }, align 8
+@_ZTVN10__cxxabiv120__si_class_type_infoE = external dso_local global i8*
+@_ZTS4Impl = linkonce_odr dso_local constant [6 x i8] c"4Impl\00", align 1
+@_ZTVN10__cxxabiv117__class_type_infoE = external dso_local global i8*
+@_ZTS9Interface = linkonce_odr dso_local constant [11 x i8] c"9Interface\00", align 1
+@_ZTI9Interface = linkonce_odr dso_local constant { i8*, i8* } { i8* bitcast (i8** getelementptr inbounds (i8*, i8** @_ZTVN10__cxxabiv117__class_type_infoE, i64 2) to i8*), i8* getelementptr inbounds ([11 x i8], [11 x i8]* @_ZTS9Interface, i32 0, i32 0) }, align 8
+@_ZTI4Impl = linkonce_odr dso_local constant { i8*, i8*, i8* } { i8* bitcast (i8** getelementptr inbounds (i8*, i8** @_ZTVN10__cxxabiv120__si_class_type_infoE, i64 2) to i8*), i8* getelementptr inbounds ([6 x i8], [6 x i8]* @_ZTS4Impl, i32 0, i32 0), i8* bitcast ({ i8*, i8* }* @_ZTI9Interface to i8*) }, align 8
+@_ZTV9Interface = linkonce_odr dso_local unnamed_addr constant { [3 x i8*] } { [3 x i8*] [i8* null, i8* bitcast ({ i8*, i8* }* @_ZTI9Interface to i8*), i8* bitcast (void ()* @__cxa_pure_virtual to i8*)] }, align 8
+
+define dso_local void @_Z4Testv() local_unnamed_addr {
+entry:
+  %o = alloca %class.Impl, align 8
+  %0 = bitcast %class.Impl* %o to i8*
+  call void @llvm.lifetime.start.p0i8(i64 16, i8* nonnull %0)
+  call void @_ZN4ImplC2Ev(%class.Impl* nonnull %o)
+  %1 = getelementptr inbounds %class.Impl, %class.Impl* %o, i64 0, i32 0
+  call fastcc void @_ZL11IndirectRunR9Interface(%class.Interface* nonnull dereferenceable(8) %1)
+  call void @llvm.lifetime.end.p0i8(i64 16, i8* nonnull %0)
+  ret void
+}
+
+declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture)
+
+define linkonce_odr dso_local void @_ZN4ImplC2Ev(%class.Impl* %this) unnamed_addr align 2 {
+entry:
+  %0 = getelementptr %class.Impl, %class.Impl* %this, i64 0, i32 0
+  call void @_ZN9InterfaceC2Ev(%class.Interface* %0)
+  %1 = getelementptr %class.Impl, %class.Impl* %this, i64 0, i32 0, i32 0
+  store i32 (...)** bitcast (i8** getelementptr inbounds ({ [3 x i8*] }, { [3 x i8*] }* @_ZTV4Impl, i64 0, inrange i32 0, i64 2) to i32 (...)**), i32 (...)*** %1, align 8
+  %f = getelementptr inbounds %class.Impl, %class.Impl* %this, i64 0, i32 1
+  store i32 3, i32* %f, align 8
+  ret void
+}
+
+define internal fastcc void @_ZL11IndirectRunR9Interface(%class.Interface* dereferenceable(8) %o) unnamed_addr {
+entry:
+  %0 = bitcast %class.Interface* %o to void (%class.Interface*)***
+  %vtable = load void (%class.Interface*)**, void (%class.Interface*)*** %0, align 8
+  %1 = load void (%class.Interface*)*, void (%class.Interface*)** %vtable, align 8
+  call void %1(%class.Interface* nonnull %o)
+  ret void
+}
+
+declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture)
+
+define linkonce_odr dso_local void @_ZN9InterfaceC2Ev(%class.Interface* %this) unnamed_addr align 2 {
+entry:
+  %0 = getelementptr %class.Interface, %class.Interface* %this, i64 0, i32 0
+  store i32 (...)** bitcast (i8** getelementptr inbounds ({ [3 x i8*] }, { [3 x i8*] }* @_ZTV9Interface, i64 0, inrange i32 0, i64 2) to i32 (...)**), i32 (...)*** %0, align 8
+  ret void
+}
+
+define linkonce_odr dso_local void @_ZN4Impl3RunEv(%class.Impl* %this) unnamed_addr align 2 {
+entry:
+  %ref.tmp = alloca %class.Impl*, align 8
+  %0 = bitcast %class.Impl** %ref.tmp to i8*
+  call void @llvm.lifetime.start.p0i8(i64 8, i8* nonnull %0)
+  store %class.Impl* %this, %class.Impl** %ref.tmp, align 8
+  call void @_Z13DoNotOptimizeIP4ImplEvRKT_(%class.Impl** nonnull dereferenceable(8) %ref.tmp)
+  call void @llvm.lifetime.end.p0i8(i64 8, i8* nonnull %0)
+  ret void
+}
+
+declare dso_local void @__cxa_pure_virtual() unnamed_addr
+
+define linkonce_odr dso_local void @_Z13DoNotOptimizeIP4ImplEvRKT_(%class.Impl** dereferenceable(8) %var) local_unnamed_addr {
+entry:
+  call void asm sideeffect "", "=*m,*m,~{dirflag},~{fpsr},~{flags}"(%class.Impl** nonnull %var, %class.Impl** nonnull %var)
+  ret void
+}
+
+
+; Based on clang/test/CodeGenCXX/member-function-pointer-calls.cpp.
+; Check that vf1 and vf2 are inlined into g1 and g2.
+; CHECK: @_Z2g1v()
+; CHECK-NOT: }
+; CHECK: ret i32 1
+; CHECK: @_Z2g2v()
+; CHECK-NOT: }
+; CHECK: ret i32 2
+;
+;struct A {
+;  virtual int vf1() { return 1; }
+;  virtual int vf2() { return 2; }
+;};
+;
+;int f(A* a, int (A::*fp)()) {
+;  return (a->*fp)();
+;}
+;int g1() {
+;  A a;
+;  return f(&a, &A::vf1);
+;}
+;int g2() {
+;  A a;
+;  return f(&a, &A::vf2);
+;}
+
+%struct.A = type { i32 (...)** }
+
+@_ZTV1A = linkonce_odr unnamed_addr constant { [4 x i8*] } { [4 x i8*] [i8* null, i8* bitcast ({ i8*, i8* }* @_ZTI1A to i8*), i8* bitcast (i32 (%struct.A*)* @_ZN1A3vf1Ev to i8*), i8* bitcast (i32 (%struct.A*)* @_ZN1A3vf2Ev to i8*)] }, align 8
+@_ZTS1A = linkonce_odr constant [3 x i8] c"1A\00", align 1
+@_ZTI1A = linkonce_odr constant { i8*, i8* } { i8* bitcast (i8** getelementptr inbounds (i8*, i8** @_ZTVN10__cxxabiv117__class_type_infoE, i64 2) to i8*), i8* getelementptr inbounds ([3 x i8], [3 x i8]* @_ZTS1A, i32 0, i32 0) }, align 8
+
+define i32 @_Z1fP1AMS_FivE(%struct.A* %a, i64 %fp.coerce0, i64 %fp.coerce1) {
+entry:
+  %0 = bitcast %struct.A* %a to i8*
+  %1 = getelementptr inbounds i8, i8* %0, i64 %fp.coerce1
+  %this.adjusted = bitcast i8* %1 to %struct.A*
+  %2 = and i64 %fp.coerce0, 1
+  %memptr.isvirtual = icmp eq i64 %2, 0
+  br i1 %memptr.isvirtual, label %memptr.nonvirtual, label %memptr.virtual
+
+memptr.virtual:                                   ; preds = %entry
+  %3 = bitcast i8* %1 to i8**
+  %vtable = load i8*, i8** %3, align 8
+  %4 = add i64 %fp.coerce0, -1
+  %5 = getelementptr i8, i8* %vtable, i64 %4
+  %6 = bitcast i8* %5 to i32 (%struct.A*)**
+  %memptr.virtualfn = load i32 (%struct.A*)*, i32 (%struct.A*)** %6, align 8
+  br label %memptr.end
+
+memptr.nonvirtual:                                ; preds = %entry
+  %memptr.nonvirtualfn = inttoptr i64 %fp.coerce0 to i32 (%struct.A*)*
+  br label %memptr.end
+
+memptr.end:                                       ; preds = %memptr.nonvirtual, %memptr.virtual
+  %7 = phi i32 (%struct.A*)* [ %memptr.virtualfn, %memptr.virtual ], [ %memptr.nonvirtualfn, %memptr.nonvirtual ]
+  %call = call i32 %7(%struct.A* %this.adjusted)
+  ret i32 %call
+}
+
+define i32 @_Z2g1v() {
+entry:
+  %a = alloca %struct.A, align 8
+  %0 = bitcast %struct.A* %a to i8*
+  call void @llvm.lifetime.start.p0i8(i64 8, i8* nonnull %0)
+  call void @_ZN1AC1Ev(%struct.A* nonnull %a)
+  %call = call i32 @_Z1fP1AMS_FivE(%struct.A* nonnull %a, i64 1, i64 0)
+  call void @llvm.lifetime.end.p0i8(i64 8, i8* nonnull %0)
+  ret i32 %call
+}
+
+define linkonce_odr void @_ZN1AC1Ev(%struct.A* %this) align 2 {
+entry:
+  call void @_ZN1AC2Ev(%struct.A* %this)
+  ret void
+}
+
+define i32 @_Z2g2v() {
+entry:
+  %a = alloca %struct.A, align 8
+  %0 = bitcast %struct.A* %a to i8*
+  call void @llvm.lifetime.start.p0i8(i64 8, i8* nonnull %0)
+  call void @_ZN1AC1Ev(%struct.A* nonnull %a)
+  %call = call i32 @_Z1fP1AMS_FivE(%struct.A* nonnull %a, i64 9, i64 0)
+  call void @llvm.lifetime.end.p0i8(i64 8, i8* nonnull %0)
+  ret i32 %call
+}
+
+define linkonce_odr void @_ZN1AC2Ev(%struct.A* %this) align 2 {
+entry:
+  %0 = getelementptr %struct.A, %struct.A* %this, i64 0, i32 0
+  store i32 (...)** bitcast (i8** getelementptr inbounds ({ [4 x i8*] }, { [4 x i8*] }* @_ZTV1A, i64 0, inrange i32 0, i64 2) to i32 (...)**), i32 (...)*** %0, align 8
+  ret void
+}
+
+define linkonce_odr i32 @_ZN1A3vf1Ev(%struct.A* %this) align 2 {
+entry:
+  ret i32 1
+}
+
+define linkonce_odr i32 @_ZN1A3vf2Ev(%struct.A* %this) align 2 {
+entry:
+  ret i32 2
+}