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

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

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

llvm/lib/Analysis/Loads.cpp

if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
       // If both StrippedPtr and StorePtr reach all the way to an alloca or
       // global and they are different, ignore the store. This is a trivial form
       // of alias analysis that is important for reg2mem'd code.
       if ((isa<AllocaInst>(StrippedPtr) || isa<GlobalVariable>(StrippedPtr)) &&
           (isa<AllocaInst>(StorePtr) || isa<GlobalVariable>(StorePtr)) &&
           StrippedPtr != StorePtr)
         continue;
 
+      // If the load and the store have the same base and constant offsets and
+      // the ranges don't overlap, ignore the store. This is a simple form of
+      // alias analysis.
+      APInt LoadOffset(DL.getTypeSizeInBits(Ptr->getType()), 0);
+      APInt StoreOffset(DL.getTypeSizeInBits(
+          SI->getPointerOperand()->getType()), 0);
+      Value *LoadBase = Ptr->stripAndAccumulateConstantOffsets(
+          DL, LoadOffset, /* AllowNonInbounds */ false);
+      Value *StoreBase = StorePtr->stripAndAccumulateConstantOffsets(
+          DL, StoreOffset, /* AllowNonInbounds */ false);
+      auto StoreAccessSize = LocationSize::precise(
+          DL.getTypeStoreSize(SI->getPointerOperand()->getType()));
+      ConstantRange LoadRange(LoadOffset,
+                              LoadOffset + AccessSize.toRaw());
+      ConstantRange StoreRange(StoreOffset,
+                               StoreOffset + StoreAccessSize.toRaw());
+      if (LoadBase == StoreBase &&
+          LoadRange.intersectWith(StoreRange).isEmptySet())
+          continue;
+
       // If we have alias analysis and it says the store won't modify the loaded
       // value, ignore the store.
       if (AA && !isModSet(AA->getModRefInfo(SI, StrippedPtr, AccessSize)))
         continue;
 
       // Otherwise the store that may or may not alias the pointer, bail out.
       ++ScanFrom;
       return nullptr;

llvm/lib/Transforms/IPO/Inliner.cpp

 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/InlineCost.h"
 #include "llvm/Analysis/LazyCallGraph.h"
+#include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/Analysis/TypeMetadataUtils.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"

 InlinerPass::~InlinerPass() {
   if (ImportedFunctionsStats) {
     assert(InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No);
     ImportedFunctionsStats->dump(InlinerFunctionImportStats ==
                                  InlinerFunctionImportStatsOpts::Verbose);
   }
 }
 
+// Try to promote (devirtualize) a virtual call on an Alloca that appears as a
+// result of inlining.
+//
+// Look for a pattern like:
+//
+//  %o = alloca %class.Impl
+//  %1 = getelementptr %class.Impl, %class.Impl* %o, 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
+//  %2 = getelementptr inbounds %class.Impl, %class.Impl* %o, i64 0, i32 0
+//  %3 = bitcast %class.Interface* %2 to void (%class.Interface*)***
+//  %vtable.i = load void (%class.Interface*)**, void (%class.Interface*)*** %3
+//  %4 = load void (%class.Interface*)*, void (%class.Interface*)** %vtable.i
+//  call void %4(%class.Interface* nonnull %2)
+//
+// @_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*)] }
+//
+static void tryPromoteCall(CallSite &CS) {
+  assert(!CS.getCalledFunction());
+  Module *M = CS.getCaller()->getParent();
+  const DataLayout &DL = M->getDataLayout();
+  Value *Callee = CS.getCalledValue();
+
+  LoadInst *VTableEntryLoad = dyn_cast<LoadInst>(Callee);
+  if (!VTableEntryLoad)
+    return; // Not a vtable entry load.
+  Value *VTableEntryPtr = VTableEntryLoad->getPointerOperand();
+  APInt VTableOffset(DL.getTypeSizeInBits(VTableEntryPtr->getType()), 0);
+  Value *VTableBasePtr = VTableEntryPtr->stripAndAccumulateConstantOffsets(
+      DL, VTableOffset, /* AllowNonInbounds */ false);
+  LoadInst *VTableLoad = dyn_cast<LoadInst>(VTableBasePtr);
+  if (!VTableLoad)
+    return; // Not a vtable load.
+  Value *Object = VTableLoad->getPointerOperand();
+  APInt ObjectOffset(DL.getTypeSizeInBits(Object->getType()), 0);
+  Value *ObjectBase = Object->stripAndAccumulateConstantOffsets(
+      DL, ObjectOffset, /* AllowNonInbounds */ false);
+  if (!(isa<AllocaInst>(ObjectBase) && ObjectOffset == 0))
+    // Not an Alloca or the offset isn't zero.
+    return;
+
+  // Look for the vtable pointer store into the object by the ctor.
+  BasicBlock::iterator BBI(VTableLoad);
+  Value *VTable = FindAvailableLoadedValue(
+      VTableLoad, VTableLoad->getParent(), BBI, 0, nullptr, nullptr);
+  if (!VTable)
+    return; // No vtable found.
+  APInt VTableOffsetGVBase(DL.getTypeSizeInBits(VTable->getType()), 0);
+  Value *VTableGVBase = VTable->stripAndAccumulateConstantOffsets(
+      DL, VTableOffsetGVBase, /* AllowNonInbounds */ false);
+  GlobalVariable *GV = dyn_cast<GlobalVariable>(VTableGVBase);
+  if (!(GV && GV->isConstant() && GV->hasDefinitiveInitializer()))
+    // Not in the form of a global constant variable with an initializer.
+    return;
+
+  Constant *VTableGVInitializer = GV->getInitializer();
+  APInt VTableGVOffset = VTableOffsetGVBase + VTableOffset;
+  if (!(VTableGVOffset.getActiveBits() <= 64))
+    return; // Out of range.
+  Constant *Ptr = getPointerAtOffset(VTableGVInitializer,
+                                     VTableGVOffset.getZExtValue(),
+                                     *M);
+  if (!Ptr)
+    return; // No constant (function) pointer found.
+  Function *DirectCallee = dyn_cast<Function>(Ptr->stripPointerCasts());
+  if (!DirectCallee)
+    return; // No function pointer found.
+
+  // Success.
+  promoteCall(CS, DirectCallee);
+}
+
 PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC,
                                    CGSCCAnalysisManager &AM, LazyCallGraph &CG,
                                    CGSCCUpdateResult &UR) {
   const ModuleAnalysisManager &MAM =
       AM.getResult<ModuleAnalysisManagerCGSCCProxy>(InitialC, CG).getManager();
   bool Changed = false;
 
   assert(InitialC.size() > 0 && "Cannot handle an empty SCC!");
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.
+            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))' -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
+}
+