[OpenMP] Introduce the OpenMPOpt transformation pass

[jdoerfert]

Summary

The OpenMPOpt pass is a CG-SCC pass in which OpenMP specific
optimizations can reside.

The OpenMPOpt pass uses the OpenMPKinds.def file to identify runtime
calls and their uses. This allows targeted transformations and eases
their implementation.

This initial patch deduplicates __kmpc_global_thread_num calls. We can
also identify arguments that are equivalent to such a call result and
use it instead. Later we can determine "gtid" arguments based on the use
in kernel functions etc.

[jdoerfert]

Remove leftover change

[jdoerfert]

Rebase after types moved to a central location

[lebedev.ri]

No old-pm?

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

49

IsVarArg

84

reusing

105

reusing

[jdoerfert]

Add old-PM support and fix typos

[jdoerfert]

Make sure to remove cached uses when calls are removed

[ABataev]

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

20

Better to use class? Also, maybe worth it to mark it as final.

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

146

What if the function is already in the entry block?

[jdoerfert]

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

20

I can do that but I do not understand why this would be better (in a lot of situations, including this one).
After all, class will just cause an additional public and that is it (for all but MSVC and only if we declare this struct/class again which we never do). Similarly, I have never seen an attempt to inherit from a new-PM style pass and if so it is unclear why we should forbid it (with final).

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

146

Not a problem and not sufficient:

If we have the following entry and the first use we visit is (for some reason) %gtid1 we need to move it because it would not dominate the use of %gtid0.

entry:
  %gtid0 = call __kmpc_global_thread_num ...
  ... use(%gtid0)
  %gtid1 = call __kmpc_global_thread_num ...

[ABataev]

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

20

Up to you. But if you going to have private or protected members later, better to make class rather than struct.

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

146

The question is a little bit different. What if we have something simple:

entry:
  %gtid0 = call __kmpc_global_thread_num ...
  ... use(%gtid0)

Will this pass try to move the call after the use? I'm not saying that this will definitely happen, I'm just asking if pass of aware of such situation and will handle it properly.

[jdoerfert]

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

20

Up to you. But if you going to have private or protected members later, better to make class rather than struct.

Why? They are the same except the default visibility.

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

146

This moves the call unconditionally to the very first position in a function. That is by definition before all uses. We can add smarts wrt. the placement later.

[ABataev]

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

20

Coding standard

[jdoerfert]

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

20

The Coding standard states, as a rule of thumb, that the right choice here is a struct:

https://llvm.org/docs/CodingStandards.html#use-of-class-and-struct-keywords

[ABataev]

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

20

But if you going to have private or protected members later, better to make class rather than struct.

[jdoerfert]

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

20

The important point is, this does not have a private or protected member now.

There are two things to my argument:

1. We do not design for what might or might not happen as that regularly results in bad design decisions. Assuming one would later change something, e.g., add a protected member, once could change the struct to a class.
2. It is unrealistic to assume a PassInfoMixin object like this one to ever have more members. This is just an interface for the pass manager to interact with the pass, and while there are exceptions, most of these interfaces I've seen only contain a run method.

[ABataev]

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

20

Just like I said, it is up to you. It was just a suggestion to avoid future possible modifications.

[jdoerfert]

Anything else?

[jdoerfert]

ping

[lebedev.ri]

I'm really not the best person to review this :/
It seems generally within what'd expect, but i'm not really familiar with SCC passes.
Some thoughts:

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

36

Traditionally DEBUG_TYPE itself is used for this.

117

I'm guessing this is 'llvm::for_each() but until first match'?
Maybe something like

Value *GTIdArg = find_if() be better?

215–216

Here and elsewhere: i'm guessing AddUserArgs() will update GTIdArgs so it must not be range-based for and we can't precache GTIdArgs.size(). This should be commented.

[jdoerfert]

In D69930#1757865, @lebedev.ri wrote:

I'm really not the best person to review this :/

No one (I ask) seems to be. At some point, I argue, it should be enough that it looks good to multiple "non-experts". We can always revert it.
Though, I will make it easier, see below.

It seems generally within what'd expect, but i'm not really familiar with SCC passes.

I will add a call graph helper soon, given that I think I figured out how to use both of them.
I hope @chandlerc or someone else familiar with both call graphs (for old & new pass manager) will review them.
Assuming that works, there is little SCC related left that is not "provided" by this helper.

Some thoughts:

I'll adjust according to your comments shortly.

[lebedev.ri]

Also, this is missing some statistics, and maybe some debug counters.

[JonChesterfield]

The plumbing looks sane to me. I imagine any bugs or limitations we miss at review will make themselves apparent as more complicated optimisations are included.

@ABataev do you have remaining concerns with the current patch?

[jdoerfert]

In D69930#1758037, @lebedev.ri wrote:

Also, this is missing some statistics, and maybe some debug counters.

I'll rebase soon and add them.

[jdoerfert]

Use D70927, address comments, introduce some statistic counters

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[jdoerfert]

Rebase

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[jdoerfert]

Explicitly check for OpenMP runtime calls and stand down if none found.

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[jdoerfert]

Replace llvm::find_if with an explicit loop that works

[merge_guards_bot]

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[lebedev.ri]

Some nits.
I think this should proceed, the intersection between "llvm developers"
and "openmp developers" appears to be only forming, and it can't possibly ever form
if the patches that form it are stuck waiting for the intersection to form :)

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

32

enum struct

llvm/lib/Passes/PassBuilder.cpp

841–843

Personally, i'd think this should only be run in -O2 and higher (i.e. not under -O0/-O1)

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

145–146

Should there be a debug counter controlled early exit as the first line of function?

[jdoerfert]

Addressed comments

[JonChesterfield]

Still looks good to me. I'll even mark it as such.

Agreed with the above sentiment - we need the infra to build on in order to progress.

[wenlei]

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

159

I think you need to make sure it's not moved before the def of the operand for openmp calls.

I'm seeing a case where __kmpc_global_thread_num has a parameter, and the call is moved to before def of parameter, see snippet below.

%5           = call i32 @__kmpc_global_thread_num(%struct.ident_t* nonnull %6)
%6           = alloca %struct.ident_t, align 8

[xiaoqing_wu]

This line needs to be guarded with #if !defined(NDEBUG) to prevent warning-as-error failures in release build.

static constexpr auto TAG = "[" DEBUG_TYPE "]";

The change made in https://reviews.llvm.org/rGa50c0b0df733423f9f6f92bb4e0be26f73326ae3 is not sufficient to prevent release build issue. Could you fix this? Thanks!

[jdoerfert]

In D69930#1900147, @xiaoqing_wu wrote:

This line needs to be guarded with #if !defined(NDEBUG) to prevent warning-as-error failures in release build.

static constexpr auto TAG = "[" DEBUG_TYPE "]";

The change made in https://reviews.llvm.org/rGa50c0b0df733423f9f6f92bb4e0be26f73326ae3 is not sufficient to prevent release build issue. Could you fix this? Thanks!

I don't understand why this is not sufficient. Could you explain that please? (I usually test with release+asserts)

llvm/lib/Passes/PassBuilder.cpp

841–843

I can do that.

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

145–146

I don't understand what you want here, could you explain?

[lebedev.ri]

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

145–146

http://llvm.org/docs/ProgrammersManual.html#adding-debug-counters-to-aid-in-debugging-your-code

[xiaoqing_wu]

In D69930#1901384, @jdoerfert wrote:

In D69930#1900147, @xiaoqing_wu wrote:

This line needs to be guarded with #if !defined(NDEBUG) to prevent warning-as-error failures in release build.

static constexpr auto TAG = "[" DEBUG_TYPE "]";

The change made in https://reviews.llvm.org/rGa50c0b0df733423f9f6f92bb4e0be26f73326ae3 is not sufficient to prevent release build issue. Could you fix this? Thanks!

I don't understand why this is not sufficient. Could you explain that please? (I usually test with release+asserts

! In D69930#1901384, @jdoerfert wrote:

! In D69930#1900147, @xiaoqing_wu wrote:

This line needs to be guarded with #if !defined(NDEBUG) to prevent warning-as-error failures in release build.

static constexpr auto TAG = "[" DEBUG_TYPE "]";

The change made in https://reviews.llvm.org/rGa50c0b0df733423f9f6f92bb4e0be26f73326ae3 is not sufficient to prevent release build issue. Could you fix this? Thanks!

I don't understand why this is not sufficient. Could you explain that please? (I usually test with release+asserts)

TAG is only used when NDEBUG is not defined. It's not used when NDEBUG is not defined and LLVM_ENABLE_DUMP is enabled. To reproduce this, run cmake with these options: -DLLVM_ENABLE_DUMP=On -DCMAKE_BUILD_TYPE=Release -DLLVM_ENABLE_ASSERTIONS=Off.

[jdoerfert]

In D69930#1910922, @xiaoqing_wu wrote:

In D69930#1901384, @jdoerfert wrote:

In D69930#1900147, @xiaoqing_wu wrote:

This line needs to be guarded with #if !defined(NDEBUG) to prevent warning-as-error failures in release build.

static constexpr auto TAG = "[" DEBUG_TYPE "]";

The change made in https://reviews.llvm.org/rGa50c0b0df733423f9f6f92bb4e0be26f73326ae3 is not sufficient to prevent release build issue. Could you fix this? Thanks!

I don't understand why this is not sufficient. Could you explain that please? (I usually test with release+asserts

! In D69930#1901384, @jdoerfert wrote:

! In D69930#1900147, @xiaoqing_wu wrote:

This line needs to be guarded with #if !defined(NDEBUG) to prevent warning-as-error failures in release build.

static constexpr auto TAG = "[" DEBUG_TYPE "]";

The change made in https://reviews.llvm.org/rGa50c0b0df733423f9f6f92bb4e0be26f73326ae3 is not sufficient to prevent release build issue. Could you fix this? Thanks!

I don't understand why this is not sufficient. Could you explain that please? (I usually test with release+asserts)

TAG is only used when NDEBUG is not defined. It's not used when NDEBUG is not defined and LLVM_ENABLE_DUMP is enabled. To reproduce this, run cmake with these options: -DLLVM_ENABLE_DUMP=On -DCMAKE_BUILD_TYPE=Release -DLLVM_ENABLE_ASSERTIONS=Off.

Sorry for the wait, I got side-tracked bad. Should be fixed by D75970.

llvm/include/llvm/Frontend/OpenMP/OMPKinds.def

 __OMP_RTL(__kmpc_push_num_threads, false, Void, IdentPtr, Int32,
           /* Int */ Int32)
 __OMP_RTL(__kmpc_push_proc_bind, false, Void, IdentPtr, Int32, /* Int */ Int32)
 __OMP_RTL(__kmpc_serialized_parallel, false, Void, IdentPtr, Int32)
 __OMP_RTL(__kmpc_end_serialized_parallel, false, Void, IdentPtr, Int32)
 
 __OMP_RTL(omp_get_thread_num, false, Int32, )
 
+__OMP_RTL(__last, false, Void, )
+
 #undef __OMP_RTL
 #undef OMP_RTL
 
 #define EnumAttr(Kind) Attribute::get(Ctx, Attribute::AttrKind::Kind)
 #define AttributeSet(...)                                                      \
   AttributeSet::get(Ctx, ArrayRef<Attribute>({__VA_ARGS__}))
 
 #ifndef OMP_ATTRS_SET

llvm/include/llvm/InitializePasses.h

 void initializeAddDiscriminatorsLegacyPassPass(PassRegistry&);
 void initializeModuleAddressSanitizerLegacyPassPass(PassRegistry &);
 void initializeASanGlobalsMetadataWrapperPassPass(PassRegistry &);
 void initializeAddressSanitizerLegacyPassPass(PassRegistry &);
 void initializeAggressiveInstCombinerLegacyPassPass(PassRegistry&);
 void initializeAliasSetPrinterPass(PassRegistry&);
 void initializeAlignmentFromAssumptionsPass(PassRegistry&);
 void initializeAlwaysInlinerLegacyPassPass(PassRegistry&);
+void initializeOpenMPOptLegacyPassPass(PassRegistry &);
 void initializeArgPromotionPass(PassRegistry&);
 void initializeAssumptionCacheTrackerPass(PassRegistry&);
 void initializeAtomicExpandPass(PassRegistry&);
 void initializeAttributorLegacyPassPass(PassRegistry&);
 void initializeBDCELegacyPassPass(PassRegistry&);
 void initializeBarrierNoopPass(PassRegistry&);
 void initializeBasicAAWrapperPassPass(PassRegistry&);
 void initializeBlockExtractorPass(PassRegistry &);

llvm/include/llvm/LinkAllPasses.h

ForcePassLinking() {
       // to know that getenv() never returns -1, this will do the job.
       if (std::getenv("bar") != (char*) -1)
         return;
 
       (void) llvm::createAAEvalPass();
       (void) llvm::createAggressiveDCEPass();
       (void) llvm::createAggressiveInstCombinerPass();
       (void) llvm::createBitTrackingDCEPass();
+      (void) llvm::createOpenMPOptLegacyPass();
       (void) llvm::createArgumentPromotionPass();
       (void) llvm::createAlignmentFromAssumptionsPass();
       (void) llvm::createBasicAAWrapperPass();
       (void) llvm::createSCEVAAWrapperPass();
       (void) llvm::createTypeBasedAAWrapperPass();
       (void) llvm::createScopedNoAliasAAWrapperPass();
       (void) llvm::createBoundsCheckingLegacyPass();
       (void) llvm::createBreakCriticalEdgesPass();

llvm/include/llvm/Transforms/IPO.h

 //===----------------------------------------------------------------------===//
 /// createArgumentPromotionPass - This pass promotes "by reference" arguments to
 /// be passed by value if the number of elements passed is smaller or
 /// equal to maxElements (maxElements == 0 means always promote).
 ///
 Pass *createArgumentPromotionPass(unsigned maxElements = 3);
 
 //===----------------------------------------------------------------------===//
+/// createOpenMPOptLegacyPass - OpenMP specific optimizations.
+Pass *createOpenMPOptLegacyPass();
+
+//===----------------------------------------------------------------------===//
 /// createIPConstantPropagationPass - This pass propagates constants from call
 /// sites into the bodies of functions.
 ///
 ModulePass *createIPConstantPropagationPass();
 
 //===----------------------------------------------------------------------===//
 /// createIPSCCPPass - This pass propagates constants from call sites into the
 /// bodies of functions, and keeps track of whether basic blocks are executable

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

+//===- IPO/OpenMPOpt.h - Collection of OpenMP optimizations -----*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_OPENMP_OPT_H
+#define LLVM_TRANSFORMS_IPO_OPENMP_OPT_H
+
+#include "llvm/Analysis/CGSCCPassManager.h"
+#include "llvm/Analysis/LazyCallGraph.h"
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+namespace omp {
+
+/// Helper to remember if the module contains OpenMP (runtime calls), to be used
+/// foremost with containsOpenMP.
+struct OpenMPInModule {
+  OpenMPInModule &operator=(bool Found) {
+    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; }
+
+private:
+  enum class OpenMP { FOUND, NOT_FOUND, UNKNOWN } Value = OpenMP::UNKNOWN;
+};
+
+/// Helper to determine if \p M contains OpenMP (runtime calls).
+bool containsOpenMP(Module &M, OpenMPInModule &OMPInModule);
+
+} // namespace omp
+
+/// OpenMP optimizations pass.
+class OpenMPOptPass : public PassInfoMixin<OpenMPOptPass> {
+  /// Helper to remember if the module contains OpenMP (runtime calls).
+  omp::OpenMPInModule OMPInModule;
+
+public:
+  PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
+                        LazyCallGraph &CG, CGSCCUpdateResult &UR);
+};
+
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_IPO_OPENMP_OPT_H

llvm/lib/LTO/LTOCodeGenerator.cpp

void LTOCodeGenerator::initializeLTOPasses() {
   initializeIPSCCPLegacyPassPass(R);
   initializeGlobalOptLegacyPassPass(R);
   initializeConstantMergeLegacyPassPass(R);
   initializeDAHPass(R);
   initializeInstructionCombiningPassPass(R);
   initializeSimpleInlinerPass(R);
   initializePruneEHPass(R);
   initializeGlobalDCELegacyPassPass(R);
+  initializeOpenMPOptLegacyPassPass(R);
   initializeArgPromotionPass(R);
   initializeJumpThreadingPass(R);
   initializeSROALegacyPassPass(R);
   initializeAttributorLegacyPassPass(R);
   initializePostOrderFunctionAttrsLegacyPassPass(R);
   initializeReversePostOrderFunctionAttrsLegacyPassPass(R);
   initializeGlobalsAAWrapperPassPass(R);
   initializeLegacyLICMPassPass(R);

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/IPO/GlobalOpt.h"
 #include "llvm/Transforms/IPO/GlobalSplit.h"
 #include "llvm/Transforms/IPO/HotColdSplitting.h"
 #include "llvm/Transforms/IPO/InferFunctionAttrs.h"
 #include "llvm/Transforms/IPO/Inliner.h"
 #include "llvm/Transforms/IPO/Internalize.h"
 #include "llvm/Transforms/IPO/LowerTypeTests.h"
 #include "llvm/Transforms/IPO/MergeFunctions.h"
+#include "llvm/Transforms/IPO/OpenMPOpt.h"
 #include "llvm/Transforms/IPO/PartialInlining.h"
 #include "llvm/Transforms/IPO/SCCP.h"
 #include "llvm/Transforms/IPO/SampleProfile.h"
 #include "llvm/Transforms/IPO/StripDeadPrototypes.h"
 #include "llvm/Transforms/IPO/SyntheticCountsPropagation.h"
 #include "llvm/Transforms/IPO/WholeProgramDevirt.h"
 #include "llvm/Transforms/InstCombine/InstCombine.h"
 #include "llvm/Transforms/Instrumentation.h"
PassBuilder::buildModuleSimplificationPipeline(OptimizationLevel Level,
   // Now deduce any function attributes based in the current code.
   MainCGPipeline.addPass(PostOrderFunctionAttrsPass());
 
   // When at O3 add argument promotion to the pass pipeline.
   // FIXME: It isn't at all clear why this should be limited to O3.
   if (Level == OptimizationLevel::O3)
     MainCGPipeline.addPass(ArgumentPromotionPass());
 
+  // Try to perform OpenMP specific optimizations. This is a (quick!) no-op if
+  // there are no OpenMP runtime calls present in the module.
+  if (Level == OptimizationLevel::O2 || Level == OptimizationLevel::O3)
+    MainCGPipeline.addPass(OpenMPOptPass());
+
   // Lastly, add the core function simplification pipeline nested inside the
   // CGSCC walk.
   MainCGPipeline.addPass(createCGSCCToFunctionPassAdaptor(
       buildFunctionSimplificationPipeline(Level, Phase, DebugLogging)));
 
   for (auto &C : CGSCCOptimizerLateEPCallbacks)
     C(MainCGPipeline, Level);
 

llvm/lib/Passes/PassRegistry.def

 
 #ifndef CGSCC_PASS
 #define CGSCC_PASS(NAME, CREATE_PASS)
 #endif
 CGSCC_PASS("argpromotion", ArgumentPromotionPass())
 CGSCC_PASS("invalidate<all>", InvalidateAllAnalysesPass())
 CGSCC_PASS("function-attrs", PostOrderFunctionAttrsPass())
 CGSCC_PASS("inline", InlinerPass())
+CGSCC_PASS("openmpopt", OpenMPOptPass())
 CGSCC_PASS("no-op-cgscc", NoOpCGSCCPass())
 #undef CGSCC_PASS
 
 #ifndef FUNCTION_ANALYSIS
 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)
 #endif
 FUNCTION_ANALYSIS("aa", AAManager())
 FUNCTION_ANALYSIS("assumptions", AssumptionAnalysis())

llvm/lib/Transforms/IPO/CMakeLists.txt

add_llvm_component_library(LLVMipo
   IPO.cpp
   InferFunctionAttrs.cpp
   InlineSimple.cpp
   Inliner.cpp
   Internalize.cpp
   LoopExtractor.cpp
   LowerTypeTests.cpp
   MergeFunctions.cpp
+  OpenMPOpt.cpp
   PartialInlining.cpp
   PassManagerBuilder.cpp
   PruneEH.cpp
   SampleProfile.cpp
   SCCP.cpp
   StripDeadPrototypes.cpp
   StripSymbols.cpp
   SyntheticCountsPropagation.cpp

llvm/lib/Transforms/IPO/IPO.cpp

 #include "llvm/InitializePasses.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/IPO/AlwaysInliner.h"
 #include "llvm/Transforms/IPO/FunctionAttrs.h"
 
 using namespace llvm;
 
 void llvm::initializeIPO(PassRegistry &Registry) {
+  initializeOpenMPOptLegacyPassPass(Registry);
   initializeArgPromotionPass(Registry);
   initializeCalledValuePropagationLegacyPassPass(Registry);
   initializeConstantMergeLegacyPassPass(Registry);
   initializeCrossDSOCFIPass(Registry);
   initializeDAEPass(Registry);
   initializeDAHPass(Registry);
   initializeForceFunctionAttrsLegacyPassPass(Registry);
   initializeGlobalDCELegacyPassPass(Registry);

llvm/lib/Transforms/IPO/LLVMBuild.txt

 ;
 ;===------------------------------------------------------------------------===;
 
 [component_0]
 type = Library
 name = IPO
 parent = Transforms
 library_name = ipo
-required_libraries = AggressiveInstCombine Analysis BitReader BitWriter Core InstCombine IRReader Linker Object ProfileData Scalar Support TransformUtils Vectorize Instrumentation
+required_libraries = AggressiveInstCombine Analysis BitReader BitWriter Core FrontendOpenMP InstCombine IRReader Linker Object ProfileData Scalar Support TransformUtils Vectorize Instrumentation

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

+//===-- IPO/OpenMPOpt.cpp - Collection of OpenMP specific optimizations ---===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// OpenMP specific optimizations:
+//
+// - Deduplication of runtime calls, e.g., omp_get_thread_num.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/IPO/OpenMPOpt.h"
+
+#include "llvm/ADT/EnumeratedArray.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/CallGraph.h"
+#include "llvm/Analysis/CallGraphSCCPass.h"
+#include "llvm/Frontend/OpenMP/OMPConstants.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/InitializePasses.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Transforms/IPO.h"
+#include "llvm/Transforms/Utils/CallGraphUpdater.h"
+
+using namespace llvm;
+using namespace omp;
+using namespace types;
+
+#define DEBUG_TYPE "openmp-opt"
+
+static cl::opt<bool> DisableOpenMPOptimizations(
+    "openmp-opt-disable", cl::ZeroOrMore,
+    cl::desc("Disable OpenMP specific optimizations."), cl::Hidden,
+    cl::init(false));
+
+STATISTIC(NumOpenMPRuntimeCallsDeduplicated,
+          "Number of OpenMP runtime calls deduplicated");
+STATISTIC(NumOpenMPRuntimeFunctionsIdentified,
+          "Number of OpenMP runtime functions identified");
+STATISTIC(NumOpenMPRuntimeFunctionUsesIdentified,
+          "Number of OpenMP runtime function uses identified");
+
+static constexpr auto TAG = "[" DEBUG_TYPE "]";
+
+namespace {
+struct OpenMPOpt {
+
+  OpenMPOpt(SmallPtrSetImpl<Function *> &SCC,
+            SmallPtrSetImpl<Function *> &ModuleSlice,
+            CallGraphUpdater &CGUpdater)
+      : M(*(*SCC.begin())->getParent()), SCC(SCC), ModuleSlice(ModuleSlice),
+        CGUpdater(CGUpdater) {
+    initializeTypes(M);
+    initializeRuntimeFunctions();
+  }
+
+  /// Generic information that describes a runtime function
+  struct RuntimeFunctionInfo {
+    /// The kind, as described by the RuntimeFunction enum.
+    RuntimeFunction Kind;
+
+    /// The name of the function.
+    StringRef Name;
+
+    /// Flag to indicate a variadic function.
+    bool IsVarArg;
+
+    /// The return type of the function.
+    Type *ReturnType;
+
+    /// The argument types of the function.
+    SmallVector<Type *, 8> ArgumentTypes;
+
+    /// The declaration if available.
+    Function *Declaration;
+
+    /// Uses of this runtime function per function containing the use.
+    DenseMap<Function *, SmallPtrSet<Use *, 16>> UsesMap;
+
+    /// Return the number of arguments (or the minimal number for variadic
+    /// functions).
+    size_t getNumArgs() const { return ArgumentTypes.size(); }
+
+    /// Run the callback \p CB on each use and forget the use if the result is
+    /// true. The callback will be fed the function in which the use was
+    /// encountered as second argument.
+    void foreachUse(function_ref<bool(Use &, Function &)> CB) {
+      SmallVector<Use *, 8> ToBeDeleted;
+      for (auto &It : UsesMap) {
+        ToBeDeleted.clear();
+        for (Use *U : It.second)
+          if (CB(*U, *It.first))
+            ToBeDeleted.push_back(U);
+        for (Use *U : ToBeDeleted)
+          It.second.erase(U);
+      }
+    }
+  };
+
+  /// Run all OpenMP optimizations on the underlying SCC/ModuleSlice.
+  bool run() {
+    bool Changed = false;
+
+    LLVM_DEBUG(dbgs() << TAG << "Run on SCC with " << SCC.size()
+                      << " functions in a slice with " << ModuleSlice.size()
+                      << " functions\n");
+
+    Changed |= deduplicateRuntimeCalls();
+
+    return Changed;
+  }
+
+private:
+  /// Try to eliminiate runtime calls by reusing existing ones.
+  bool deduplicateRuntimeCalls() {
+    bool Changed = false;
+
+    SmallSetVector<Value *, 16> GTIdArgs;
+    collectGlobalThreadIdArguments(GTIdArgs);
+    LLVM_DEBUG(dbgs() << TAG << "Found " << GTIdArgs.size()
+                      << " global thread ID arguments\n");
+
+    for (Function *F : SCC) {
+      Value *GTIdArg = nullptr;
+      for (Argument &Arg : F->args())
+        if (GTIdArgs.count(&Arg)) {
+          GTIdArg = &Arg;
+          break;
+        }
+      Changed |= deduplicateRuntimeCalls(
+          *F, RFIs[OMPRTL___kmpc_global_thread_num], GTIdArg);
+      Changed |= deduplicateRuntimeCalls(*F, RFIs[OMPRTL_omp_get_thread_num]);
+    }
+
+    return Changed;
+  }
+
+  /// Try to eliminiate calls of \p RFI in \p F by reusing an existing one or
+  /// \p ReplVal if given.
+  bool deduplicateRuntimeCalls(Function &F, RuntimeFunctionInfo &RFI,
+                               Value *ReplVal = nullptr) {
+    auto &Uses = RFI.UsesMap[&F];
+    if (Uses.size() + (ReplVal != nullptr) < 2)
+      return false;
+
+    LLVM_DEBUG(dbgs() << TAG << "Deduplicate " << Uses.size() << " uses of "
+                      << RFI.Name
+                      << (ReplVal ? " with an existing value\n" : "\n")
+                      << "\n");
+    assert(!ReplVal || (isa<Argument>(ReplVal) &&
+                        cast<Argument>(ReplVal)->getParent() == &F) &&
+                           "Unexpected replacement value!");
+    if (!ReplVal) {
+      for (Use *U : Uses)
+        if (CallInst *CI = getCallIfRegularCall(*U, &RFI)) {
+          CI->moveBefore(&*F.getEntryBlock().getFirstInsertionPt());
+          ReplVal = CI;
+          break;
+        }
+      if (!ReplVal)
+        return false;
+    }
+
+    bool Changed = false;
+    auto ReplaceAndDeleteCB = [&](Use &U, Function &Caller) {
+      CallInst *CI = getCallIfRegularCall(U, &RFI);
+      if (!CI || CI == ReplVal || &F != &Caller)
+        return false;
+      assert(CI->getCaller() == &F && "Unexpected call!");
+      CGUpdater.removeCallSite(*CI);
+      CI->replaceAllUsesWith(ReplVal);
+      CI->eraseFromParent();
+      ++NumOpenMPRuntimeCallsDeduplicated;
+      Changed = true;
+      return true;
+    };
+    RFI.foreachUse(ReplaceAndDeleteCB);
+
+    return Changed;
+  }
+
+  /// Collect arguments that represent the global thread id in \p GTIdArgs.
+  void collectGlobalThreadIdArguments(SmallSetVector<Value *, 16> &GTIdArgs) {
+    // TODO: Below we basically perform a fixpoint iteration with a pessimistic
+    //       initialization. We could define an AbstractAttribute instead and
+    //       run the Attributor here once it can be run as an SCC pass.
+
+    // Helper to check the argument \p ArgNo at all call sites of \p F for
+    // a GTId.
+    auto CallArgOpIsGTId = [&](Function &F, unsigned ArgNo, CallInst &RefCI) {
+      if (!F.hasLocalLinkage())
+        return false;
+      for (Use &U : F.uses()) {
+        if (CallInst *CI = getCallIfRegularCall(U)) {
+          Value *ArgOp = CI->getArgOperand(ArgNo);
+          if (CI == &RefCI || GTIdArgs.count(ArgOp) ||
+              getCallIfRegularCall(*ArgOp,
+                                   &RFIs[OMPRTL___kmpc_global_thread_num]))
+            continue;
+        }
+        return false;
+      }
+      return true;
+    };
+
+    // Helper to identify uses of a GTId as GTId arguments.
+    auto AddUserArgs = [&](Value &GTId) {
+      for (Use &U : GTId.uses())
+        if (CallInst *CI = dyn_cast<CallInst>(U.getUser()))
+          if (CI->isArgOperand(&U))
+            if (Function *Callee = CI->getCalledFunction())
+              if (CallArgOpIsGTId(*Callee, U.getOperandNo(), *CI))
+                GTIdArgs.insert(Callee->getArg(U.getOperandNo()));
+    };
+
+    // The argument users of __kmpc_global_thread_num calls are GTIds.
+    RuntimeFunctionInfo &GlobThreadNumRFI =
+        RFIs[OMPRTL___kmpc_global_thread_num];
+    for (auto &It : GlobThreadNumRFI.UsesMap)
+      for (Use *U : It.second)
+        if (CallInst *CI = getCallIfRegularCall(*U, &GlobThreadNumRFI))
+          AddUserArgs(*CI);
+
+    // Transitively search for more arguments by looking at the users of the
+    // ones we know already. During the search the GTIdArgs vector is extended
+    // so we cannot cache the size nor can we use a range based for.
+    for (unsigned u = 0; u < GTIdArgs.size(); ++u)
+      AddUserArgs(*GTIdArgs[u]);
+  }
+
+  /// Return the call if \p U is a callee use in a regular call. If \p RFI is
+  /// given it has to be the callee or a nullptr is returned.
+  CallInst *getCallIfRegularCall(Use &U, RuntimeFunctionInfo *RFI = nullptr) {
+    CallInst *CI = dyn_cast<CallInst>(U.getUser());
+    if (CI && CI->isCallee(&U) && !CI->hasOperandBundles() &&
+        (!RFI || CI->getCalledFunction() == RFI->Declaration))
+      return CI;
+    return nullptr;
+  }
+
+  /// Return the call if \p V is a regular call. If \p RFI is given it has to be
+  /// the callee or a nullptr is returned.
+  CallInst *getCallIfRegularCall(Value &V, RuntimeFunctionInfo *RFI = nullptr) {
+    CallInst *CI = dyn_cast<CallInst>(&V);
+    if (CI && !CI->hasOperandBundles() &&
+        (!RFI || CI->getCalledFunction() == RFI->Declaration))
+      return CI;
+    return nullptr;
+  }
+
+  /// Helper to initialize all runtime function information for those defined in
+  /// OpenMPKinds.def.
+  void initializeRuntimeFunctions() {
+    // Helper to collect all uses of the decleration in the UsesMap.
+    auto CollectUses = [&](RuntimeFunctionInfo &RFI) {
+      unsigned NumUses = 0;
+      if (!RFI.Declaration)
+        return NumUses;
+
+      NumOpenMPRuntimeFunctionsIdentified += 1;
+      NumOpenMPRuntimeFunctionUsesIdentified += RFI.Declaration->getNumUses();
+
+      // TODO: We directly convert uses into proper calls and unknown uses.
+      for (Use &U : RFI.Declaration->uses()) {
+        if (Instruction *UserI = dyn_cast<Instruction>(U.getUser())) {
+          if (ModuleSlice.count(UserI->getFunction())) {
+            RFI.UsesMap[UserI->getFunction()].insert(&U);
+            ++NumUses;
+          }
+        } else {
+          RFI.UsesMap[nullptr].insert(&U);
+          ++NumUses;
+        }
+      }
+      return NumUses;
+    };
+
+#define OMP_RTL(_Enum, _Name, _IsVarArg, _ReturnType, ...)                     \
+  {                                                                            \
+    auto &RFI = RFIs[_Enum];                                                   \
+    RFI.Kind = _Enum;                                                          \
+    RFI.Name = _Name;                                                          \
+    RFI.IsVarArg = _IsVarArg;                                                  \
+    RFI.ReturnType = _ReturnType;                                              \
+    RFI.ArgumentTypes = SmallVector<Type *, 8>({__VA_ARGS__});                 \
+    RFI.Declaration = M.getFunction(_Name);                                    \
+    unsigned NumUses = CollectUses(RFI);                                       \
+    (void)NumUses;                                                             \
+    LLVM_DEBUG({                                                               \
+      dbgs() << TAG << RFI.Name << (RFI.Declaration ? "" : " not")             \
+             << " found\n";                                                    \
+      if (RFI.Declaration)                                                     \
+        dbgs() << TAG << "-> got " << NumUses << " uses in "                   \
+               << RFI.UsesMap.size() << " different functions.\n";             \
+    });                                                                        \
+  }
+#include "llvm/Frontend/OpenMP/OMPKinds.def"
+
+    // TODO: We should validate the declaration agains the types we expect.
+    // TODO: We should attach the attributes defined in OMPKinds.def.
+  }
+
+  /// The underyling module.
+  Module &M;
+
+  /// The SCC we are operating on.
+  SmallPtrSetImpl<Function *> &SCC;
+
+  /// The slice of the module we are allowed to look at.
+  SmallPtrSetImpl<Function *> &ModuleSlice;
+
+  /// Callback to update the call graph, the first argument is a removed call,
+  /// the second an optional replacement call.
+  CallGraphUpdater &CGUpdater;
+
+  /// Map from runtime function kind to the runtime function description.
+  EnumeratedArray<RuntimeFunctionInfo, RuntimeFunction,
+                  RuntimeFunction::OMPRTL___last>
+      RFIs;
+};
+} // namespace
+
+PreservedAnalyses OpenMPOptPass::run(LazyCallGraph::SCC &C,
+                                     CGSCCAnalysisManager &AM,
+                                     LazyCallGraph &CG, CGSCCUpdateResult &UR) {
+  if (!containsOpenMP(*C.begin()->getFunction().getParent(), OMPInModule))
+    return PreservedAnalyses::all();
+
+  if (DisableOpenMPOptimizations)
+    return PreservedAnalyses::all();
+
+  SmallPtrSet<Function *, 16> SCC;
+  for (LazyCallGraph::Node &N : C)
+    SCC.insert(&N.getFunction());
+
+  if (SCC.empty())
+    return PreservedAnalyses::all();
+
+  CallGraphUpdater CGUpdater;
+  CGUpdater.initialize(CG, C, AM, UR);
+  // TODO: Compute the module slice we are allowed to look at.
+  OpenMPOpt OMPOpt(SCC, SCC, CGUpdater);
+  bool Changed = OMPOpt.run();
+  (void)Changed;
+  return PreservedAnalyses::all();
+}
+
+namespace {
+
+struct OpenMPOptLegacyPass : public CallGraphSCCPass {
+  CallGraphUpdater CGUpdater;
+  OpenMPInModule OMPInModule;
+  static char ID;
+
+  OpenMPOptLegacyPass() : CallGraphSCCPass(ID) {
+    initializeOpenMPOptLegacyPassPass(*PassRegistry::getPassRegistry());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    CallGraphSCCPass::getAnalysisUsage(AU);
+  }
+
+  bool doInitialization(CallGraph &CG) override {
+    // Disable the pass if there is no OpenMP (runtime call) in the module.
+    containsOpenMP(CG.getModule(), OMPInModule);
+    return false;
+  }
+
+  bool runOnSCC(CallGraphSCC &CGSCC) override {
+    if (!containsOpenMP(CGSCC.getCallGraph().getModule(), OMPInModule))
+      return false;
+    if (DisableOpenMPOptimizations || skipSCC(CGSCC))
+      return false;
+
+    SmallPtrSet<Function *, 16> SCC;
+    for (CallGraphNode *CGN : CGSCC)
+      if (Function *Fn = CGN->getFunction())
+        if (!Fn->isDeclaration())
+          SCC.insert(Fn);
+
+    if (SCC.empty())
+      return false;
+
+    CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
+    CGUpdater.initialize(CG, CGSCC);
+
+    // TODO: Compute the module slice we are allowed to look at.
+    OpenMPOpt OMPOpt(SCC, SCC, CGUpdater);
+    return OMPOpt.run();
+  }
+
+  bool doFinalization(CallGraph &CG) override { return CGUpdater.finalize(); }
+};
+
+} // end anonymous namespace
+
+bool llvm::omp::containsOpenMP(Module &M, OpenMPInModule &OMPInModule) {
+  if (OMPInModule.isKnown())
+    return OMPInModule;
+
+#define OMP_RTL(_Enum, _Name, ...)                                             \
+  if (M.getFunction(_Name))                                                    \
+    return OMPInModule = true;
+#include "llvm/Frontend/OpenMP/OMPKinds.def"
+  return OMPInModule = false;
+}
+
+char OpenMPOptLegacyPass::ID = 0;
+
+INITIALIZE_PASS_BEGIN(OpenMPOptLegacyPass, "openmpopt",
+                      "OpenMP specific optimizations", false, false)
+INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)
+INITIALIZE_PASS_END(OpenMPOptLegacyPass, "openmpopt",
+                    "OpenMP specific optimizations", false, false)
+
+Pass *llvm::createOpenMPOptLegacyPass() { return new OpenMPOptLegacyPass(); }

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::populateModulePassManager(
   MPM.add(createPruneEHPass()); // Remove dead EH info
   bool RunInliner = false;
   if (Inliner) {
     MPM.add(Inliner);
     Inliner = nullptr;
     RunInliner = true;
   }
 
+  // Try to perform OpenMP specific optimizations. This is a (quick!) no-op if
+  // there are no OpenMP runtime calls present in the module.
+  if (OptLevel > 1)
+    MPM.add(createOpenMPOptLegacyPass());
+
   MPM.add(createPostOrderFunctionAttrsLegacyPass());
   if (OptLevel > 2)
     MPM.add(createArgumentPromotionPass()); // Scalarize uninlined fn args
 
   addExtensionsToPM(EP_CGSCCOptimizerLate, MPM);
   addFunctionSimplificationPasses(MPM);
 
   // FIXME: This is a HACK! The inliner pass above implicitly creates a CGSCC
if (RunInliner) {
     Inliner = nullptr;
   }
 
   PM.add(createPruneEHPass());   // Remove dead EH info.
 
   // CSFDO instrumentation and use pass.
   addPGOInstrPasses(PM, /* IsCS */ true);
 
+  // Try to perform OpenMP specific optimizations. This is a (quick!) no-op if
+  // there are no OpenMP runtime calls present in the module.
+  if (OptLevel > 1)
+    PM.add(createOpenMPOptLegacyPass());
+
   // Optimize globals again if we ran the inliner.
   if (RunInliner)
     PM.add(createGlobalOptimizerPass());
   PM.add(createGlobalDCEPass()); // Remove dead functions.
 
   // If we didn't decide to inline a function, check to see if we can
   // transform it to pass arguments by value instead of by reference.
   PM.add(createArgumentPromotionPass());

llvm/test/Other/new-pm-defaults.ll

 ; CHECK-O-NEXT: Running analysis: LazyCallGraphAnalysis
 ; CHECK-O-NEXT: Running analysis: FunctionAnalysisManagerCGSCCProxy
 ; CHECK-O-NEXT: Running analysis: PassInstrumentationAnalysis
 ; CHECK-O-NEXT: Running analysis: OuterAnalysisManagerProxy<{{.*}}LazyCallGraph::SCC{{.*}}>
 ; CHECK-O-NEXT: Starting CGSCC pass manager run.
 ; CHECK-O-NEXT: Running pass: InlinerPass
 ; CHECK-O-NEXT: Running pass: PostOrderFunctionAttrsPass
 ; CHECK-O3-NEXT: Running pass: ArgumentPromotionPass
+; CHECK-O-NEXT: Running pass: OpenMPOptPass on (foo)
 ; CHECK-O-NEXT: Running pass: CGSCCToFunctionPassAdaptor<{{.*}}PassManager{{.*}}>
 ; CHECK-O-NEXT: Starting llvm::Function pass manager run.
 ; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running pass: EarlyCSEPass
 ; CHECK-O-NEXT: Running analysis: MemorySSAAnalysis
 ; CHECK-O23SZ-NEXT: Running pass: SpeculativeExecutionPass
 ; CHECK-O23SZ-NEXT: Running pass: JumpThreadingPass
 ; CHECK-O23SZ-NEXT: Running analysis: LazyValueAnalysis

llvm/test/Other/new-pm-thinlto-defaults.ll

 ; CHECK-O-NEXT: Running analysis: LazyCallGraphAnalysis
 ; CHECK-O-NEXT: Running analysis: FunctionAnalysisManagerCGSCCProxy
 ; CHECK-O-NEXT: Running analysis: PassInstrumentationAnalysis
 ; CHECK-O-NEXT: Running analysis: OuterAnalysisManagerProxy<{{.*}}LazyCallGraph::SCC{{.*}}>
 ; CHECK-O-NEXT: Starting CGSCC pass manager run.
 ; CHECK-O-NEXT: Running pass: InlinerPass
 ; CHECK-O-NEXT: Running pass: PostOrderFunctionAttrsPass
 ; CHECK-O3-NEXT: Running pass: ArgumentPromotionPass
+; CHECK-O-NEXT: Running pass: OpenMPOptPass on (foo)
 ; CHECK-O-NEXT: Running pass: CGSCCToFunctionPassAdaptor<{{.*}}PassManager{{.*}}>
 ; CHECK-O-NEXT: Starting llvm::Function pass manager run.
 ; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running pass: EarlyCSEPass
 ; CHECK-O-NEXT: Running analysis: MemorySSAAnalysis
 ; CHECK-O23SZ-NEXT: Running pass: SpeculativeExecutionPass
 ; CHECK-O23SZ-NEXT: Running pass: JumpThreadingPass
 ; CHECK-O23SZ-NEXT: Running analysis: LazyValueAnalysis

llvm/test/Other/opt-O2-pipeline.ll

 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Combine redundant instructions
 ; CHECK-NEXT:       Simplify the CFG
 ; CHECK-NEXT:     CallGraph Construction
 ; CHECK-NEXT:     Globals Alias Analysis
 ; CHECK-NEXT:     Call Graph SCC Pass Manager
 ; CHECK-NEXT:       Remove unused exception handling info
 ; CHECK-NEXT:       Function Integration/Inlining
+; CHECK-NEXT:       OpenMP specific optimizations
 ; CHECK-NEXT:       Deduce function attributes
 ; CHECK-NEXT:       FunctionPass Manager
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         SROA
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Early CSE w/ MemorySSA

llvm/test/Other/opt-O3-pipeline.ll

 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Combine redundant instructions
 ; CHECK-NEXT:       Simplify the CFG
 ; CHECK-NEXT:     CallGraph Construction
 ; CHECK-NEXT:     Globals Alias Analysis
 ; CHECK-NEXT:     Call Graph SCC Pass Manager
 ; CHECK-NEXT:       Remove unused exception handling info
 ; CHECK-NEXT:       Function Integration/Inlining
+; CHECK-NEXT:       OpenMP specific optimizations
 ; CHECK-NEXT:       Deduce function attributes
 ; CHECK-NEXT:       Promote 'by reference' arguments to scalars
 ; CHECK-NEXT:       FunctionPass Manager
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         SROA
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory SSA

llvm/test/Other/opt-Os-pipeline.ll

 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Combine redundant instructions
 ; CHECK-NEXT:       Simplify the CFG
 ; CHECK-NEXT:     CallGraph Construction
 ; CHECK-NEXT:     Globals Alias Analysis
 ; CHECK-NEXT:     Call Graph SCC Pass Manager
 ; CHECK-NEXT:       Remove unused exception handling info
 ; CHECK-NEXT:       Function Integration/Inlining
+; CHECK-NEXT:       OpenMP specific optimizations
 ; CHECK-NEXT:       Deduce function attributes
 ; CHECK-NEXT:       FunctionPass Manager
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         SROA
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Early CSE w/ MemorySSA

llvm/test/Other/pass-pipelines.ll

 ; PGOUSE:      Function Integration/Inlining
 ; PGOUSE: PGOInstrumentationUsePass
 ; PGOUSE: PGOIndirectCallPromotion
 ; PGOUSE: CallGraph Construction
 ; CHECK-O2-NEXT: Globals Alias Analysis
 ; CHECK-O2-NEXT: Call Graph SCC Pass Manager
 ; CHECK-O2-NEXT: Remove unused exception handling info
 ; CHECK-O2-NEXT: Function Integration/Inlining
+; CHECK-O2-NEXT: OpenMP specific optimizations
 ; CHECK-O2-NEXT: Deduce function attributes
 ; Next up is the main function pass pipeline. It shouldn't be split up and
 ; should contain the main loop pass pipeline as well.
 ; CHECK-O2-NEXT: FunctionPass Manager
 ; CHECK-O2-NOT: Manager
 ; CHECK-O2: Loop Pass Manager
 ; CHECK-O2-NOT: Manager
 ; FIXME: We shouldn't be pulling out to simplify-cfg and instcombine and

llvm/test/Transforms/OpenMP/gtid.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --function-signature
+; RUN: opt -openmpopt -S < %s | FileCheck %s
+; RUN: opt -passes=openmpopt -S < %s | FileCheck %s
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+
+%struct.ident_t = type { i32, i32, i32, i32, i8* }
+
+@0 = private unnamed_addr global %struct.ident_t { i32 0, i32 34, i32 0, i32 0, i8* getelementptr inbounds ([23 x i8], [23 x i8]* @.str, i32 0, i32 0) }, align 8
+@.str = private unnamed_addr constant [23 x i8] c";unknown;unknown;0;0;;\00", align 1
+
+declare i32 @__kmpc_global_thread_num(%struct.ident_t*)
+declare void @useI32(i32)
+
+define void @external(i1 %c) {
+; CHECK-LABEL: define {{[^@]+}}@external
+; CHECK-SAME: (i1 [[C:%.*]])
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[C2:%.*]] = tail call i32 @__kmpc_global_thread_num(%struct.ident_t* nonnull @0)
+; CHECK-NEXT:    br i1 [[C]], label [[T:%.*]], label [[E:%.*]]
+; CHECK:       t:
+; CHECK-NEXT:    call void @internal(i32 [[C2]], i32 [[C2]])
+; CHECK-NEXT:    call void @useI32(i32 [[C2]])
+; CHECK-NEXT:    br label [[M:%.*]]
+; CHECK:       e:
+; CHECK-NEXT:    call void @internal(i32 [[C2]], i32 [[C2]])
+; CHECK-NEXT:    call void @useI32(i32 [[C2]])
+; CHECK-NEXT:    br label [[M]]
+; CHECK:       m:
+; CHECK-NEXT:    call void @internal(i32 0, i32 [[C2]])
+; CHECK-NEXT:    call void @useI32(i32 [[C2]])
+; CHECK-NEXT:    ret void
+;
+entry:
+  br i1 %c, label %t, label %e
+t:
+  %c0 = tail call i32 @__kmpc_global_thread_num(%struct.ident_t* nonnull @0)
+  call void @internal(i32 %c0, i32 %c0)
+  call void @useI32(i32 %c0)
+  br label %m
+e:
+  %c1 = tail call i32 @__kmpc_global_thread_num(%struct.ident_t* nonnull @0)
+  call void @internal(i32 %c1, i32 %c1)
+  call void @useI32(i32 %c1)
+  br label %m
+m:
+  %c2 = tail call i32 @__kmpc_global_thread_num(%struct.ident_t* nonnull @0)
+  call void @internal(i32 0, i32 %c2)
+  call void @useI32(i32 %c2)
+  ret void
+}
+
+define internal void @internal(i32 %not_gtid, i32 %gtid) {
+; CHECK-LABEL: define {{[^@]+}}@internal
+; CHECK-SAME: (i32 [[NOT_GTID:%.*]], i32 [[GTID:%.*]])
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[GTID]], [[GTID]]
+; CHECK-NEXT:    br i1 [[C]], label [[T:%.*]], label [[E:%.*]]
+; CHECK:       t:
+; CHECK-NEXT:    call void @useI32(i32 [[GTID]])
+; CHECK-NEXT:    call void @external(i1 [[C]])
+; CHECK-NEXT:    br label [[M:%.*]]
+; CHECK:       e:
+; CHECK-NEXT:    call void @useI32(i32 [[GTID]])
+; CHECK-NEXT:    br label [[M]]
+; CHECK:       m:
+; CHECK-NEXT:    call void @useI32(i32 [[GTID]])
+; CHECK-NEXT:    ret void
+;
+entry:
+  %cc = tail call i32 @__kmpc_global_thread_num(%struct.ident_t* nonnull @0)
+  %c = icmp eq i32 %cc, %gtid
+  br i1 %c, label %t, label %e
+t:
+  %c0 = tail call i32 @__kmpc_global_thread_num(%struct.ident_t* nonnull @0)
+  call void @useI32(i32 %c0)
+  call void @external(i1 %c)
+  br label %m
+e:
+  %c1 = tail call i32 @__kmpc_global_thread_num(%struct.ident_t* nonnull @0)
+  call void @useI32(i32 %c1)
+  br label %m
+m:
+  %c2 = tail call i32 @__kmpc_global_thread_num(%struct.ident_t* nonnull @0)
+  call void @useI32(i32 %c2)
+  ret void
+}