Repeat DevirtSCCRepeatedPass if new indirect calls are found.

[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.

[hjyamauchi]

This is an alternative approach to https://reviews.llvm.org/D69591

[davidxl]

Any compile time impact numbers?

[davidxl]

llvm/lib/Transforms/IPO/Inliner.cpp

1095

Alternatively, if compile time is a concern, the inline analysis 'shouldInline' can return a flag indicating if the callee has any indirect calls. If it is true and if the site is inlined, set this flag.

[hjyamauchi]

The way this patch currently is, the compile time impact in Clang's self build is ~5.3%.

[davidxl]

The compile time impact looks too high. Might consider more fine grained check to trigger more iterations.

[hjyamauchi]

Updated.

[hjyamauchi]

Now it would repeat DevirtSCCRepeatedPass if new indirect calls appear after inlining.

With this version, the compile time impact is ~1.48%.

[davidxl]

Around line 1323 of InlineCost.cpp, there is code that detects if the new indirect callsites can become direct sites after inlining. This information can be passed back to the caller (via GetInlineCost and shouldInline interfaces). WIth that, I think the compile time impact can be minimized.

[hjyamauchi]

As I understand, that code around line 1323 of InlineCost.cpp would handle a simple case where a caller is passing a (constant) function pointer as a call argument and the callee simply calls it (constant propagation). But it wouldn't handle a (more complex) virtual call (vtable lookup though memory) on a stack allocated (in the caller) object passed to a callee, and would not work for this particular missed inlining case, at least, as is.

To handle such a case, it would have to add logic like the original patch (D69591) that detects a vtable look up pattern along with consideration for aliasing (since the vtable is in memory). But it'd be difficult to do because CallAnalyzer/InlineCost operates without actually having the code inlined (ie. interprocedural) and won't be able to reuse the facilities like llvm::FindAvailablePtrLoadStore.

It'd be conceivable to beef up CallAnalyzer to do this sort of things, but it'd be potentially non-trivial in complexity and compile-time-increasing.

The original patch D69591 (which, I think is, fairly fine grained to this case, btw) doesn't have this issue because it applies right after the call is actually inlined and the scope of analysis becomes intraprocedural.

llvm/include/llvm/Analysis/CGSCCPassManager.h

struct CGSCCUpdateResult {
   /// A hacky area where the inliner can retain history about inlining
   /// decisions that mutated the call graph's SCC structure in order to avoid
   /// infinite inlining. See the comments in the inliner's CG update logic.
   ///
   /// FIXME: Keeping this here seems like a big layering issue, we should look
   /// for a better technique.
   SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
       &InlinedInternalEdges;
+
+  /// Used for the inliner pass to request DevirtSCCRepeatedPass to repeat one
+  /// more iteration.
+  bool RepeatDevirtSCC;
 };
 
 /// The core module pass which does a post-order walk of the SCCs and
 /// runs a CGSCC pass over each one.
 ///
 /// Designed to allow composition of a CGSCCPass(Manager) and
 /// a ModulePassManager. Note that this pass must be run with a module analysis
 /// manager as it uses the LazyCallGraph analysis. It will also run the
PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM,
     // Populate the initial call handles and get the initial call counts.
     auto CallCounts = ScanSCC(*C, CallHandles);
 
     for (int Iteration = 0;; ++Iteration) {
 
       if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
         continue;
 
+      UR.RepeatDevirtSCC = false;
       PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR);
 
       if (UR.InvalidatedSCCs.count(C))
         PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass);
       else
         PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C);
 
       // If the SCC structure has changed, bail immediately and let the outer
for (int Iteration = 0;; ++Iteration) {
         LLVM_DEBUG(dbgs() << "Found devirtualized call from "
                           << CS.getParent()->getParent()->getName() << " to "
                           << F->getName() << "\n");
 
         // We now have a direct call where previously we had an indirect call,
         // so iterate to process this devirtualization site.
         return true;
       };
-      bool Devirt = llvm::any_of(CallHandles, IsDevirtualizedHandle);
+      bool Repeat = UR.RepeatDevirtSCC ||
+                    llvm::any_of(CallHandles, IsDevirtualizedHandle);
 
       // Rescan to build up a new set of handles and count how many direct
       // calls remain. If we decide to iterate, this also sets up the input to
       // the next iteration.
       CallHandles.clear();
       auto NewCallCounts = ScanSCC(*C, CallHandles);
 
       // If we haven't found an explicit devirtualization already see if we
       // have decreased the number of indirect calls and increased the number
       // of direct calls for any function in the SCC. This can be fooled by all
       // manner of transformations such as DCE and other things, but seems to
       // work well in practice.
-      if (!Devirt)
+      if (!Repeat)
         // Iterate over the keys in NewCallCounts, if Function also exists in
         // CallCounts, make the check below.
         for (auto &Pair : NewCallCounts) {
           auto &CallCountNew = Pair.second;
           auto CountIt = CallCounts.find(Pair.first);
           if (CountIt != CallCounts.end()) {
             const auto &CallCountOld = CountIt->second;
             if (CallCountOld.Indirect > CallCountNew.Indirect &&
                 CallCountOld.Direct < CallCountNew.Direct) {
-              Devirt = true;
+              Repeat = true;
               break;
             }
           }
         }
 
-      if (!Devirt) {
+      if (!Repeat) {
         PA.intersect(std::move(PassPA));
         break;
       }
 
       // Otherwise, if we've already hit our max, we're done.
       if (Iteration >= MaxIterations) {
         LLVM_DEBUG(
             dbgs() << "Found another devirtualization after hitting the max "
ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>::run(Module &M,
   SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet;
   SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
 
   SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
       InlinedInternalEdges;
 
   CGSCCUpdateResult UR = {
       RCWorklist, CWorklist, InvalidRefSCCSet,         InvalidSCCSet,
-      nullptr,    nullptr,   PreservedAnalyses::all(), InlinedInternalEdges};
+      nullptr,    nullptr,   PreservedAnalyses::all(), InlinedInternalEdges,
+      false
+  };
 
   // Request PassInstrumentation from analysis manager, will use it to run
   // instrumenting callbacks for the passes later.
   PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
 
   PreservedAnalyses PA = PreservedAnalyses::all();
   CG.buildRefSCCs();
   for (auto RCI = CG.postorder_ref_scc_begin(),

llvm/lib/Transforms/IPO/Inliner.cpp

 /// Flag to add inline messages as callsite attributes 'inline-remark'.
 static cl::opt<bool>
     InlineRemarkAttribute("inline-remark-attribute", cl::init(false),
                           cl::Hidden,
                           cl::desc("Enable adding inline-remark attribute to"
                                    " callsites processed by inliner but decided"
                                    " to be not inlined"));
 
+static cl::opt<bool> RepeatDevirtSCCForNewIndirectCalls(
+    "repeat-devirt-scc-for-new-indirect-calls",
+    cl::init(true), cl::Hidden,
+    cl::desc("Request to iterate DevirtSCCRepeatedPass one more time when "
+             "new indirect calls appear after inlining"));
+
 LegacyInlinerBase::LegacyInlinerBase(char &ID) : CallGraphSCCPass(ID) {}
 
 LegacyInlinerBase::LegacyInlinerBase(char &ID, bool InsertLifetime)
     : CallGraphSCCPass(ID), InsertLifetime(InsertLifetime) {}
 
 /// For this class, we declare that we require and preserve the call graph.
 /// If the derived class implements this method, it should
 /// always explicitly call the implementation here.
for (; i < (int)Calls.size() && Calls[i].first.getCaller() == &F; ++i) {
         ORE.emit([&]() {
           return OptimizationRemarkMissed(DEBUG_TYPE, "NotInlined", DLoc, Block)
                  << NV("Callee", &Callee) << " will not be inlined into "
                  << NV("Caller", &F) << ": " << NV("Reason", IR.message);
         });
         continue;
       }
       DidInline = true;
       InlinedCallees.insert(&Callee);
 
       ++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())
+          if (Function *NewCallee = CS.getCalledFunction()) {
             if (!NewCallee->isDeclaration())
               Calls.push_back({CS, NewHistoryID});
+          } else {
+            // An indirect call appeared after inlining. Request one more
+            // DevirtSCCRepeatedPass iteration in case it turns into a direct
+            // call after cleanup.
+            if (RepeatDevirtSCCForNewIndirectCalls)
+              UR.RepeatDevirtSCC = true;
+          }
       }
 
       if (InlinerFunctionImportStats != InlinerFunctionImportStatsOpts::No)
         ImportedFunctionsStats->recordInline(F, Callee);
 
       // Merge the attributes based on the inlining.
       AttributeFuncs::mergeAttributesForInlining(F, Callee);
 

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

+; RUN: opt < %s -aa-pipeline=basic-aa -passes='cgscc(devirt<4>(inline,function(instcombine)))' -S | FileCheck %s
+; RUN: opt < %s -aa-pipeline=basic-aa -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
+}
+