From 3024fe5b55ed72633915f613bd5e2826583c396f Mon Sep 17 00:00:00 2001 From: Arthur Eubanks Date: Wed, 14 Oct 2020 17:56:38 -0700 Subject: [PATCH] [CGSCC] Detect devirtualization in more cases 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). Reviewed By: asbirlea Differential Revision: https://reviews.llvm.org/D89587 --- llvm/include/llvm/Analysis/CGSCCPassManager.h | 46 +++++++-------------------- llvm/lib/Analysis/CGSCCPassManager.cpp | 1 + llvm/test/Transforms/Inline/devirtualize-3.ll | 1 + llvm/test/Transforms/Inline/devirtualize-5.ll | 22 +++++++++++++ llvm/test/Transforms/Inline/devirtualize.ll | 1 + 5 files changed, 36 insertions(+), 35 deletions(-) create mode 100644 llvm/test/Transforms/Inline/devirtualize-5.ll diff --git a/llvm/include/llvm/Analysis/CGSCCPassManager.h b/llvm/include/llvm/Analysis/CGSCCPassManager.h index 755bc92..5f2e50e 100644 --- a/llvm/include/llvm/Analysis/CGSCCPassManager.h +++ b/llvm/include/llvm/Analysis/CGSCCPassManager.h @@ -314,6 +314,9 @@ struct CGSCCUpdateResult { /// for a better technique. SmallDenseSet, 4> &InlinedInternalEdges; + + /// If any calls in the current SCC were devirtualized. + bool Devirtualized; }; /// The core module pass which does a post-order walk of the SCCs and @@ -596,9 +599,6 @@ public: // a pointer that we can update. LazyCallGraph::SCC *C = &InitialC; - // Collect value handles for all of the indirect call sites. - SmallVector CallHandles; - // Struct to track the counts of direct and indirect calls in each function // of the SCC. struct CallCount { @@ -608,10 +608,7 @@ public: // 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 &CallHandles) { - assert(CallHandles.empty() && "Must start with a clear set of handles."); - + auto ScanSCC = [](LazyCallGraph::SCC &C) { SmallDenseMap CallCounts; CallCount CountLocal = {0, 0}; for (LazyCallGraph::Node &N : C) { @@ -624,7 +621,6 @@ public: ++Count.Direct; } else { ++Count.Indirect; - CallHandles.push_back(WeakTrackingVH(&I)); } } } @@ -633,13 +629,14 @@ public: }; // Populate the initial call handles and get the initial call counts. - auto CallCounts = ScanSCC(*C, CallHandles); + auto CallCounts = ScanSCC(*C); for (int Iteration = 0;; ++Iteration) { - if (!PI.runBeforePass(Pass, *C)) continue; + UR.Devirtualized = false; + PreservedAnalyses PassPA = Pass.run(*C, AM, CG, UR); if (UR.InvalidatedSCCs.count(C)) @@ -658,34 +655,12 @@ public: 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(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. - return true; - }; - bool Devirt = llvm::any_of(CallHandles, IsDevirtualizedHandle); + bool Devirt = UR.Devirtualized; // 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); + auto NewCallCounts = ScanSCC(*C); // If we haven't found an explicit devirtualization already see if we // have decreased the number of indirect calls and increased the number @@ -790,7 +765,8 @@ ModuleToPostOrderCGSCCPassAdaptor::run(Module &M, 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. diff --git a/llvm/lib/Analysis/CGSCCPassManager.cpp b/llvm/lib/Analysis/CGSCCPassManager.cpp index 61c03f9..206088b 100644 --- a/llvm/lib/Analysis/CGSCCPassManager.cpp +++ b/llvm/lib/Analysis/CGSCCPassManager.cpp @@ -666,6 +666,7 @@ static LazyCallGraph::SCC &updateCGAndAnalysisManagerForPass( // Now promote ref edges into call edges. for (Node *CallTarget : PromotedRefTargets) { + UR.Devirtualized = true; SCC &TargetC = *G.lookupSCC(*CallTarget); RefSCC &TargetRC = TargetC.getOuterRefSCC(); diff --git a/llvm/test/Transforms/Inline/devirtualize-3.ll b/llvm/test/Transforms/Inline/devirtualize-3.ll index 4165b21..987463a 100644 --- a/llvm/test/Transforms/Inline/devirtualize-3.ll +++ b/llvm/test/Transforms/Inline/devirtualize-3.ll @@ -1,4 +1,5 @@ ; RUN: opt -basic-aa -S -O2 < %s | FileCheck %s +; RUN: opt -aa-pipeline=basic-aa -S -passes='default' < %s | FileCheck %s ; PR5009 ; CHECK: define i32 @main() diff --git a/llvm/test/Transforms/Inline/devirtualize-5.ll b/llvm/test/Transforms/Inline/devirtualize-5.ll new file mode 100644 index 0000000..359c8e1 --- /dev/null +++ b/llvm/test/Transforms/Inline/devirtualize-5.ll @@ -0,0 +1,22 @@ +; RUN: opt -abort-on-max-devirt-iterations-reached -passes='cgscc(devirt<2>(inline,instcombine))' -S < %s | FileCheck %s +; RUN: opt -abort-on-max-devirt-iterations-reached -passes='default' -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 +} diff --git a/llvm/test/Transforms/Inline/devirtualize.ll b/llvm/test/Transforms/Inline/devirtualize.ll index 561bb62..eaba1a8 100644 --- a/llvm/test/Transforms/Inline/devirtualize.ll +++ b/llvm/test/Transforms/Inline/devirtualize.ll @@ -1,4 +1,5 @@ ; RUN: opt -S -Os < %s | FileCheck %s +; RUN: opt -S -aa-pipeline=basic-aa -passes='default' < %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" -- 2.7.4