[OpenMPOpt] Most SCC's are uninteresting, don't waste time on them (up to 16x faster)

[lebedev.ri]

Summary

This seems obvious in hindsight, but the result is surprising.
I've measured compile-time of -openmpopt pass standalone
on RawSpeed unity build, and while there is some OpenMP stuff,
most is not OpenMP. But nonetheless the pass does a lot of costly
preparations before ever trying to look for OpenMP stuff in SCC.

Numbers (n=25): 0.094624s -> 0.005976s, an -93.68% improvement, or ~16x

[lebedev.ri]

Fix typo.

[lebedev.ri]

As per IRC disscussion, let's do the (identical!) check in another way,
by recording in a set which functions are known to have openmp runtime calls,
and simply looking each function in SCC in that set.
This appears to be identical in the sense of detection
(though, if the omp functions are used only by constantexprs, we'll miss those cases.),
and at least not worse performance-wise.

As a bonus, works for NewPM!

[jdoerfert]

LGTM, thanks for discovering and fixing this :)

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

1415–1421

1. For now ;)
2. missing ., also above.

[lebedev.ri]

In D84689#2176981, @jdoerfert wrote:

LGTM, thanks for discovering and fixing this :)

Thank you for review! :)

llvm/include/llvm/Transforms/IPO/OpenMPOpt.h

if (Found)
       Value = OpenMPInModule::OpenMP::FOUND;
     else
       Value = OpenMPInModule::OpenMP::NOT_FOUND;
     return *this;
   }
   bool isKnown() { return Value != OpenMP::UNKNOWN; }
   operator bool() { return Value != OpenMP::NOT_FOUND; }
 
+  /// Does this function \p F contain any OpenMP runtime calls?
+  bool containsOMPRuntimeCalls(Function *F) const {
+    return FuncsWithOMPRuntimeCalls.contains(F);
+  }
+
   /// Return the known kernels (=GPU entry points) in the module.
   SmallPtrSetImpl<Kernel> &getKernels() { return Kernels; }
 
   /// Identify kernels in the module and populate the Kernels set.
   void identifyKernels(Module &M);
 
 private:
   enum class OpenMP { FOUND, NOT_FOUND, UNKNOWN } Value = OpenMP::UNKNOWN;
 
+  friend bool containsOpenMP(Module &M, OpenMPInModule &OMPInModule);
+
+  /// In which functions are OpenMP runtime calls present?
+  SmallPtrSet<Function *, 32> FuncsWithOMPRuntimeCalls;
+
   /// Collection of known kernels (=GPU entry points) in the module.
   SmallPtrSet<Kernel, 8> Kernels;
 };
 
 /// Helper to determine if \p M contains OpenMP (runtime calls).
 bool containsOpenMP(Module &M, OpenMPInModule &OMPInModule);
 
 } // namespace omp

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

PreservedAnalyses OpenMPOptPass::run(LazyCallGraph::SCC &C,
                                      LazyCallGraph &CG, CGSCCUpdateResult &UR) {
   if (!containsOpenMP(*C.begin()->getFunction().getParent(), OMPInModule))
     return PreservedAnalyses::all();
 
   if (DisableOpenMPOptimizations)
     return PreservedAnalyses::all();
 
   SmallVector<Function *, 16> SCC;
-  for (LazyCallGraph::Node &N : C)
-    SCC.push_back(&N.getFunction());
+  // If there are kernels in the module, we have to run on all SCC's.
+  bool SCCIsInteresting = !OMPInModule.getKernels().empty();
+  for (LazyCallGraph::Node &N : C) {
+    Function *Fn = &N.getFunction();
+    SCC.push_back(Fn);
 
-  if (SCC.empty())
+    // Do we already know that the SCC contains kernels,
+    // or that OpenMP functions are called from this SCC?
+    if (SCCIsInteresting)
+      continue;
+    // If not, let's check that.
+    SCCIsInteresting |= OMPInModule.containsOMPRuntimeCalls(Fn);
+  }
+
+  if (!SCCIsInteresting || SCC.empty())
     return PreservedAnalyses::all();
 
   FunctionAnalysisManager &FAM =
       AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
 
   AnalysisGetter AG(FAM);
 
   auto OREGetter = [&FAM](Function *F) -> OptimizationRemarkEmitter & {
struct OpenMPOptLegacyPass : public CallGraphSCCPass {
 
   bool runOnSCC(CallGraphSCC &CGSCC) override {
     if (!containsOpenMP(CGSCC.getCallGraph().getModule(), OMPInModule))
       return false;
     if (DisableOpenMPOptimizations || skipSCC(CGSCC))
       return false;
 
     SmallVector<Function *, 16> SCC;
-    for (CallGraphNode *CGN : CGSCC)
-      if (Function *Fn = CGN->getFunction())
-        if (!Fn->isDeclaration())
-          SCC.push_back(Fn);
+    // If there are kernels in the module, we have to run on all SCC's.
+    bool SCCIsInteresting = !OMPInModule.getKernels().empty();
+    for (CallGraphNode *CGN : CGSCC) {
+      Function *Fn = CGN->getFunction();
+      if (!Fn || Fn->isDeclaration())
+        continue;
 
-    if (SCC.empty())
+      // Do we already know that the SCC contains kernels,
+      // or that OpenMP functions are called from this SCC?
+      if (SCCIsInteresting)
+        continue;
+      // If not, let's check that.
+      SCCIsInteresting |= OMPInModule.containsOMPRuntimeCalls(Fn);
+    }
+
+    if (!SCCIsInteresting || SCC.empty())
       return false;
 
     CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
     CGUpdater.initialize(CG, CGSCC);
 
     // Maintain a map of functions to avoid rebuilding the ORE
     DenseMap<Function *, std::unique_ptr<OptimizationRemarkEmitter>> OREMap;
     auto OREGetter = [&OREMap](Function *F) -> OptimizationRemarkEmitter & {
for (auto *Op : MD->operands()) {
     Kernels.insert(KernelFn);
   }
 }
 
 bool llvm::omp::containsOpenMP(Module &M, OpenMPInModule &OMPInModule) {
   if (OMPInModule.isKnown())
     return OMPInModule;
 
+  auto RecordFunctionsContainingUsesOf = [&](Function *F) {
+    for (User *U : F->users())
+      if (auto *I = dyn_cast<Instruction>(U))
+        OMPInModule.FuncsWithOMPRuntimeCalls.insert(I->getFunction());
+  };
+
   // MSVC doesn't like long if-else chains for some reason and instead just
   // issues an error. Work around it..
   do {
 #define OMP_RTL(_Enum, _Name, ...)                                             \
-  if (M.getFunction(_Name)) {                                                  \
+  if (Function *F = M.getFunction(_Name)) {                                    \
+    RecordFunctionsContainingUsesOf(F);                                        \
     OMPInModule = true;                                                        \
-    break;                                                                     \
   }
 #include "llvm/Frontend/OpenMP/OMPKinds.def"
   } while (false);
 
   // Identify kernels once. TODO: We should split the OMPInformationCache into a
   // module and an SCC part. The kernel information, among other things, could
   // go into the module part.
   if (OMPInModule.isKnown() && OMPInModule) {