[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

1408–1413

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; }
 
+  /// Is this function \p F an OpenMP function that is known ot be called
+  /// in the module?
+  bool isOMPReferencedFunction(Function *F) const {
+    return OMPFuncs.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);
+
+  /// Which OpenMP functions are called in this module?
+  SmallPtrSet<Function *, 32> OMPFuncs;
+
   /// 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,
 
   if (DisableOpenMPOptimizations)
     return PreservedAnalyses::all();
 
   SmallVector<Function *, 16> SCC;
   for (LazyCallGraph::Node &N : C)
     SCC.push_back(&N.getFunction());
 
+  // FIXME: skip SCC's that don't contain calls to OpenMP functions.
+  // The problem is that those OpenMP functions are declarations,
+  // and LazyCallGraph currently does not track them.
+
   if (SCC.empty())
     return PreservedAnalyses::all();
 
   FunctionAnalysisManager &FAM =
       AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
 
   AnalysisGetter AG(FAM);
 
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);
+    bool InterestingSCC = !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 (InterestingSCC)
+        continue;
+      // If not, let's check that.
+      InterestingSCC |= any_of(*CGN, [&](CallGraphNode::CallRecord Callee) {
+        return OMPInModule.isOMPReferencedFunction(
+            Callee.second->getFunction());
+      });
+    }
+
+    if (!InterestingSCC || 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 & {

 bool llvm::omp::containsOpenMP(Module &M, OpenMPInModule &OMPInModule) {
   if (OMPInModule.isKnown())
     return OMPInModule;
 
   // 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)) {                                    \
+    OMPInModule.OMPFuncs.insert(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) {