[CGSCC] Detect devirtualization in more cases

[aeubanks]

Summary

The devirtualization wrapper misses cases where if it wraps a pass
manager, an individual pass may devirtualize an indirect call created by
a previous pass. For example, inlining may create a new indirect call
which is devirtualized by instcombine. Currently the devirtualization
wrapper will not see that because it only checks cgscc edges at the very
beginning and end of the pass (manager) it wraps.

This fixes some tests testing this exact behavior in the legacy PM.

This piggybacks off of updateCGAndAnalysisManagerForPass()'s detection
of promoted ref to call edges.

This supercedes one of the previous mechanisms to detect
devirtualization by keeping track of potentially promoted call
instructions via WeakTrackingVHs.

There is one more existing way of detecting devirtualization, by
checking if the number of indirect calls has decreased and the number of
direct calls has increased in a function. It handles cases where calls
to functions without definitions are promoted, and some tests rely on
that. LazyCallGraph doesn't track edges to functions without
definitions so this part can't be removed in this change.

check-llvm and check-clang with -abort-on-max-devirt-iterations-reached
on by default doesn't show any failures outside of tests specifically
testing it so it doesn't needlessly rerun passes more than necessary.
(The NPM -O2/3 pipeline run the inliner/function simplification pipeline
under a devirtualization repeater pass up to 4 times by default).

[asbirlea]

This makes sense to me.

[nikic]

FYI, this showed up as a 5% compile-time regression in the NewPM-O3 configuration: https://llvm-compile-time-tracker.com/compare.php?from=3b8d8954bf2c192502d757019b9fe434864068e9&to=3024fe5b55ed72633915f613bd5e2826583c396f&stat=instructions

[aeubanks]

Will investigate compile time regression

[aeubanks]

Using sqlite3 in llvm-test-suite, without this change DevirtSCCRepeatedPass never reruns the pipeline, but with this change it does for lots of SCCs.
Off the top of my head the only thing I can think of that would rerun passes with this is that a call promoted in one pass that gets deleted in a later pass would trigger a rerun.

[aeubanks]

The issue is that the inliner is inserting ref edges right before it calls updateCGAndAnalysisManagerForFunctionPass, which then promotes those edges to call edges, making us think there's been a devirtualization.
https://github.com/llvm/llvm-project/blob/72ddd559b8aafef402091f8e192e025022e4ebef/llvm/lib/Transforms/IPO/Inliner.cpp#L944

[aeubanks]

I think the proper way to address this is to fix the TODOs in updateCGAndAnalysisManagerForPass where it doesn't allow non-trivial edges to be added. With that fixed, we can remove the hack in the inliner that adds ref edges just to be promoted in updateCGAndAnalysisManagerForPass. That will also include changing the call from the inliner from updateCGAndAnalysisManagerForFunctionPass to updateCGAndAnalysisManagerForCGSCCPass.

[aeubanks]

rebase
use WeakTrackingVH solution instead of just looking for promoted edges

[aeubanks]

It turns out that using promoted edges didn't catch the case where a function that returns a function pointer is inlined into another function that calls the returned function pointer. That test happened to pass previously because we were accidentally always detecting promoted edges so we always reran the pipeline at least once, which was fixed in https://reviews.llvm.org/D91046.
The WeakTrackingVH approach seems to cover all cases that the promoted edge method caught, so I just used that in updateCGAndAnalysisManagerForPass() as you suggested offline.

[rnk]

llvm/include/llvm/Analysis/CGSCCPassManager.h

321

Using a Value pointer as a key seems like it could suffer from the ABA problem. Suppose a CallInst is deallocated and another is reallocated at the same address. The map will contain a false entry for the new call.

It seems like the lookup functionality (find/insert) is only needed during the update scan. You could build a map from Value* to handle index before that loop, and then do the instruction scan.

[asbirlea]

Could you clarify why a map and not a SmallVector?

I was expecting the indirect calls to be added by all CGSCC passes, e.g. lib/Transforms/IPO/Inliner.cpp:750. Adding the calls in updateCG... instead, introduces a single point of failure so less chances of having passes forget to add them; the one thing I'm not clear is if the updateCG... call may be added too late in a CGSCC pass; for the inliner, it seems fine (thank you for adding the tests) but I'm not clear if this will hold for other passes. I don't have a use case now, just making a note to verify this for coroutines.
The check that all accesses are still indirect on the return looks good.

[aeubanks]

add debug logging
add comment to IndirectVHs

[aeubanks]

In D89587#2398531, @asbirlea wrote:

Could you clarify why a map and not a SmallVector?

I was expecting the indirect calls to be added by all CGSCC passes, e.g. lib/Transforms/IPO/Inliner.cpp:750. Adding the calls in updateCG... instead, introduces a single point of failure so less chances of having passes forget to add them; the one thing I'm not clear is if the updateCG... call may be added too late in a CGSCC pass; for the inliner, it seems fine (thank you for adding the tests) but I'm not clear if this will hold for other passes. I don't have a use case now, just making a note to verify this for coroutines.
The check that all accesses are still indirect on the return looks good.

It is definitely possible to have a call to updateCG... miss a devirtualization in a CGSCC pass if an indirect call is introduced and then promoted before the call to updateCG..., but the inliner looks ok. I think other CGSCC passes don't really devirtualize much. As long as we call updateCG... after passes that can devirtualize (inliner, function passes like instcombine, etc) we should be good. And we can always revisit if we find missed cases.

llvm/include/llvm/Analysis/CGSCCPassManager.h

321

If a CallInst is deallocated, its corresponding WeakTrackingVH will become null, and that should be ok. We just want to make sure that we don't insert duplicate entries into IndirectVHs. If we never end up with a new CallInst at the same address, then we'll ignore the nulled WeakTrackingVH when scanning for promoted calls. If there is a new CallInst at the same address, it will overwrite the old one due to the !Entry->second check in updateCGAndAnalysisManager.

We could remove all null WeakTrackingVHs at the beginning of updateCGAndAnalysisManager to alleviate any ABA and memory (we never remove entries) concerns, although I was trying to avoid looking through all entries in WeakTrackingVHs on every call to updateCGAndAnalysisManager.

I tried changing IndirectVHs into a SmallVector<WeakTrackingVH>, but then we end up adding extra code (and runtime) to create a map on every call to updateCGAndAnalysisManager, and we might as well just have that map as IndirectVHs itself.

[asbirlea]

In D89587#2400646, @aeubanks wrote:

In D89587#2398531, @asbirlea wrote:

Could you clarify why a map and not a SmallVector?

I was expecting the indirect calls to be added by all CGSCC passes, e.g. lib/Transforms/IPO/Inliner.cpp:750. Adding the calls in updateCG... instead, introduces a single point of failure so less chances of having passes forget to add them; the one thing I'm not clear is if the updateCG... call may be added too late in a CGSCC pass; for the inliner, it seems fine (thank you for adding the tests) but I'm not clear if this will hold for other passes. I don't have a use case now, just making a note to verify this for coroutines.
The check that all accesses are still indirect on the return looks good.

It is definitely possible to have a call to updateCG... miss a devirtualization in a CGSCC pass if an indirect call is introduced and then promoted before the call to updateCG..., but the inliner looks ok. I think other CGSCC passes don't really devirtualize much. As long as we call updateCG... after passes that can devirtualize (inliner, function passes like instcombine, etc) we should be good. And we can always revisit if we find missed cases.

SG. Can you make a note/comment on this in the update function where adding IndirectVH?

[aeubanks]

add comment
Is this what you were looking for? Or more explanation?

[aeubanks]

don't insert if found entry in map

llvm/include/llvm/Analysis/CGSCCPassManager.h

 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_CGSCCPASSMANAGER_H
 #define LLVM_ANALYSIS_CGSCCPASSMANAGER_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PriorityWorklist.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/PassManager.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;
+
+  /// Weak VHs to keep track of indirect calls for the purposes of detecting
+  /// devirtualization.
+  ///
+  /// This is a map to avoid having duplicate entries. If a Value is
+  /// deallocated, its corresponding WeakTrackingVH will be nulled out. When
+  /// checking if a Value is in the map or not, also check if the corresponding
+  /// WeakTrackingVH is null to avoid issues with a new Value sharing the same
+  /// address as a deallocated one.
+  SmallMapVector<Value *, WeakTrackingVH, 16> IndirectVHs;
 };
 
 /// 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,
     PreservedAnalyses PA = PreservedAnalyses::all();
     PassInstrumentation PI =
         AM.getResult<PassInstrumentationAnalysis>(InitialC, CG);
 
     // The SCC may be refined while we are running passes over it, so set up
     // a pointer that we can update.
     LazyCallGraph::SCC *C = &InitialC;
 
-    // Collect value handles for all of the indirect call sites.
-    SmallVector<WeakTrackingVH, 8> CallHandles;
-
     // Struct to track the counts of direct and indirect calls in each function
     // of the SCC.
     struct CallCount {
       int Direct;
       int Indirect;
     };
 
     // Put value handles on all of the indirect calls and return the number of
     // direct calls for each function in the SCC.
-    auto ScanSCC = [](LazyCallGraph::SCC &C,
-                      SmallVectorImpl<WeakTrackingVH> &CallHandles) {
-      assert(CallHandles.empty() && "Must start with a clear set of handles.");
+    auto ScanSCC =
+        [](LazyCallGraph::SCC &C,
+           SmallMapVector<Value *, WeakTrackingVH, 16> &CallHandles) {
+          assert(CallHandles.empty() &&
+                 "Must start with a clear set of handles.");
 
           SmallDenseMap<Function *, CallCount> CallCounts;
           CallCount CountLocal = {0, 0};
           for (LazyCallGraph::Node &N : C) {
             CallCount &Count =
                 CallCounts.insert(std::make_pair(&N.getFunction(), CountLocal))
                     .first->second;
             for (Instruction &I : instructions(N.getFunction()))
               if (auto *CB = dyn_cast<CallBase>(&I)) {
                 if (CB->getCalledFunction()) {
                   ++Count.Direct;
                 } else {
                   ++Count.Indirect;
-              CallHandles.push_back(WeakTrackingVH(&I));
+                  CallHandles.insert({CB, WeakTrackingVH(CB)});
                 }
               }
           }
 
           return CallCounts;
         };
 
+    UR.IndirectVHs.clear();
     // Populate the initial call handles and get the initial call counts.
-    auto CallCounts = ScanSCC(*C, CallHandles);
+    auto CallCounts = ScanSCC(*C, UR.IndirectVHs);
 
     for (int Iteration = 0;; ++Iteration) {
-
       if (!PI.runBeforePass<LazyCallGraph::SCC>(Pass, *C))
         continue;
 
       PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR);
 
       if (UR.InvalidatedSCCs.count(C))
         PI.runAfterPassInvalidated<LazyCallGraph::SCC>(Pass, PassPA);
       else
         PI.runAfterPass<LazyCallGraph::SCC>(Pass, *C, PassPA);
 
       // If the SCC structure has changed, bail immediately and let the outer
       // CGSCC layer handle any iteration to reflect the refined structure.
       if (UR.UpdatedC && UR.UpdatedC != C) {
         PA.intersect(std::move(PassPA));
         break;
       }
 
       // Check that we didn't miss any update scenario.
       assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!");
       assert(C->begin() != C->end() && "Cannot have an empty SCC!");
 
       // Check whether any of the handles were devirtualized.
-      auto IsDevirtualizedHandle = [&](WeakTrackingVH &CallH) {
-        if (!CallH)
-          return false;
-        auto *CB = dyn_cast<CallBase>(CallH);
-        if (!CB)
-          return false;
-
-        // If the call is still indirect, leave it alone.
-        Function *F = CB->getCalledFunction();
-        if (!F)
-          return false;
-
-        LLVM_DEBUG(dbgs() << "Found devirtualized call from "
-                          << CB->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.
+      bool Devirt = llvm::any_of(UR.IndirectVHs, [](auto &P) -> bool {
+        if (P.second) {
+          CallBase *CB = cast<CallBase>(P.second);
+          if (CB->getCalledFunction()) {
+            LLVM_DEBUG(dbgs() << "Found devirtualized call: " << *CB << "\n");
             return true;
-      };
-      bool Devirt = llvm::any_of(CallHandles, IsDevirtualizedHandle);
+          }
+        }
+        return false;
+      });
 
       // 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);
+      UR.IndirectVHs.clear();
+      auto NewCallCounts = ScanSCC(*C, UR.IndirectVHs);
 
       // 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)
         // Iterate over the keys in NewCallCounts, if Function also exists in
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,
+      {}};
 
   // 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/Analysis/CGSCCPassManager.cpp

 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/PassManagerImpl.h"
+#include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/TimeProfiler.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
static LazyCallGraph::SCC &updateCGAndAnalysisManagerForPass(
   SmallSetVector<Node *, 4> DemotedCallTargets;
   SmallSetVector<Node *, 4> NewCallEdges;
   SmallSetVector<Node *, 4> NewRefEdges;
   SmallSetVector<Node *, 4> NewNodes;
 
   // First walk the function and handle all called functions. We do this first
   // because if there is a single call edge, whether there are ref edges is
   // irrelevant.
-  for (Instruction &I : instructions(F))
-    if (auto *CB = dyn_cast<CallBase>(&I))
-      if (Function *Callee = CB->getCalledFunction())
+  for (Instruction &I : instructions(F)) {
+    if (auto *CB = dyn_cast<CallBase>(&I)) {
+      if (Function *Callee = CB->getCalledFunction()) {
         if (Visited.insert(Callee).second && !Callee->isDeclaration()) {
           Node *CalleeN = G.lookup(*Callee);
           if (!CalleeN) {
             CalleeN = &G.get(*Callee);
             NewNodes.insert(CalleeN);
           }
           Edge *E = N->lookup(*CalleeN);
           assert((E || !FunctionPass) &&
                  "No function transformations should introduce *new* "
                  "call edges! Any new calls should be modeled as "
                  "promoted existing ref edges!");
           bool Inserted = RetainedEdges.insert(CalleeN).second;
           (void)Inserted;
           assert(Inserted && "We should never visit a function twice.");
           if (!E)
             NewCallEdges.insert(CalleeN);
           else if (!E->isCall())
             PromotedRefTargets.insert(CalleeN);
         }
+      } else {
+        auto *Entry = UR.IndirectVHs.find(CB);
+        if (Entry == UR.IndirectVHs.end() || !Entry->second)
+          UR.IndirectVHs.insert({CB, WeakTrackingVH(CB)});
+      }
+    }
+  }
 
   // Now walk all references.
   for (Instruction &I : instructions(F))
     for (Value *Op : I.operand_values())
       if (auto *C = dyn_cast<Constant>(Op))
         if (Visited.insert(C).second)
           Worklist.push_back(C);
 

llvm/lib/Passes/PassBuilder.cpp

if (Name.getAsInteger(0, Count) || Count <= 0)
     return None;
   return Count;
 }
 
 static Optional<int> parseDevirtPassName(StringRef Name) {
   if (!Name.consume_front("devirt<") || !Name.consume_back(">"))
     return None;
   int Count;
-  if (Name.getAsInteger(0, Count) || Count <= 0)
+  if (Name.getAsInteger(0, Count) || Count < 0)
     return None;
   return Count;
 }
 
 static bool checkParametrizedPassName(StringRef Name, StringRef PassName) {
   if (!Name.consume_front(PassName))
     return false;
   // normal pass name w/o parameters == default parameters

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

 ; RUN: opt -basic-aa -S -O2 < %s | FileCheck %s
+; RUN: opt -aa-pipeline=basic-aa -S -passes='default<O2>' < %s | FileCheck %s
 ; PR5009
 
 ; CHECK: define i32 @main() 
 ; CHECK-NEXT: entry:
 ; CHECK-NEXT:  call void @exit(i32 38) 
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-apple-darwin10.0.0"

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

+; RUN: opt -abort-on-max-devirt-iterations-reached -passes='cgscc(devirt<1>(inline,instcombine))' -S < %s | FileCheck %s
+; RUN: opt -abort-on-max-devirt-iterations-reached -passes='default<O2>' -S < %s | FileCheck %s
+
+define i32 @i() alwaysinline {
+  ret i32 45
+}
+
+; CHECK-LABEL: define i32 @main
+; CHECK-NEXT: ret i32 45
+
+define i32 @main() {
+  %a = alloca i32 ()*
+  store i32 ()* @i, i32 ()** %a
+  %r = call i32 @call(i32 ()** %a)
+  ret i32 %r
+}
+
+define i32 @call(i32 ()** %a) alwaysinline {
+  %c = load i32 ()*, i32 ()** %a
+  %r = call i32 %c()
+  ret i32 %r
+}

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

+; Make sure we don't detect devirtualization on inlining a function with a direct call
+; RUN: opt -abort-on-max-devirt-iterations-reached -passes='cgscc(devirt<0>(inline))' -S < %s | FileCheck %s
+
+define i32 @i() noinline {
+  ret i32 45
+}
+
+; CHECK-NOT: call i32 @call()
+
+define i32 @main() {
+  %r = call i32 @call()
+  ret i32 %r
+}
+
+define i32 @call() alwaysinline {
+  %r = call i32 @i()
+  ret i32 %r
+}

llvm/test/Transforms/Inline/devirtualize.ll

 ; RUN: opt -S -Os < %s | FileCheck %s
+; RUN: opt -S -aa-pipeline=basic-aa -passes='default<Os>' < %s | FileCheck %s
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
 target triple = "x86_64-apple-darwin10.0.0"
 
 
 ; Simple devirt testcase, requires iteration between inliner and GVN.
 ;  rdar://6295824
 define i32 @foo(i32 ()** noalias %p, i64* noalias %q) nounwind ssp {
 entry: