1//===-- IPO/OpenMPOpt.cpp - Collection of OpenMP specific optimizations ---===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// OpenMP specific optimizations:
10//
11// - Deduplication of runtime calls, e.g., omp_get_thread_num.
12// - Replacing globalized device memory with stack memory.
13// - Replacing globalized device memory with shared memory.
14// - Parallel region merging.
15// - Transforming generic-mode device kernels to SPMD mode.
16// - Specializing the state machine for generic-mode device kernels.
17//
18//===----------------------------------------------------------------------===//
19
20#include "llvm/Transforms/IPO/OpenMPOpt.h"
21
22#include "llvm/ADT/DenseSet.h"
23#include "llvm/ADT/EnumeratedArray.h"
24#include "llvm/ADT/PostOrderIterator.h"
25#include "llvm/ADT/SetVector.h"
26#include "llvm/ADT/SmallPtrSet.h"
27#include "llvm/ADT/SmallVector.h"
28#include "llvm/ADT/Statistic.h"
29#include "llvm/ADT/StringExtras.h"
30#include "llvm/ADT/StringRef.h"
31#include "llvm/Analysis/CallGraph.h"
32#include "llvm/Analysis/MemoryBuiltins.h"
33#include "llvm/Analysis/MemoryLocation.h"
34#include "llvm/Analysis/OptimizationRemarkEmitter.h"
35#include "llvm/Analysis/ValueTracking.h"
36#include "llvm/Frontend/OpenMP/OMPConstants.h"
37#include "llvm/Frontend/OpenMP/OMPDeviceConstants.h"
38#include "llvm/Frontend/OpenMP/OMPIRBuilder.h"
39#include "llvm/IR/Assumptions.h"
40#include "llvm/IR/BasicBlock.h"
41#include "llvm/IR/Constants.h"
42#include "llvm/IR/DiagnosticInfo.h"
43#include "llvm/IR/Dominators.h"
44#include "llvm/IR/Function.h"
45#include "llvm/IR/GlobalValue.h"
46#include "llvm/IR/GlobalVariable.h"
47#include "llvm/IR/InstrTypes.h"
48#include "llvm/IR/Instruction.h"
49#include "llvm/IR/Instructions.h"
50#include "llvm/IR/IntrinsicInst.h"
51#include "llvm/IR/IntrinsicsAMDGPU.h"
52#include "llvm/IR/IntrinsicsNVPTX.h"
53#include "llvm/IR/LLVMContext.h"
54#include "llvm/IR/MDBuilder.h"
55#include "llvm/IR/ProfDataUtils.h"
56#include "llvm/IR/ProfileSummary.h"
57#include "llvm/Support/Casting.h"
58#include "llvm/Support/CommandLine.h"
59#include "llvm/Support/Debug.h"
60#include "llvm/TargetParser/AtomicScope.h"
61#include "llvm/TargetParser/Triple.h"
62#include "llvm/Transforms/IPO/Attributor.h"
63#include "llvm/Transforms/Utils/BasicBlockUtils.h"
64#include "llvm/Transforms/Utils/CallGraphUpdater.h"
65
66#include <algorithm>
67#include <memory>
68#include <optional>
69#include <string>
70
71using namespace llvm;
72using namespace omp;
73
74#define DEBUG_TYPE "openmp-opt"
75
76static cl::opt<bool> DisableOpenMPOptimizations(
77 "openmp-opt-disable", cl::desc("Disable OpenMP specific optimizations."),
78 cl::Hidden, cl::init(Val: false));
79
80static cl::opt<bool> EnableParallelRegionMerging(
81 "openmp-opt-enable-merging",
82 cl::desc("Enable the OpenMP region merging optimization."), cl::Hidden,
83 cl::init(Val: false));
84
85static cl::opt<bool>
86 DisableInternalization("openmp-opt-disable-internalization",
87 cl::desc("Disable function internalization."),
88 cl::Hidden, cl::init(Val: false));
89
90static cl::opt<bool> DeduceICVValues("openmp-deduce-icv-values",
91 cl::init(Val: false), cl::Hidden);
92static cl::opt<bool> PrintICVValues("openmp-print-icv-values", cl::init(Val: false),
93 cl::Hidden);
94static cl::opt<bool> PrintOpenMPKernels("openmp-print-gpu-kernels",
95 cl::init(Val: false), cl::Hidden);
96
97static cl::opt<bool> HideMemoryTransferLatency(
98 "openmp-hide-memory-transfer-latency",
99 cl::desc("[WIP] Tries to hide the latency of host to device memory"
100 " transfers"),
101 cl::Hidden, cl::init(Val: false));
102
103static cl::opt<bool> DisableOpenMPOptDeglobalization(
104 "openmp-opt-disable-deglobalization",
105 cl::desc("Disable OpenMP optimizations involving deglobalization."),
106 cl::Hidden, cl::init(Val: false));
107
108static cl::opt<bool> DisableOpenMPOptSPMDization(
109 "openmp-opt-disable-spmdization",
110 cl::desc("Disable OpenMP optimizations involving SPMD-ization."),
111 cl::Hidden, cl::init(Val: false));
112
113static cl::opt<bool> DisableOpenMPOptFolding(
114 "openmp-opt-disable-folding",
115 cl::desc("Disable OpenMP optimizations involving folding."), cl::Hidden,
116 cl::init(Val: false));
117
118static cl::opt<bool> DisableOpenMPOptStateMachineRewrite(
119 "openmp-opt-disable-state-machine-rewrite",
120 cl::desc("Disable OpenMP optimizations that replace the state machine."),
121 cl::Hidden, cl::init(Val: false));
122
123static cl::opt<bool> DisableOpenMPOptBarrierElimination(
124 "openmp-opt-disable-barrier-elimination",
125 cl::desc("Disable OpenMP optimizations that eliminate barriers."),
126 cl::Hidden, cl::init(Val: false));
127
128static cl::opt<bool> PrintModuleAfterOptimizations(
129 "openmp-opt-print-module-after",
130 cl::desc("Print the current module after OpenMP optimizations."),
131 cl::Hidden, cl::init(Val: false));
132
133static cl::opt<bool> PrintModuleBeforeOptimizations(
134 "openmp-opt-print-module-before",
135 cl::desc("Print the current module before OpenMP optimizations."),
136 cl::Hidden, cl::init(Val: false));
137
138static cl::opt<bool> AlwaysInlineDeviceFunctions(
139 "openmp-opt-inline-device",
140 cl::desc("Inline all applicable functions on the device."), cl::Hidden,
141 cl::init(Val: false));
142
143static cl::opt<bool>
144 EnableVerboseRemarks("openmp-opt-verbose-remarks",
145 cl::desc("Enables more verbose remarks."), cl::Hidden,
146 cl::init(Val: false));
147
148static cl::opt<unsigned>
149 SetFixpointIterations("openmp-opt-max-iterations", cl::Hidden,
150 cl::desc("Maximal number of attributor iterations."),
151 cl::init(Val: 256));
152
153static cl::opt<unsigned>
154 SharedMemoryLimit("openmp-opt-shared-limit", cl::Hidden,
155 cl::desc("Maximum amount of shared memory to use."),
156 cl::init(Val: std::numeric_limits<unsigned>::max()));
157
158static cl::opt<unsigned> MaxCalleesForSpecialization(
159 "openmp-opt-max-callees-for-specialization", cl::Hidden,
160 cl::desc("Number of possible callees above which an indirect call site is "
161 "left alone rather than specialized into an if-cascade."),
162 cl::init(Val: 3));
163
164STATISTIC(NumOpenMPRuntimeCallsDeduplicated,
165 "Number of OpenMP runtime calls deduplicated");
166STATISTIC(NumOpenMPParallelRegionsDeleted,
167 "Number of OpenMP parallel regions deleted");
168STATISTIC(NumOpenMPRuntimeFunctionsIdentified,
169 "Number of OpenMP runtime functions identified");
170STATISTIC(NumOpenMPRuntimeFunctionUsesIdentified,
171 "Number of OpenMP runtime function uses identified");
172STATISTIC(NumOpenMPTargetRegionKernels,
173 "Number of OpenMP target region entry points (=kernels) identified");
174STATISTIC(NumNonOpenMPTargetRegionKernels,
175 "Number of non-OpenMP target region kernels identified");
176STATISTIC(NumOpenMPTargetRegionKernelsSPMD,
177 "Number of OpenMP target region entry points (=kernels) executed in "
178 "SPMD-mode instead of generic-mode");
179STATISTIC(NumOpenMPTargetRegionKernelsWithoutStateMachine,
180 "Number of OpenMP target region entry points (=kernels) executed in "
181 "generic-mode without a state machines");
182STATISTIC(NumOpenMPTargetRegionKernelsCustomStateMachineWithFallback,
183 "Number of OpenMP target region entry points (=kernels) executed in "
184 "generic-mode with customized state machines with fallback");
185STATISTIC(NumOpenMPTargetRegionKernelsCustomStateMachineWithoutFallback,
186 "Number of OpenMP target region entry points (=kernels) executed in "
187 "generic-mode with customized state machines without fallback");
188STATISTIC(
189 NumOpenMPParallelRegionsReplacedInGPUStateMachine,
190 "Number of OpenMP parallel regions replaced with ID in GPU state machines");
191STATISTIC(NumOpenMPParallelRegionsMerged,
192 "Number of OpenMP parallel regions merged");
193STATISTIC(NumBytesMovedToSharedMemory,
194 "Amount of memory pushed to shared memory");
195STATISTIC(NumBarriersEliminated, "Number of redundant barriers eliminated");
196
197#if !defined(NDEBUG)
198static constexpr auto TAG = "[" DEBUG_TYPE "]";
199#endif
200
201namespace KernelInfo {
202
203// struct ConfigurationEnvironmentTy {
204// uint8_t UseGenericStateMachine;
205// uint8_t MayUseNestedParallelism;
206// llvm::omp::OMPTgtExecModeFlags ExecMode;
207// int32_t MinThreads;
208// int32_t MaxThreads;
209// int32_t MinTeams;
210// int32_t MaxTeams;
211// };
212
213// struct DynamicEnvironmentTy {
214// uint16_t DebugIndentionLevel;
215// };
216
217// struct KernelEnvironmentTy {
218// ConfigurationEnvironmentTy Configuration;
219// IdentTy *Ident;
220// DynamicEnvironmentTy *DynamicEnv;
221// };
222
223#define KERNEL_ENVIRONMENT_IDX(MEMBER, IDX) \
224 constexpr unsigned MEMBER##Idx = IDX;
225
226KERNEL_ENVIRONMENT_IDX(Configuration, 0)
227KERNEL_ENVIRONMENT_IDX(Ident, 1)
228
229#undef KERNEL_ENVIRONMENT_IDX
230
231#define KERNEL_ENVIRONMENT_CONFIGURATION_IDX(MEMBER, IDX) \
232 constexpr unsigned MEMBER##Idx = IDX;
233
234KERNEL_ENVIRONMENT_CONFIGURATION_IDX(UseGenericStateMachine, 0)
235KERNEL_ENVIRONMENT_CONFIGURATION_IDX(MayUseNestedParallelism, 1)
236KERNEL_ENVIRONMENT_CONFIGURATION_IDX(ExecMode, 2)
237KERNEL_ENVIRONMENT_CONFIGURATION_IDX(MinThreads, 3)
238KERNEL_ENVIRONMENT_CONFIGURATION_IDX(MaxThreads, 4)
239KERNEL_ENVIRONMENT_CONFIGURATION_IDX(MinTeams, 5)
240KERNEL_ENVIRONMENT_CONFIGURATION_IDX(MaxTeams, 6)
241
242#undef KERNEL_ENVIRONMENT_CONFIGURATION_IDX
243
244#define KERNEL_ENVIRONMENT_GETTER(MEMBER, RETURNTYPE) \
245 RETURNTYPE *get##MEMBER##FromKernelEnvironment(ConstantStruct *KernelEnvC) { \
246 return cast<RETURNTYPE>(KernelEnvC->getAggregateElement(MEMBER##Idx)); \
247 }
248
249KERNEL_ENVIRONMENT_GETTER(Ident, Constant)
250KERNEL_ENVIRONMENT_GETTER(Configuration, ConstantStruct)
251
252#undef KERNEL_ENVIRONMENT_GETTER
253
254#define KERNEL_ENVIRONMENT_CONFIGURATION_GETTER(MEMBER) \
255 ConstantInt *get##MEMBER##FromKernelEnvironment( \
256 ConstantStruct *KernelEnvC) { \
257 ConstantStruct *ConfigC = \
258 getConfigurationFromKernelEnvironment(KernelEnvC); \
259 return dyn_cast<ConstantInt>(ConfigC->getAggregateElement(MEMBER##Idx)); \
260 }
261
262KERNEL_ENVIRONMENT_CONFIGURATION_GETTER(UseGenericStateMachine)
263KERNEL_ENVIRONMENT_CONFIGURATION_GETTER(MayUseNestedParallelism)
264KERNEL_ENVIRONMENT_CONFIGURATION_GETTER(ExecMode)
265KERNEL_ENVIRONMENT_CONFIGURATION_GETTER(MinThreads)
266KERNEL_ENVIRONMENT_CONFIGURATION_GETTER(MaxThreads)
267KERNEL_ENVIRONMENT_CONFIGURATION_GETTER(MinTeams)
268KERNEL_ENVIRONMENT_CONFIGURATION_GETTER(MaxTeams)
269
270#undef KERNEL_ENVIRONMENT_CONFIGURATION_GETTER
271
272GlobalVariable *
273getKernelEnvironementGVFromKernelInitCB(CallBase *KernelInitCB) {
274 constexpr int InitKernelEnvironmentArgNo = 0;
275 return cast<GlobalVariable>(
276 Val: KernelInitCB->getArgOperand(i: InitKernelEnvironmentArgNo)
277 ->stripPointerCasts());
278}
279
280ConstantStruct *getKernelEnvironementFromKernelInitCB(CallBase *KernelInitCB) {
281 GlobalVariable *KernelEnvGV =
282 getKernelEnvironementGVFromKernelInitCB(KernelInitCB);
283 return cast<ConstantStruct>(Val: KernelEnvGV->getInitializer());
284}
285} // namespace KernelInfo
286
287namespace {
288
289struct AAHeapToShared;
290
291struct AAICVTracker;
292
293/// OpenMP specific information. For now, stores RFIs and ICVs also needed for
294/// Attributor runs.
295struct OMPInformationCache : public InformationCache {
296 OMPInformationCache(Module &M, AnalysisGetter &AG,
297 BumpPtrAllocator &Allocator, SetVector<Function *> *CGSCC,
298 bool OpenMPPostLink)
299 : InformationCache(M, AG, Allocator, CGSCC), OMPBuilder(M),
300 OpenMPPostLink(OpenMPPostLink) {
301
302 OMPBuilder.Config.IsTargetDevice = isOpenMPDevice(M&: OMPBuilder.M);
303 const Triple T(OMPBuilder.M.getTargetTriple());
304 switch (T.getArch()) {
305 case llvm::Triple::nvptx:
306 case llvm::Triple::nvptx64:
307 case llvm::Triple::amdgpu:
308 assert(OMPBuilder.Config.IsTargetDevice &&
309 "OpenMP AMDGPU/NVPTX is only prepared to deal with device code.");
310 OMPBuilder.Config.IsGPU = true;
311 break;
312 default:
313 OMPBuilder.Config.IsGPU = false;
314 break;
315 }
316 OMPBuilder.initialize();
317 initializeRuntimeFunctions(M);
318 initializeInternalControlVars();
319 }
320
321 /// Generic information that describes an internal control variable.
322 struct InternalControlVarInfo {
323 /// The kind, as described by InternalControlVar enum.
324 InternalControlVar Kind;
325
326 /// The name of the ICV.
327 StringRef Name;
328
329 /// Environment variable associated with this ICV.
330 StringRef EnvVarName;
331
332 /// Initial value kind.
333 ICVInitValue InitKind;
334
335 /// Initial value.
336 ConstantInt *InitValue;
337
338 /// Setter RTL function associated with this ICV.
339 RuntimeFunction Setter;
340
341 /// Getter RTL function associated with this ICV.
342 RuntimeFunction Getter;
343
344 /// RTL Function corresponding to the override clause of this ICV
345 RuntimeFunction Clause;
346 };
347
348 /// Generic information that describes a runtime function
349 struct RuntimeFunctionInfo {
350
351 /// The kind, as described by the RuntimeFunction enum.
352 RuntimeFunction Kind;
353
354 /// The name of the function.
355 StringRef Name;
356
357 /// Flag to indicate a variadic function.
358 bool IsVarArg;
359
360 /// The return type of the function.
361 Type *ReturnType;
362
363 /// The argument types of the function.
364 SmallVector<Type *, 8> ArgumentTypes;
365
366 /// The declaration if available.
367 Function *Declaration = nullptr;
368
369 /// Uses of this runtime function per function containing the use.
370 using UseVector = SmallVector<Use *, 16>;
371
372 /// Clear UsesMap for runtime function.
373 void clearUsesMap() { UsesMap.clear(); }
374
375 /// Boolean conversion that is true if the runtime function was found.
376 operator bool() const { return Declaration; }
377
378 /// Return the vector of uses in function \p F.
379 UseVector &getOrCreateUseVector(Function *F) {
380 std::shared_ptr<UseVector> &UV = UsesMap[F];
381 if (!UV)
382 UV = std::make_shared<UseVector>();
383 return *UV;
384 }
385
386 /// Return the vector of uses in function \p F or `nullptr` if there are
387 /// none.
388 const UseVector *getUseVector(Function &F) const {
389 auto I = UsesMap.find(Val: &F);
390 if (I != UsesMap.end())
391 return I->second.get();
392 return nullptr;
393 }
394
395 /// Return how many functions contain uses of this runtime function.
396 size_t getNumFunctionsWithUses() const { return UsesMap.size(); }
397
398 /// Return the number of arguments (or the minimal number for variadic
399 /// functions).
400 size_t getNumArgs() const { return ArgumentTypes.size(); }
401
402 /// Run the callback \p CB on each use and forget the use if the result is
403 /// true. The callback will be fed the function in which the use was
404 /// encountered as second argument.
405 void foreachUse(SmallVectorImpl<Function *> &SCC,
406 function_ref<bool(Use &, Function &)> CB) {
407 for (Function *F : SCC)
408 foreachUse(CB, F);
409 }
410
411 /// Run the callback \p CB on each use within the function \p F and forget
412 /// the use if the result is true.
413 void foreachUse(function_ref<bool(Use &, Function &)> CB, Function *F) {
414 SmallVector<unsigned, 8> ToBeDeleted;
415 ToBeDeleted.clear();
416
417 unsigned Idx = 0;
418 UseVector &UV = getOrCreateUseVector(F);
419
420 for (Use *U : UV) {
421 if (CB(*U, *F))
422 ToBeDeleted.push_back(Elt: Idx);
423 ++Idx;
424 }
425
426 // Remove the to-be-deleted indices in reverse order as prior
427 // modifications will not modify the smaller indices.
428 while (!ToBeDeleted.empty()) {
429 unsigned Idx = ToBeDeleted.pop_back_val();
430 UV[Idx] = UV.back();
431 UV.pop_back();
432 }
433 }
434
435 private:
436 /// Map from functions to all uses of this runtime function contained in
437 /// them.
438 DenseMap<Function *, std::shared_ptr<UseVector>> UsesMap;
439
440 public:
441 /// Iterators for the uses of this runtime function.
442 decltype(UsesMap)::iterator begin() { return UsesMap.begin(); }
443 decltype(UsesMap)::iterator end() { return UsesMap.end(); }
444 };
445
446 /// An OpenMP-IR-Builder instance
447 OpenMPIRBuilder OMPBuilder;
448
449 /// Map from runtime function kind to the runtime function description.
450 EnumeratedArray<RuntimeFunctionInfo, RuntimeFunction,
451 RuntimeFunction::OMPRTL___last>
452 RFIs;
453
454 /// Map from function declarations/definitions to their runtime enum type.
455 DenseMap<Function *, RuntimeFunction> RuntimeFunctionIDMap;
456
457 /// Map from ICV kind to the ICV description.
458 EnumeratedArray<InternalControlVarInfo, InternalControlVar,
459 InternalControlVar::ICV___last>
460 ICVs;
461
462 /// Helper to initialize all internal control variable information for those
463 /// defined in OMPKinds.def.
464 void initializeInternalControlVars() {
465#define ICV_RT_SET(_Name, RTL) \
466 { \
467 auto &ICV = ICVs[_Name]; \
468 ICV.Setter = RTL; \
469 }
470#define ICV_RT_GET(Name, RTL) \
471 { \
472 auto &ICV = ICVs[Name]; \
473 ICV.Getter = RTL; \
474 }
475#define ICV_DATA_ENV(Enum, _Name, _EnvVarName, Init) \
476 { \
477 auto &ICV = ICVs[Enum]; \
478 ICV.Name = _Name; \
479 ICV.Kind = Enum; \
480 ICV.InitKind = Init; \
481 ICV.EnvVarName = _EnvVarName; \
482 switch (ICV.InitKind) { \
483 case ICV_IMPLEMENTATION_DEFINED: \
484 ICV.InitValue = nullptr; \
485 break; \
486 case ICV_ZERO: \
487 ICV.InitValue = ConstantInt::get( \
488 Type::getInt32Ty(OMPBuilder.Int32->getContext()), 0); \
489 break; \
490 case ICV_FALSE: \
491 ICV.InitValue = ConstantInt::getFalse(OMPBuilder.Int1->getContext()); \
492 break; \
493 case ICV_LAST: \
494 break; \
495 } \
496 }
497#include "llvm/Frontend/OpenMP/OMPKinds.def"
498 }
499
500 /// Returns true if the function declaration \p F matches the runtime
501 /// function types, that is, return type \p RTFRetType, and argument types
502 /// \p RTFArgTypes.
503 static bool declMatchesRTFTypes(Function *F, Type *RTFRetType,
504 SmallVector<Type *, 8> &RTFArgTypes) {
505 // TODO: We should output information to the user (under debug output
506 // and via remarks).
507
508 if (!F)
509 return false;
510 if (F->getReturnType() != RTFRetType)
511 return false;
512 if (F->arg_size() != RTFArgTypes.size())
513 return false;
514
515 auto *RTFTyIt = RTFArgTypes.begin();
516 for (Argument &Arg : F->args()) {
517 if (Arg.getType() != *RTFTyIt)
518 return false;
519
520 ++RTFTyIt;
521 }
522
523 return true;
524 }
525
526 // Helper to collect all uses of the declaration in the UsesMap.
527 unsigned collectUses(RuntimeFunctionInfo &RFI, bool CollectStats = true) {
528 unsigned NumUses = 0;
529 if (!RFI.Declaration)
530 return NumUses;
531 OMPBuilder.addAttributes(FnID: RFI.Kind, Fn&: *RFI.Declaration);
532
533 if (CollectStats) {
534 NumOpenMPRuntimeFunctionsIdentified += 1;
535 NumOpenMPRuntimeFunctionUsesIdentified += RFI.Declaration->getNumUses();
536 }
537
538 // TODO: We directly convert uses into proper calls and unknown uses.
539 for (Use &U : RFI.Declaration->uses()) {
540 if (Instruction *UserI = dyn_cast<Instruction>(Val: U.getUser())) {
541 if (!CGSCC || CGSCC->empty() || CGSCC->contains(key: UserI->getFunction())) {
542 RFI.getOrCreateUseVector(F: UserI->getFunction()).push_back(Elt: &U);
543 ++NumUses;
544 }
545 } else {
546 RFI.getOrCreateUseVector(F: nullptr).push_back(Elt: &U);
547 ++NumUses;
548 }
549 }
550 return NumUses;
551 }
552
553 // Helper function to recollect uses of a runtime function.
554 void recollectUsesForFunction(RuntimeFunction RTF) {
555 auto &RFI = RFIs[RTF];
556 RFI.clearUsesMap();
557 collectUses(RFI, /*CollectStats*/ false);
558 }
559
560 /// Attach !callback metadata to a runtime function that takes one, so that
561 /// the Attributor sees the edge from the runtime call to the callback and
562 /// AAKernelInfo can look inside it. The runtime declares these functions
563 /// without the metadata, so OpenMPOpt supplies it from the table in
564 /// OMPKinds.def.
565 void setCallbackMetadata(Function *F, unsigned ArgNo, ArrayRef<int> Indices,
566 bool IsVarArg) {
567 if (!F || F->hasMetadata(KindID: LLVMContext::MD_callback))
568 return;
569
570 LLVMContext &Ctx = F->getContext();
571 MDBuilder MDB(Ctx);
572 F->addMetadata(KindID: LLVMContext::MD_callback,
573 MD&: *MDNode::get(Context&: Ctx, MDs: {MDB.createCallbackEncoding(CalleeArgNo: ArgNo, Arguments: Indices,
574 VarArgsArePassed: IsVarArg)}));
575 }
576
577 /// The callback a runtime function was handed, if it is one we can analyze.
578 /// Returns null when the call takes no callback, or when the callback is not
579 /// a definition this module can see, in which case its contents are unknown
580 /// and callers have to stay conservative.
581 static Function *getAnalyzableCallback(const CallBase &CB) {
582 Function *Callee = CB.getCalledFunction();
583 if (!Callee)
584 return nullptr;
585 MDNode *CallbackMD = Callee->getMetadata(KindID: LLVMContext::MD_callback);
586 if (!CallbackMD || CallbackMD->getNumOperands() == 0)
587 return nullptr;
588 // TODO: A runtime function with more than one callback would need each of
589 // them checked; none of the ones in the table have more than one.
590 auto *Encoding = dyn_cast<MDNode>(Val: CallbackMD->getOperand(I: 0));
591 if (!Encoding || Encoding->getNumOperands() == 0)
592 return nullptr;
593 auto *ArgNoMD = dyn_cast<ConstantAsMetadata>(Val: Encoding->getOperand(I: 0));
594 if (!ArgNoMD)
595 return nullptr;
596 uint64_t ArgNo =
597 cast<ConstantInt>(Val: ArgNoMD->getValue())->getLimitedValue(UINT64_MAX);
598 if (ArgNo >= CB.arg_size())
599 return nullptr;
600 auto *Callback =
601 dyn_cast<Function>(Val: CB.getArgOperand(i: ArgNo)->stripPointerCasts());
602 if (!Callback || Callback->isDeclaration())
603 return nullptr;
604 return Callback;
605 }
606
607 // Helper function to recollect uses of all runtime functions.
608 void recollectUses() {
609 for (int Idx = 0; Idx < RFIs.size(); ++Idx)
610 recollectUsesForFunction(RTF: static_cast<RuntimeFunction>(Idx));
611 }
612
613 // Helper function to inherit the calling convention of the function callee.
614 void setCallingConvention(FunctionCallee Callee, CallInst *CI) {
615 if (Function *Fn = dyn_cast<Function>(Val: Callee.getCallee()))
616 CI->setCallingConv(Fn->getCallingConv());
617 }
618
619 // Helper function to determine if it's legal to create a call to the runtime
620 // functions.
621 bool runtimeFnsAvailable(ArrayRef<RuntimeFunction> Fns) {
622 // We can always emit calls if we haven't yet linked in the runtime.
623 if (!OpenMPPostLink)
624 return true;
625
626 // Once the runtime has been already been linked in we cannot emit calls to
627 // any undefined functions.
628 for (RuntimeFunction Fn : Fns) {
629 RuntimeFunctionInfo &RFI = RFIs[Fn];
630
631 if (!RFI.Declaration || RFI.Declaration->isDeclaration())
632 return false;
633 }
634 return true;
635 }
636
637 /// Helper to initialize all runtime function information for those defined
638 /// in OpenMPKinds.def.
639 void initializeRuntimeFunctions(Module &M) {
640
641 // Helper macros for handling __VA_ARGS__ in OMP_RTL
642#define OMP_TYPE(VarName, ...) \
643 Type *VarName = OMPBuilder.VarName; \
644 (void)VarName;
645
646#define OMP_ARRAY_TYPE(VarName, ...) \
647 ArrayType *VarName##Ty = OMPBuilder.VarName##Ty; \
648 (void)VarName##Ty; \
649 PointerType *VarName##PtrTy = OMPBuilder.VarName##PtrTy; \
650 (void)VarName##PtrTy;
651
652#define OMP_FUNCTION_TYPE(VarName, ...) \
653 FunctionType *VarName = OMPBuilder.VarName; \
654 (void)VarName; \
655 PointerType *VarName##Ptr = OMPBuilder.VarName##Ptr; \
656 (void)VarName##Ptr;
657
658#define OMP_STRUCT_TYPE(VarName, ...) \
659 StructType *VarName = OMPBuilder.VarName; \
660 (void)VarName; \
661 PointerType *VarName##Ptr = OMPBuilder.VarName##Ptr; \
662 (void)VarName##Ptr;
663
664#define OMP_RTL(_Enum, _Name, _IsVarArg, _ReturnType, ...) \
665 { \
666 SmallVector<Type *, 8> ArgsTypes({__VA_ARGS__}); \
667 Function *F = M.getFunction(_Name); \
668 RTLFunctions.insert(F); \
669 if (declMatchesRTFTypes(F, OMPBuilder._ReturnType, ArgsTypes)) { \
670 RuntimeFunctionIDMap[F] = _Enum; \
671 auto &RFI = RFIs[_Enum]; \
672 RFI.Kind = _Enum; \
673 RFI.Name = _Name; \
674 RFI.IsVarArg = _IsVarArg; \
675 RFI.ReturnType = OMPBuilder._ReturnType; \
676 RFI.ArgumentTypes = std::move(ArgsTypes); \
677 RFI.Declaration = F; \
678 unsigned NumUses = collectUses(RFI); \
679 (void)NumUses; \
680 LLVM_DEBUG({ \
681 dbgs() << TAG << RFI.Name << (RFI.Declaration ? "" : " not") \
682 << " found\n"; \
683 if (RFI.Declaration) \
684 dbgs() << TAG << "-> got " << NumUses << " uses in " \
685 << RFI.getNumFunctionsWithUses() \
686 << " different functions.\n"; \
687 }); \
688 } \
689 }
690
691#define OMP_RTL_CB_INFO(_Enum, _Name, _ArgNo, _ArgIndices, _IsVarArg) \
692 setCallbackMetadata(M.getFunction(_Name), _ArgNo, _ArgIndices, _IsVarArg);
693
694#include "llvm/Frontend/OpenMP/OMPKinds.def"
695
696 // Remove the `noinline` attribute from `__kmpc`, `ompx::` and `omp_`
697 // functions, except if `optnone` is present.
698 if (isOpenMPDevice(M)) {
699 for (Function &F : M) {
700 for (StringRef Prefix : {"__kmpc", "_ZN4ompx", "omp_"})
701 if (F.hasFnAttribute(Kind: Attribute::NoInline) &&
702 F.getName().starts_with(Prefix) &&
703 !F.hasFnAttribute(Kind: Attribute::OptimizeNone))
704 F.removeFnAttr(Kind: Attribute::NoInline);
705 }
706 }
707
708 // TODO: We should attach the attributes defined in OMPKinds.def.
709 }
710
711 /// Collection of known OpenMP runtime functions..
712 DenseSet<const Function *> RTLFunctions;
713
714 /// Indicates if we have already linked in the OpenMP device library.
715 bool OpenMPPostLink = false;
716
717 /// Kernels that OpenMPOpt transformed from generic to SPMD mode. Recorded at
718 /// the transform (changeToSPMDMode) so later cleanup does not have to
719 /// re-derive the mode. Such kernels no longer run a generic-mode state
720 /// machine, so the parallel data-sharing wrapper passed to __kmpc_parallel_60
721 /// is dead in them.
722 SmallPtrSet<Function *, 8> SPMDizedKernels;
723};
724
725template <typename Ty, bool InsertInvalidates = true>
726struct BooleanStateWithSetVector : public BooleanState {
727 bool contains(const Ty &Elem) const { return Set.contains(Elem); }
728 bool insert(const Ty &Elem) {
729 if (InsertInvalidates)
730 BooleanState::indicatePessimisticFixpoint();
731 return Set.insert(Elem);
732 }
733
734 const Ty &operator[](int Idx) const { return Set[Idx]; }
735 bool operator==(const BooleanStateWithSetVector &RHS) const {
736 return BooleanState::operator==(R: RHS) && Set == RHS.Set;
737 }
738 bool operator!=(const BooleanStateWithSetVector &RHS) const {
739 return !(*this == RHS);
740 }
741
742 bool empty() const { return Set.empty(); }
743 size_t size() const { return Set.size(); }
744
745 /// "Clamp" this state with \p RHS.
746 BooleanStateWithSetVector &operator^=(const BooleanStateWithSetVector &RHS) {
747 BooleanState::operator^=(R: RHS);
748 Set.insert_range(RHS.Set);
749 return *this;
750 }
751
752private:
753 /// A set to keep track of elements.
754 SetVector<Ty> Set;
755
756public:
757 typename decltype(Set)::iterator begin() { return Set.begin(); }
758 typename decltype(Set)::iterator end() { return Set.end(); }
759 typename decltype(Set)::const_iterator begin() const { return Set.begin(); }
760 typename decltype(Set)::const_iterator end() const { return Set.end(); }
761};
762
763template <typename Ty, bool InsertInvalidates = true>
764using BooleanStateWithPtrSetVector =
765 BooleanStateWithSetVector<Ty *, InsertInvalidates>;
766
767struct KernelInfoState : AbstractState {
768 /// Flag to track if we reached a fixpoint.
769 bool IsAtFixpoint = false;
770
771 /// The parallel regions (identified by the outlined parallel functions) that
772 /// can be reached from the associated function.
773 BooleanStateWithPtrSetVector<CallBase, /* InsertInvalidates */ false>
774 ReachedKnownParallelRegions;
775
776 /// State to track what parallel region we might reach.
777 BooleanStateWithPtrSetVector<CallBase> ReachedUnknownParallelRegions;
778
779 /// State to track if we are in SPMD-mode, assumed or know, and why we decided
780 /// we cannot be. If it is assumed, then RequiresFullRuntime should also be
781 /// false.
782 BooleanStateWithPtrSetVector<Instruction, false> SPMDCompatibilityTracker;
783
784 /// The __kmpc_target_init call in this kernel, if any. If we find more than
785 /// one we abort as the kernel is malformed.
786 CallBase *KernelInitCB = nullptr;
787
788 /// The constant kernel environement as taken from and passed to
789 /// __kmpc_target_init.
790 ConstantStruct *KernelEnvC = nullptr;
791
792 /// The __kmpc_target_deinit call in this kernel, if any. If we find more than
793 /// one we abort as the kernel is malformed.
794 CallBase *KernelDeinitCB = nullptr;
795
796 /// Flag to indicate if the associated function is a kernel entry.
797 bool IsKernelEntry = false;
798
799 /// State to track what kernel entries can reach the associated function.
800 BooleanStateWithPtrSetVector<Function, false> ReachingKernelEntries;
801
802 /// State to indicate if we can track parallel level of the associated
803 /// function. We will give up tracking if we encounter unknown caller or the
804 /// caller is __kmpc_parallel_60.
805 BooleanStateWithSetVector<uint8_t> ParallelLevels;
806
807 /// Flag that indicates if the kernel has nested Parallelism
808 bool NestedParallelism = false;
809
810 /// Abstract State interface
811 ///{
812
813 KernelInfoState() = default;
814 KernelInfoState(bool BestState) {
815 if (!BestState)
816 indicatePessimisticFixpoint();
817 }
818
819 /// See AbstractState::isValidState(...)
820 bool isValidState() const override { return true; }
821
822 /// See AbstractState::isAtFixpoint(...)
823 bool isAtFixpoint() const override { return IsAtFixpoint; }
824
825 /// See AbstractState::indicatePessimisticFixpoint(...)
826 ChangeStatus indicatePessimisticFixpoint() override {
827 IsAtFixpoint = true;
828 ParallelLevels.indicatePessimisticFixpoint();
829 ReachingKernelEntries.indicatePessimisticFixpoint();
830 SPMDCompatibilityTracker.indicatePessimisticFixpoint();
831 ReachedKnownParallelRegions.indicatePessimisticFixpoint();
832 ReachedUnknownParallelRegions.indicatePessimisticFixpoint();
833 NestedParallelism = true;
834 return ChangeStatus::CHANGED;
835 }
836
837 /// See AbstractState::indicateOptimisticFixpoint(...)
838 ChangeStatus indicateOptimisticFixpoint() override {
839 IsAtFixpoint = true;
840 ParallelLevels.indicateOptimisticFixpoint();
841 ReachingKernelEntries.indicateOptimisticFixpoint();
842 SPMDCompatibilityTracker.indicateOptimisticFixpoint();
843 ReachedKnownParallelRegions.indicateOptimisticFixpoint();
844 ReachedUnknownParallelRegions.indicateOptimisticFixpoint();
845 return ChangeStatus::UNCHANGED;
846 }
847
848 /// Return the assumed state
849 KernelInfoState &getAssumed() { return *this; }
850 const KernelInfoState &getAssumed() const { return *this; }
851
852 bool operator==(const KernelInfoState &RHS) const {
853 if (SPMDCompatibilityTracker != RHS.SPMDCompatibilityTracker)
854 return false;
855 if (ReachedKnownParallelRegions != RHS.ReachedKnownParallelRegions)
856 return false;
857 if (ReachedUnknownParallelRegions != RHS.ReachedUnknownParallelRegions)
858 return false;
859 if (ReachingKernelEntries != RHS.ReachingKernelEntries)
860 return false;
861 if (ParallelLevels != RHS.ParallelLevels)
862 return false;
863 if (NestedParallelism != RHS.NestedParallelism)
864 return false;
865 return true;
866 }
867
868 /// Returns true if this kernel contains any OpenMP parallel regions.
869 bool mayContainParallelRegion() {
870 return !ReachedKnownParallelRegions.empty() ||
871 !ReachedUnknownParallelRegions.empty();
872 }
873
874 /// Return empty set as the best state of potential values.
875 static KernelInfoState getBestState() { return KernelInfoState(true); }
876
877 static KernelInfoState getBestState(KernelInfoState &KIS) {
878 return getBestState();
879 }
880
881 /// Return full set as the worst state of potential values.
882 static KernelInfoState getWorstState() { return KernelInfoState(false); }
883
884 /// "Clamp" this state with \p KIS.
885 KernelInfoState operator^=(const KernelInfoState &KIS) {
886 // Do not merge two different _init and _deinit call sites.
887 if (KIS.KernelInitCB) {
888 if (KernelInitCB && KernelInitCB != KIS.KernelInitCB)
889 llvm_unreachable("Kernel that calls another kernel violates OpenMP-Opt "
890 "assumptions.");
891 KernelInitCB = KIS.KernelInitCB;
892 }
893 if (KIS.KernelDeinitCB) {
894 if (KernelDeinitCB && KernelDeinitCB != KIS.KernelDeinitCB)
895 llvm_unreachable("Kernel that calls another kernel violates OpenMP-Opt "
896 "assumptions.");
897 KernelDeinitCB = KIS.KernelDeinitCB;
898 }
899 if (KIS.KernelEnvC) {
900 if (KernelEnvC && KernelEnvC != KIS.KernelEnvC)
901 llvm_unreachable("Kernel that calls another kernel violates OpenMP-Opt "
902 "assumptions.");
903 KernelEnvC = KIS.KernelEnvC;
904 }
905 SPMDCompatibilityTracker ^= KIS.SPMDCompatibilityTracker;
906 ReachedKnownParallelRegions ^= KIS.ReachedKnownParallelRegions;
907 ReachedUnknownParallelRegions ^= KIS.ReachedUnknownParallelRegions;
908 NestedParallelism |= KIS.NestedParallelism;
909 return *this;
910 }
911
912 KernelInfoState operator&=(const KernelInfoState &KIS) {
913 return (*this ^= KIS);
914 }
915
916 ///}
917};
918
919/// Used to map the values physically (in the IR) stored in an offload
920/// array, to a vector in memory.
921struct OffloadArray {
922 /// Physical array (in the IR).
923 AllocaInst *Array = nullptr;
924 /// Mapped values.
925 SmallVector<Value *, 8> StoredValues;
926 /// Last stores made in the offload array.
927 SmallVector<StoreInst *, 8> LastAccesses;
928
929 OffloadArray() = default;
930
931 /// Initializes the OffloadArray with the values stored in \p Array before
932 /// instruction \p Before is reached. Returns false if the initialization
933 /// fails.
934 /// This MUST be used immediately after the construction of the object.
935 bool initialize(AllocaInst &Array, Instruction &Before) {
936 if (!getValues(Array, Before))
937 return false;
938
939 this->Array = &Array;
940 return true;
941 }
942
943 static const unsigned DeviceIDArgNum = 1;
944 static const unsigned BasePtrsArgNum = 3;
945 static const unsigned PtrsArgNum = 4;
946 static const unsigned SizesArgNum = 5;
947
948private:
949 /// Traverses the BasicBlock where \p Array is, collecting the stores made to
950 /// \p Array, leaving StoredValues with the values stored before the
951 /// instruction \p Before is reached.
952 bool getValues(AllocaInst &Array, Instruction &Before) {
953 // Initialize containers.
954 const DataLayout &DL = Array.getDataLayout();
955 std::optional<TypeSize> ArraySize = Array.getAllocationSize(DL);
956 if (!ArraySize || !ArraySize->isFixed())
957 return false;
958 const unsigned int PointerSize = DL.getPointerSize();
959 const uint64_t NumValues = ArraySize->getFixedValue() / PointerSize;
960 StoredValues.assign(NumElts: NumValues, Elt: nullptr);
961 LastAccesses.assign(NumElts: NumValues, Elt: nullptr);
962
963 // TODO: This assumes the instruction \p Before is in the same
964 // BasicBlock as Array. Make it general, for any control flow graph.
965 BasicBlock *BB = Array.getParent();
966 if (BB != Before.getParent())
967 return false;
968
969 for (Instruction &I : *BB) {
970 if (&I == &Before)
971 break;
972
973 if (!isa<StoreInst>(Val: &I))
974 continue;
975
976 auto *S = cast<StoreInst>(Val: &I);
977 int64_t Offset = -1;
978 auto *Dst =
979 GetPointerBaseWithConstantOffset(Ptr: S->getPointerOperand(), Offset, DL);
980 if (Dst == &Array) {
981 int64_t Idx = Offset / PointerSize;
982 // Ignore updates that must be UB (probably in dead code at runtime)
983 if ((uint64_t)Idx < NumValues) {
984 StoredValues[Idx] = getUnderlyingObject(V: S->getValueOperand());
985 LastAccesses[Idx] = S;
986 }
987 }
988 }
989
990 return isFilled();
991 }
992
993 /// Returns true if all values in StoredValues and
994 /// LastAccesses are not nullptrs.
995 bool isFilled() {
996 const unsigned NumValues = StoredValues.size();
997 for (unsigned I = 0; I < NumValues; ++I) {
998 if (!StoredValues[I] || !LastAccesses[I])
999 return false;
1000 }
1001
1002 return true;
1003 }
1004};
1005
1006// Use the max outlined entry count. Instrumentation counts should already
1007// match across merged callbacks, but sample profiles can differ. Returns
1008// nullopt when no callback entry count is available.
1009static std::optional<uint64_t>
1010getMergedWrapperEntryCount(ArrayRef<CallInst *> ForkCalls,
1011 unsigned CallbackOpNo) {
1012 std::optional<uint64_t> EntryCount;
1013 for (CallInst *CI : ForkCalls) {
1014 auto *Callback = dyn_cast<Function>(
1015 Val: CI->getArgOperand(i: CallbackOpNo)->stripPointerCasts());
1016 if (!Callback)
1017 continue;
1018 if (std::optional<uint64_t> EC = Callback->getEntryCount())
1019 // Each callback runs once per wrapper entry, so the counts should match.
1020 // The Sample profiles can disagree slightly, so take the largest.
1021 EntryCount = EntryCount ? std::max(a: *EntryCount, b: *EC) : *EC;
1022 }
1023 return EntryCount;
1024}
1025
1026static bool moduleHasSampleProfile(const Module &M) {
1027 std::unique_ptr<ProfileSummary> Summary(
1028 ProfileSummary::getFromMD(MD: M.getProfileSummary(/*IsCS=*/false)));
1029 return Summary && Summary->getKind() == ProfileSummary::PSK_Sample;
1030}
1031
1032struct OpenMPOpt {
1033
1034 using OptimizationRemarkGetter =
1035 function_ref<OptimizationRemarkEmitter &(Function *)>;
1036
1037 OpenMPOpt(SmallVectorImpl<Function *> &SCC, CallGraphUpdater &CGUpdater,
1038 OptimizationRemarkGetter OREGetter,
1039 OMPInformationCache &OMPInfoCache, Attributor &A)
1040 : M(*(*SCC.begin())->getParent()), SCC(SCC), CGUpdater(CGUpdater),
1041 OREGetter(OREGetter), OMPInfoCache(OMPInfoCache), A(A) {}
1042
1043 /// Check if any remarks are enabled for openmp-opt
1044 bool remarksEnabled() {
1045 auto &Ctx = M.getContext();
1046 return Ctx.getDiagHandlerPtr()->isAnyRemarkEnabled(DEBUG_TYPE);
1047 }
1048
1049 /// Run all OpenMP optimizations on the underlying SCC.
1050 bool run(bool IsModulePass) {
1051 if (SCC.empty())
1052 return false;
1053
1054 bool Changed = false;
1055
1056 LLVM_DEBUG(dbgs() << TAG << "Run on SCC with " << SCC.size()
1057 << " functions\n");
1058
1059 if (IsModulePass) {
1060 Changed |= runAttributor(IsModulePass);
1061
1062 // Recollect uses, in case Attributor deleted any.
1063 OMPInfoCache.recollectUses();
1064
1065 // TODO: This should be folded into buildCustomStateMachine.
1066 Changed |= rewriteDeviceCodeStateMachine();
1067
1068 // Drop the parallel data-sharing wrapper from __kmpc_parallel_60 calls in
1069 // SPMD kernels, where the runtime never uses it, so the (otherwise dead)
1070 // wrapper can be eliminated instead of lingering as a non-kernel LDS
1071 // user.
1072 Changed |= removeSPMDParallelWrappers();
1073
1074 if (remarksEnabled())
1075 analysisGlobalization();
1076 } else {
1077 if (PrintICVValues)
1078 printICVs();
1079 if (PrintOpenMPKernels)
1080 printKernels();
1081
1082 Changed |= runAttributor(IsModulePass);
1083
1084 // Recollect uses, in case Attributor deleted any.
1085 OMPInfoCache.recollectUses();
1086
1087 Changed |= deleteParallelRegions();
1088
1089 if (HideMemoryTransferLatency)
1090 Changed |= hideMemTransfersLatency();
1091 Changed |= deduplicateRuntimeCalls();
1092 if (EnableParallelRegionMerging) {
1093 if (mergeParallelRegions()) {
1094 deduplicateRuntimeCalls();
1095 Changed = true;
1096 }
1097 }
1098 }
1099
1100 if (OMPInfoCache.OpenMPPostLink)
1101 Changed |= removeRuntimeSymbols();
1102
1103 return Changed;
1104 }
1105
1106 /// Print initial ICV values for testing.
1107 /// FIXME: This should be done from the Attributor once it is added.
1108 void printICVs() const {
1109 InternalControlVar ICVs[] = {ICV_nthreads, ICV_active_levels, ICV_cancel,
1110 ICV_proc_bind};
1111
1112 for (Function *F : SCC) {
1113 for (auto ICV : ICVs) {
1114 auto ICVInfo = OMPInfoCache.ICVs[ICV];
1115 auto Remark = [&](OptimizationRemarkAnalysis ORA) {
1116 return ORA << "OpenMP ICV " << ore::NV("OpenMPICV", ICVInfo.Name)
1117 << " Value: "
1118 << (ICVInfo.InitValue
1119 ? toString(I: ICVInfo.InitValue->getValue(), Radix: 10, Signed: true)
1120 : "IMPLEMENTATION_DEFINED");
1121 };
1122
1123 emitRemark<OptimizationRemarkAnalysis>(F, RemarkName: "OpenMPICVTracker", RemarkCB&: Remark);
1124 }
1125 }
1126 }
1127
1128 /// Print OpenMP GPU kernels for testing.
1129 void printKernels() const {
1130 for (Function *F : SCC) {
1131 if (!omp::isOpenMPKernel(Fn&: *F))
1132 continue;
1133
1134 auto Remark = [&](OptimizationRemarkAnalysis ORA) {
1135 return ORA << "OpenMP GPU kernel "
1136 << ore::NV("OpenMPGPUKernel", F->getName()) << "\n";
1137 };
1138
1139 emitRemark<OptimizationRemarkAnalysis>(F, RemarkName: "OpenMPGPU", RemarkCB&: Remark);
1140 }
1141 }
1142
1143 /// Return the call if \p U is a callee use in a regular call. If \p RFI is
1144 /// given it has to be the callee or a nullptr is returned.
1145 static CallInst *getCallIfRegularCall(
1146 Use &U, OMPInformationCache::RuntimeFunctionInfo *RFI = nullptr) {
1147 CallInst *CI = dyn_cast<CallInst>(Val: U.getUser());
1148 if (CI && CI->isCallee(U: &U) && !CI->hasOperandBundles() &&
1149 (!RFI ||
1150 (RFI->Declaration && CI->getCalledFunction() == RFI->Declaration)))
1151 return CI;
1152 return nullptr;
1153 }
1154
1155 /// Return the call if \p V is a regular call. If \p RFI is given it has to be
1156 /// the callee or a nullptr is returned.
1157 static CallInst *getCallIfRegularCall(
1158 Value &V, OMPInformationCache::RuntimeFunctionInfo *RFI = nullptr) {
1159 CallInst *CI = dyn_cast<CallInst>(Val: &V);
1160 if (CI && !CI->hasOperandBundles() &&
1161 (!RFI ||
1162 (RFI->Declaration && CI->getCalledFunction() == RFI->Declaration)))
1163 return CI;
1164 return nullptr;
1165 }
1166
1167private:
1168 /// Merge parallel regions when it is safe.
1169 bool mergeParallelRegions() {
1170 const unsigned CallbackCalleeOperand = 2;
1171 const unsigned CallbackFirstArgOperand = 3;
1172 using InsertPointTy = OpenMPIRBuilder::InsertPointTy;
1173
1174 // Check if there are any __kmpc_fork_call calls to merge.
1175 OMPInformationCache::RuntimeFunctionInfo &RFI =
1176 OMPInfoCache.RFIs[OMPRTL___kmpc_fork_call];
1177
1178 if (!RFI.Declaration)
1179 return false;
1180
1181 // Unmergable calls that prevent merging a parallel region.
1182 OMPInformationCache::RuntimeFunctionInfo UnmergableCallsInfo[] = {
1183 OMPInfoCache.RFIs[OMPRTL___kmpc_push_proc_bind],
1184 OMPInfoCache.RFIs[OMPRTL___kmpc_push_num_threads],
1185 };
1186
1187 bool Changed = false;
1188 LoopInfo *LI = nullptr;
1189 DominatorTree *DT = nullptr;
1190
1191 SmallDenseMap<BasicBlock *, SmallPtrSet<Instruction *, 4>> BB2PRMap;
1192
1193 BasicBlock *StartBB = nullptr, *EndBB = nullptr;
1194 auto BodyGenCB = [&](InsertPointTy AllocaIP, InsertPointTy CodeGenIP,
1195 ArrayRef<BasicBlock *> DeallocBlocks) {
1196 BasicBlock *CGStartBB = CodeGenIP.getNodeParent();
1197 BasicBlock *CGEndBB = SplitBlock(Old: CGStartBB, SplitPt: &*CodeGenIP, DT, LI);
1198 assert(StartBB != nullptr && "StartBB should not be null");
1199 CGStartBB->getTerminator()->setSuccessor(Idx: 0, BB: StartBB);
1200 assert(EndBB != nullptr && "EndBB should not be null");
1201 EndBB->getTerminator()->setSuccessor(Idx: 0, BB: CGEndBB);
1202 return Error::success();
1203 };
1204
1205 auto PrivCB = [&](InsertPointTy AllocaIP, InsertPointTy CodeGenIP, Value &,
1206 Value &Inner, Value *&ReplacementValue) -> InsertPointTy {
1207 ReplacementValue = &Inner;
1208 return CodeGenIP;
1209 };
1210
1211 auto FiniCB = [&](InsertPointTy CodeGenIP) { return Error::success(); };
1212
1213 /// Create a sequential execution region within a merged parallel region,
1214 /// encapsulated in a master construct with a barrier for synchronization.
1215 auto CreateSequentialRegion = [&](Function *OuterFn,
1216 BasicBlock *OuterPredBB,
1217 Instruction *SeqStartI,
1218 Instruction *SeqEndI) {
1219 // Isolate the instructions of the sequential region to a separate
1220 // block.
1221 BasicBlock *ParentBB = SeqStartI->getParent();
1222 BasicBlock *SeqEndBB =
1223 SplitBlock(Old: ParentBB, SplitPt: SeqEndI->getNextNode(), DT, LI);
1224 BasicBlock *SeqAfterBB =
1225 SplitBlock(Old: SeqEndBB, SplitPt: &*SeqEndBB->getFirstInsertionPt(), DT, LI);
1226 BasicBlock *SeqStartBB =
1227 SplitBlock(Old: ParentBB, SplitPt: SeqStartI, DT, LI, MSSAU: nullptr, BBName: "seq.par.merged");
1228
1229 assert(ParentBB->getUniqueSuccessor() == SeqStartBB &&
1230 "Expected a different CFG");
1231 const DebugLoc DL = ParentBB->getTerminator()->getDebugLoc();
1232 ParentBB->getTerminator()->eraseFromParent();
1233
1234 auto BodyGenCB = [&](InsertPointTy AllocaIP, InsertPointTy CodeGenIP,
1235 ArrayRef<BasicBlock *> DeallocBlocks) {
1236 BasicBlock *CGStartBB = CodeGenIP.getNodeParent();
1237 BasicBlock *CGEndBB = SplitBlock(Old: CGStartBB, SplitPt: &*CodeGenIP, DT, LI);
1238 assert(SeqStartBB != nullptr && "SeqStartBB should not be null");
1239 CGStartBB->getTerminator()->setSuccessor(Idx: 0, BB: SeqStartBB);
1240 assert(SeqEndBB != nullptr && "SeqEndBB should not be null");
1241 SeqEndBB->getTerminator()->setSuccessor(Idx: 0, BB: CGEndBB);
1242 return Error::success();
1243 };
1244 auto FiniCB = [&](InsertPointTy CodeGenIP) { return Error::success(); };
1245
1246 // Find outputs from the sequential region to outside users and
1247 // broadcast their values to them.
1248 for (Instruction &I : *SeqStartBB) {
1249 SmallPtrSet<Instruction *, 4> OutsideUsers;
1250 for (User *Usr : I.users()) {
1251 Instruction &UsrI = *cast<Instruction>(Val: Usr);
1252 // Ignore outputs to LT intrinsics, code extraction for the merged
1253 // parallel region will fix them.
1254 if (UsrI.isLifetimeStartOrEnd())
1255 continue;
1256
1257 if (UsrI.getParent() != SeqStartBB)
1258 OutsideUsers.insert(Ptr: &UsrI);
1259 }
1260
1261 if (OutsideUsers.empty())
1262 continue;
1263
1264 // Emit an alloca in the outer region to store the broadcasted
1265 // value.
1266 const DataLayout &DL = M.getDataLayout();
1267 AllocaInst *AllocaI = new AllocaInst(
1268 I.getType(), DL.getAllocaAddrSpace(), nullptr,
1269 I.getName() + ".seq.output.alloc", OuterFn->front().begin());
1270
1271 // Emit a store instruction in the sequential BB to update the
1272 // value.
1273 new StoreInst(&I, AllocaI, SeqStartBB->getTerminator()->getIterator());
1274
1275 // Emit a load instruction and replace the use of the output value
1276 // with it.
1277 for (Instruction *UsrI : OutsideUsers) {
1278 LoadInst *LoadI = new LoadInst(I.getType(), AllocaI,
1279 I.getName() + ".seq.output.load",
1280 UsrI->getIterator());
1281 UsrI->replaceUsesOfWith(From: &I, To: LoadI);
1282 }
1283 }
1284
1285 OpenMPIRBuilder::LocationDescription Loc(ParentBB->end(), DL);
1286 OpenMPIRBuilder::InsertPointTy SeqAfterIP = cantFail(
1287 ValOrErr: OMPInfoCache.OMPBuilder.createMaster(Loc, BodyGenCB, FiniCB));
1288 cantFail(ValOrErr: OMPInfoCache.OMPBuilder.createBarrier(Loc: {SeqAfterIP, DL},
1289 Kind: OMPD_parallel));
1290
1291 UncondBrInst::Create(Target: SeqAfterBB, InsertBefore: SeqAfterIP.getNodeParent());
1292
1293 LLVM_DEBUG(dbgs() << TAG << "After sequential inlining " << *OuterFn
1294 << "\n");
1295 };
1296
1297 // Helper to merge the __kmpc_fork_call calls in MergableCIs. They are all
1298 // contained in BB and only separated by instructions that can be
1299 // redundantly executed in parallel. The block BB is split before the first
1300 // call (in MergableCIs) and after the last so the entire region we merge
1301 // into a single parallel region is contained in a single basic block
1302 // without any other instructions. We use the OpenMPIRBuilder to outline
1303 // that block and call the resulting function via __kmpc_fork_call.
1304 auto Merge = [&](const SmallVectorImpl<CallInst *> &MergableCIs,
1305 BasicBlock *BB) {
1306 // TODO: Change the interface to allow single CIs expanded, e.g, to
1307 // include an outer loop.
1308 assert(MergableCIs.size() > 1 && "Assumed multiple mergable CIs");
1309
1310 auto Remark = [&](OptimizationRemark OR) {
1311 OR << "Parallel region merged with parallel region"
1312 << (MergableCIs.size() > 2 ? "s" : "") << " at ";
1313 for (auto *CI : llvm::drop_begin(RangeOrContainer: MergableCIs)) {
1314 OR << ore::NV("OpenMPParallelMerge", CI->getDebugLoc());
1315 if (CI != MergableCIs.back())
1316 OR << ", ";
1317 }
1318 return OR << ".";
1319 };
1320
1321 emitRemark<OptimizationRemark>(I: MergableCIs.front(), RemarkName: "OMP150", RemarkCB&: Remark);
1322
1323 Function *OriginalFn = BB->getParent();
1324 LLVM_DEBUG(dbgs() << TAG << "Merge " << MergableCIs.size()
1325 << " parallel regions in " << OriginalFn->getName()
1326 << "\n");
1327
1328 // Isolate the calls to merge in a separate block.
1329 EndBB = SplitBlock(Old: BB, SplitPt: MergableCIs.back()->getNextNode(), DT, LI);
1330 BasicBlock *AfterBB =
1331 SplitBlock(Old: EndBB, SplitPt: &*EndBB->getFirstInsertionPt(), DT, LI);
1332 StartBB = SplitBlock(Old: BB, SplitPt: MergableCIs.front(), DT, LI, MSSAU: nullptr,
1333 BBName: "omp.par.merged");
1334
1335 assert(BB->getUniqueSuccessor() == StartBB && "Expected a different CFG");
1336 const DebugLoc DL = BB->getTerminator()->getDebugLoc();
1337 BB->getTerminator()->eraseFromParent();
1338
1339 // Create sequential regions for sequential instructions that are
1340 // in-between mergable parallel regions.
1341 for (auto *It = MergableCIs.begin(), *End = MergableCIs.end() - 1;
1342 It != End; ++It) {
1343 Instruction *ForkCI = *It;
1344 Instruction *NextForkCI = *(It + 1);
1345
1346 // Continue if there are not in-between instructions.
1347 if (ForkCI->getNextNode() == NextForkCI)
1348 continue;
1349
1350 CreateSequentialRegion(OriginalFn, BB, ForkCI->getNextNode(),
1351 NextForkCI->getPrevNode());
1352 }
1353
1354 OpenMPIRBuilder::LocationDescription Loc(BB->end(), DL);
1355 IRBuilder<>::InsertPoint AllocaIP(
1356 OriginalFn->getEntryBlock().getFirstInsertionPt());
1357 // Create the merged parallel region with default proc binding, to
1358 // avoid overriding binding settings, and without explicit cancellation.
1359 OpenMPIRBuilder::InsertPointTy AfterIP =
1360 cantFail(ValOrErr: OMPInfoCache.OMPBuilder.createParallel(
1361 Loc, AllocaIP, /* DeallocBlocks */ {}, BodyGenCB, PrivCB, FiniCB,
1362 IfCondition: nullptr, NumThreads: nullptr, ProcBind: OMP_PROC_BIND_default,
1363 /* IsCancellable */ false));
1364 UncondBrInst::Create(Target: AfterBB, InsertBefore: AfterIP.getNodeParent());
1365
1366 // Perform the actual outlining.
1367 OMPInfoCache.OMPBuilder.finalize(Fn: OriginalFn);
1368
1369 Function *OutlinedFn = MergableCIs.front()->getCaller();
1370 std::optional<uint64_t> WrapperCount =
1371 getMergedWrapperEntryCount(ForkCalls: MergableCIs, CallbackOpNo: CallbackCalleeOperand);
1372 // Leave the wrapper unprofiled when no callback has an entry count.
1373 if (WrapperCount)
1374 OutlinedFn->setEntryCount(Count: *WrapperCount);
1375 // Only sample PGO treats a profiled caller with no callsite weight as
1376 // cold. Instrumentation profiles derive that count from the entry count.
1377 const bool SampleProfile =
1378 moduleHasSampleProfile(M: *OriginalFn->getParent());
1379
1380 // Replace the __kmpc_fork_call calls with direct calls to the outlined
1381 // callbacks.
1382 SmallVector<Value *, 8> Args;
1383 for (auto *CI : MergableCIs) {
1384 Value *Callee = CI->getArgOperand(i: CallbackCalleeOperand);
1385 FunctionType *FT = OMPInfoCache.OMPBuilder.ParallelTask;
1386 Args.clear();
1387 Args.push_back(Elt: OutlinedFn->getArg(i: 0));
1388 Args.push_back(Elt: OutlinedFn->getArg(i: 1));
1389 for (unsigned U = CallbackFirstArgOperand, E = CI->arg_size(); U < E;
1390 ++U)
1391 Args.push_back(Elt: CI->getArgOperand(i: U));
1392
1393 CallInst *NewCI =
1394 CallInst::Create(Ty: FT, Func: Callee, Args, NameStr: "", InsertBefore: CI->getIterator());
1395 if (CI->getDebugLoc())
1396 NewCI->setDebugLoc(CI->getDebugLoc());
1397 // Each body runs once per wrapper entry. Without a callsite weight,
1398 // sample PGO treats these calls as cold.
1399 if (WrapperCount && SampleProfile) {
1400 setFittedBranchWeights(I&: *NewCI, Weights: {*WrapperCount},
1401 /*IsExpected=*/false);
1402 }
1403
1404 // Forward parameter attributes from the callback to the callee.
1405 for (unsigned U = CallbackFirstArgOperand, E = CI->arg_size(); U < E;
1406 ++U)
1407 for (const Attribute &A : CI->getAttributes().getParamAttrs(ArgNo: U))
1408 NewCI->addParamAttr(
1409 ArgNo: U - (CallbackFirstArgOperand - CallbackCalleeOperand), Attr: A);
1410
1411 // Emit an explicit barrier to replace the implicit fork-join barrier.
1412 if (CI != MergableCIs.back()) {
1413 // TODO: Remove barrier if the merged parallel region includes the
1414 // 'nowait' clause.
1415 cantFail(ValOrErr: OMPInfoCache.OMPBuilder.createBarrier(
1416 Loc: {NewCI->getNextNode()->getIterator(), NewCI->getDebugLoc()},
1417 Kind: OMPD_parallel));
1418 }
1419
1420 CI->eraseFromParent();
1421 }
1422
1423 assert(OutlinedFn != OriginalFn && "Outlining failed");
1424 CGUpdater.registerOutlinedFunction(OriginalFn&: *OriginalFn, NewFn&: *OutlinedFn);
1425 CGUpdater.reanalyzeFunction(Fn&: *OriginalFn);
1426
1427 NumOpenMPParallelRegionsMerged += MergableCIs.size();
1428
1429 return true;
1430 };
1431
1432 // Helper function that identifes sequences of
1433 // __kmpc_fork_call uses in a basic block.
1434 auto DetectPRsCB = [&](Use &U, Function &F) {
1435 CallInst *CI = getCallIfRegularCall(U, RFI: &RFI);
1436 BB2PRMap[CI->getParent()].insert(Ptr: CI);
1437
1438 return false;
1439 };
1440
1441 BB2PRMap.clear();
1442 RFI.foreachUse(SCC, CB: DetectPRsCB);
1443 SmallVector<SmallVector<CallInst *, 4>, 4> MergableCIsVector;
1444 // Find mergable parallel regions within a basic block that are
1445 // safe to merge, that is any in-between instructions can safely
1446 // execute in parallel after merging.
1447 // TODO: support merging across basic-blocks.
1448 for (auto &It : BB2PRMap) {
1449 auto &CIs = It.getSecond();
1450 if (CIs.size() < 2)
1451 continue;
1452
1453 BasicBlock *BB = It.getFirst();
1454 SmallVector<CallInst *, 4> MergableCIs;
1455
1456 /// Returns true if the instruction is mergable, false otherwise.
1457 /// A terminator instruction is unmergable by definition since merging
1458 /// works within a BB. Instructions before the mergable region are
1459 /// mergable if they are not calls to OpenMP runtime functions that may
1460 /// set different execution parameters for subsequent parallel regions.
1461 /// Instructions in-between parallel regions are mergable if they are not
1462 /// calls to any non-intrinsic function since that may call a non-mergable
1463 /// OpenMP runtime function.
1464 auto IsMergable = [&](Instruction &I, bool IsBeforeMergableRegion) {
1465 // We do not merge across BBs, hence return false (unmergable) if the
1466 // instruction is a terminator.
1467 if (I.isTerminator())
1468 return false;
1469
1470 if (!isa<CallInst>(Val: &I))
1471 return true;
1472
1473 CallInst *CI = cast<CallInst>(Val: &I);
1474 if (IsBeforeMergableRegion) {
1475 Function *CalledFunction = CI->getCalledFunction();
1476 if (!CalledFunction)
1477 return false;
1478 // Return false (unmergable) if the call before the parallel
1479 // region calls an explicit affinity (proc_bind) or number of
1480 // threads (num_threads) compiler-generated function. Those settings
1481 // may be incompatible with following parallel regions.
1482 // TODO: ICV tracking to detect compatibility.
1483 for (const auto &RFI : UnmergableCallsInfo) {
1484 if (CalledFunction == RFI.Declaration)
1485 return false;
1486 }
1487 } else {
1488 // Return false (unmergable) if there is a call instruction
1489 // in-between parallel regions when it is not an intrinsic. It
1490 // may call an unmergable OpenMP runtime function in its callpath.
1491 // TODO: Keep track of possible OpenMP calls in the callpath.
1492 if (!isa<IntrinsicInst>(Val: CI))
1493 return false;
1494 }
1495
1496 return true;
1497 };
1498 // Find maximal number of parallel region CIs that are safe to merge.
1499 for (auto It = BB->begin(), End = BB->end(); It != End;) {
1500 Instruction &I = *It;
1501 ++It;
1502
1503 if (CIs.count(Ptr: &I)) {
1504 MergableCIs.push_back(Elt: cast<CallInst>(Val: &I));
1505 continue;
1506 }
1507
1508 // Continue expanding if the instruction is mergable.
1509 if (IsMergable(I, MergableCIs.empty()))
1510 continue;
1511
1512 // Forward the instruction iterator to skip the next parallel region
1513 // since there is an unmergable instruction which can affect it.
1514 for (; It != End; ++It) {
1515 Instruction &SkipI = *It;
1516 if (CIs.count(Ptr: &SkipI)) {
1517 LLVM_DEBUG(dbgs() << TAG << "Skip parallel region " << SkipI
1518 << " due to " << I << "\n");
1519 ++It;
1520 break;
1521 }
1522 }
1523
1524 // Store mergable regions found.
1525 if (MergableCIs.size() > 1) {
1526 MergableCIsVector.push_back(Elt: MergableCIs);
1527 LLVM_DEBUG(dbgs() << TAG << "Found " << MergableCIs.size()
1528 << " parallel regions in block " << BB->getName()
1529 << " of function " << BB->getParent()->getName()
1530 << "\n";);
1531 }
1532
1533 MergableCIs.clear();
1534 }
1535
1536 if (!MergableCIsVector.empty()) {
1537 Changed = true;
1538
1539 for (auto &MergableCIs : MergableCIsVector)
1540 Merge(MergableCIs, BB);
1541 MergableCIsVector.clear();
1542 }
1543 }
1544
1545 if (Changed) {
1546 /// Re-collect use for fork calls, emitted barrier calls, and
1547 /// any emitted master/end_master calls.
1548 OMPInfoCache.recollectUsesForFunction(RTF: OMPRTL___kmpc_fork_call);
1549 OMPInfoCache.recollectUsesForFunction(RTF: OMPRTL___kmpc_barrier);
1550 OMPInfoCache.recollectUsesForFunction(RTF: OMPRTL___kmpc_master);
1551 OMPInfoCache.recollectUsesForFunction(RTF: OMPRTL___kmpc_end_master);
1552 }
1553
1554 return Changed;
1555 }
1556
1557 /// Try to delete parallel regions if possible.
1558 bool deleteParallelRegions() {
1559 const unsigned CallbackCalleeOperand = 2;
1560
1561 OMPInformationCache::RuntimeFunctionInfo &RFI =
1562 OMPInfoCache.RFIs[OMPRTL___kmpc_fork_call];
1563
1564 if (!RFI.Declaration)
1565 return false;
1566
1567 bool Changed = false;
1568 auto DeleteCallCB = [&](Use &U, Function &) {
1569 CallInst *CI = getCallIfRegularCall(U);
1570 if (!CI)
1571 return false;
1572 auto *Fn = dyn_cast<Function>(
1573 Val: CI->getArgOperand(i: CallbackCalleeOperand)->stripPointerCasts());
1574 if (!Fn)
1575 return false;
1576 if (!Fn->onlyReadsMemory())
1577 return false;
1578 if (!Fn->hasFnAttribute(Kind: Attribute::WillReturn))
1579 return false;
1580
1581 LLVM_DEBUG(dbgs() << TAG << "Delete read-only parallel region in "
1582 << CI->getCaller()->getName() << "\n");
1583
1584 auto Remark = [&](OptimizationRemark OR) {
1585 return OR << "Removing parallel region with no side-effects.";
1586 };
1587 emitRemark<OptimizationRemark>(I: CI, RemarkName: "OMP160", RemarkCB&: Remark);
1588
1589 CI->eraseFromParent();
1590 Changed = true;
1591 ++NumOpenMPParallelRegionsDeleted;
1592 return true;
1593 };
1594
1595 RFI.foreachUse(SCC, CB: DeleteCallCB);
1596
1597 return Changed;
1598 }
1599
1600 /// Try to eliminate runtime calls by reusing existing ones.
1601 bool deduplicateRuntimeCalls() {
1602 bool Changed = false;
1603
1604 RuntimeFunction DeduplicableRuntimeCallIDs[] = {
1605 OMPRTL_omp_get_num_threads,
1606 OMPRTL_omp_in_parallel,
1607 OMPRTL_omp_get_cancellation,
1608 OMPRTL_omp_get_supported_active_levels,
1609 OMPRTL_omp_get_level,
1610 OMPRTL_omp_get_ancestor_thread_num,
1611 OMPRTL_omp_get_team_size,
1612 OMPRTL_omp_get_active_level,
1613 OMPRTL_omp_in_final,
1614 OMPRTL_omp_get_proc_bind,
1615 OMPRTL_omp_get_num_places,
1616 OMPRTL_omp_get_num_procs,
1617 OMPRTL_omp_get_place_num,
1618 OMPRTL_omp_get_partition_num_places,
1619 OMPRTL_omp_get_partition_place_nums};
1620
1621 // Global-tid is handled separately.
1622 SmallSetVector<Value *, 16> GTIdArgs;
1623 collectGlobalThreadIdArguments(GTIdArgs);
1624 LLVM_DEBUG(dbgs() << TAG << "Found " << GTIdArgs.size()
1625 << " global thread ID arguments\n");
1626
1627 for (Function *F : SCC) {
1628 for (auto DeduplicableRuntimeCallID : DeduplicableRuntimeCallIDs)
1629 Changed |= deduplicateRuntimeCalls(
1630 F&: *F, RFI&: OMPInfoCache.RFIs[DeduplicableRuntimeCallID]);
1631
1632 // __kmpc_global_thread_num is special as we can replace it with an
1633 // argument in enough cases to make it worth trying.
1634 Value *GTIdArg = nullptr;
1635 for (Argument &Arg : F->args())
1636 if (GTIdArgs.count(key: &Arg)) {
1637 GTIdArg = &Arg;
1638 break;
1639 }
1640 Changed |= deduplicateRuntimeCalls(
1641 F&: *F, RFI&: OMPInfoCache.RFIs[OMPRTL___kmpc_global_thread_num], ReplVal: GTIdArg);
1642 }
1643
1644 return Changed;
1645 }
1646
1647 /// Tries to remove known runtime symbols that are optional from the module.
1648 bool removeRuntimeSymbols() {
1649 // The RPC client symbol is defined in `libc` and indicates that something
1650 // required an RPC server. If its users were all optimized out then we can
1651 // safely remove it.
1652 // TODO: This should be somewhere more common in the future.
1653 if (GlobalVariable *GV = M.getNamedGlobal(Name: "__llvm_rpc_client")) {
1654 if (GV->hasNUsesOrMore(N: 1))
1655 return false;
1656
1657 GV->replaceAllUsesWith(V: PoisonValue::get(T: GV->getType()));
1658 GV->eraseFromParent();
1659 return true;
1660 }
1661 return false;
1662 }
1663
1664 /// Tries to hide the latency of runtime calls that involve host to
1665 /// device memory transfers by splitting them into their "issue" and "wait"
1666 /// versions. The "issue" is moved upwards as much as possible. The "wait" is
1667 /// moved downards as much as possible. The "issue" issues the memory transfer
1668 /// asynchronously, returning a handle. The "wait" waits in the returned
1669 /// handle for the memory transfer to finish.
1670 bool hideMemTransfersLatency() {
1671 auto &RFI = OMPInfoCache.RFIs[OMPRTL___tgt_target_data_begin_mapper];
1672 bool Changed = false;
1673 auto SplitMemTransfers = [&](Use &U, Function &Decl) {
1674 auto *RTCall = getCallIfRegularCall(U, RFI: &RFI);
1675 if (!RTCall)
1676 return false;
1677
1678 OffloadArray OffloadArrays[3];
1679 if (!getValuesInOffloadArrays(RuntimeCall&: *RTCall, OAs: OffloadArrays))
1680 return false;
1681
1682 LLVM_DEBUG(dumpValuesInOffloadArrays(OffloadArrays));
1683
1684 // TODO: Check if can be moved upwards.
1685 bool WasSplit = false;
1686 Instruction *WaitMovementPoint = canBeMovedDownwards(RuntimeCall&: *RTCall);
1687 if (WaitMovementPoint)
1688 WasSplit = splitTargetDataBeginRTC(RuntimeCall&: *RTCall, WaitMovementPoint&: *WaitMovementPoint);
1689
1690 Changed |= WasSplit;
1691 return WasSplit;
1692 };
1693 if (OMPInfoCache.runtimeFnsAvailable(
1694 Fns: {OMPRTL___tgt_target_data_begin_mapper_issue,
1695 OMPRTL___tgt_target_data_begin_mapper_wait}))
1696 RFI.foreachUse(SCC, CB: SplitMemTransfers);
1697
1698 return Changed;
1699 }
1700
1701 void analysisGlobalization() {
1702 auto &RFI = OMPInfoCache.RFIs[OMPRTL___kmpc_alloc_shared];
1703
1704 auto CheckGlobalization = [&](Use &U, Function &Decl) {
1705 if (CallInst *CI = getCallIfRegularCall(U, RFI: &RFI)) {
1706 auto Remark = [&](OptimizationRemarkMissed ORM) {
1707 return ORM
1708 << "Found thread data sharing on the GPU. "
1709 << "Expect degraded performance due to data globalization.";
1710 };
1711 emitRemark<OptimizationRemarkMissed>(I: CI, RemarkName: "OMP112", RemarkCB&: Remark);
1712 }
1713
1714 return false;
1715 };
1716
1717 RFI.foreachUse(SCC, CB: CheckGlobalization);
1718 }
1719
1720 /// Maps the values stored in the offload arrays passed as arguments to
1721 /// \p RuntimeCall into the offload arrays in \p OAs.
1722 bool getValuesInOffloadArrays(CallInst &RuntimeCall,
1723 MutableArrayRef<OffloadArray> OAs) {
1724 assert(OAs.size() == 3 && "Need space for three offload arrays!");
1725
1726 // A runtime call that involves memory offloading looks something like:
1727 // call void @__tgt_target_data_begin_mapper(arg0, arg1,
1728 // i8** %offload_baseptrs, i8** %offload_ptrs, i64* %offload_sizes,
1729 // ...)
1730 // So, the idea is to access the allocas that allocate space for these
1731 // offload arrays, offload_baseptrs, offload_ptrs, offload_sizes.
1732 // Therefore:
1733 // i8** %offload_baseptrs.
1734 Value *BasePtrsArg =
1735 RuntimeCall.getArgOperand(i: OffloadArray::BasePtrsArgNum);
1736 // i8** %offload_ptrs.
1737 Value *PtrsArg = RuntimeCall.getArgOperand(i: OffloadArray::PtrsArgNum);
1738 // i8** %offload_sizes.
1739 Value *SizesArg = RuntimeCall.getArgOperand(i: OffloadArray::SizesArgNum);
1740
1741 // Get values stored in **offload_baseptrs.
1742 auto *V = getUnderlyingObject(V: BasePtrsArg);
1743 if (!isa<AllocaInst>(Val: V))
1744 return false;
1745 auto *BasePtrsArray = cast<AllocaInst>(Val: V);
1746 if (!OAs[0].initialize(Array&: *BasePtrsArray, Before&: RuntimeCall))
1747 return false;
1748
1749 // Get values stored in **offload_baseptrs.
1750 V = getUnderlyingObject(V: PtrsArg);
1751 if (!isa<AllocaInst>(Val: V))
1752 return false;
1753 auto *PtrsArray = cast<AllocaInst>(Val: V);
1754 if (!OAs[1].initialize(Array&: *PtrsArray, Before&: RuntimeCall))
1755 return false;
1756
1757 // Get values stored in **offload_sizes.
1758 V = getUnderlyingObject(V: SizesArg);
1759 // If it's a [constant] global array don't analyze it.
1760 if (isa<GlobalValue>(Val: V))
1761 return isa<Constant>(Val: V);
1762 if (!isa<AllocaInst>(Val: V))
1763 return false;
1764
1765 auto *SizesArray = cast<AllocaInst>(Val: V);
1766 if (!OAs[2].initialize(Array&: *SizesArray, Before&: RuntimeCall))
1767 return false;
1768
1769 return true;
1770 }
1771
1772 /// Prints the values in the OffloadArrays \p OAs using LLVM_DEBUG.
1773 /// For now this is a way to test that the function getValuesInOffloadArrays
1774 /// is working properly.
1775 /// TODO: Move this to a unittest when unittests are available for OpenMPOpt.
1776 void dumpValuesInOffloadArrays(ArrayRef<OffloadArray> OAs) {
1777 assert(OAs.size() == 3 && "There are three offload arrays to debug!");
1778
1779 LLVM_DEBUG(dbgs() << TAG << " Successfully got offload values:\n");
1780 std::string ValuesStr;
1781 raw_string_ostream Printer(ValuesStr);
1782 std::string Separator = " --- ";
1783
1784 for (auto *BP : OAs[0].StoredValues) {
1785 BP->print(O&: Printer);
1786 Printer << Separator;
1787 }
1788 LLVM_DEBUG(dbgs() << "\t\toffload_baseptrs: " << ValuesStr << "\n");
1789 ValuesStr.clear();
1790
1791 for (auto *P : OAs[1].StoredValues) {
1792 P->print(O&: Printer);
1793 Printer << Separator;
1794 }
1795 LLVM_DEBUG(dbgs() << "\t\toffload_ptrs: " << ValuesStr << "\n");
1796 ValuesStr.clear();
1797
1798 for (auto *S : OAs[2].StoredValues) {
1799 S->print(O&: Printer);
1800 Printer << Separator;
1801 }
1802 LLVM_DEBUG(dbgs() << "\t\toffload_sizes: " << ValuesStr << "\n");
1803 }
1804
1805 /// Returns the instruction where the "wait" counterpart \p RuntimeCall can be
1806 /// moved. Returns nullptr if the movement is not possible, or not worth it.
1807 Instruction *canBeMovedDownwards(CallInst &RuntimeCall) {
1808 // FIXME: This traverses only the BasicBlock where RuntimeCall is.
1809 // Make it traverse the CFG.
1810
1811 Instruction *CurrentI = &RuntimeCall;
1812 bool IsWorthIt = false;
1813 while ((CurrentI = CurrentI->getNextNode())) {
1814
1815 // TODO: Once we detect the regions to be offloaded we should use the
1816 // alias analysis manager to check if CurrentI may modify one of
1817 // the offloaded regions.
1818 if (CurrentI->mayHaveSideEffects() || CurrentI->mayReadFromMemory()) {
1819 if (IsWorthIt)
1820 return CurrentI;
1821
1822 return nullptr;
1823 }
1824
1825 // FIXME: For now if we move it over anything without side effect
1826 // is worth it.
1827 IsWorthIt = true;
1828 }
1829
1830 // Return end of BasicBlock.
1831 return RuntimeCall.getParent()->getTerminator();
1832 }
1833
1834 /// Splits \p RuntimeCall into its "issue" and "wait" counterparts.
1835 bool splitTargetDataBeginRTC(CallInst &RuntimeCall,
1836 Instruction &WaitMovementPoint) {
1837 // Create stack allocated handle (__tgt_async_info) at the beginning of the
1838 // function. Used for storing information of the async transfer, allowing to
1839 // wait on it later.
1840 auto &IRBuilder = OMPInfoCache.OMPBuilder;
1841 Function *F = RuntimeCall.getCaller();
1842 BasicBlock &Entry = F->getEntryBlock();
1843 IRBuilder.Builder.SetInsertPoint(Entry.getFirstNonPHIOrAlloca());
1844 Value *Handle = IRBuilder.Builder.CreateAlloca(
1845 Ty: IRBuilder.AsyncInfo, /*ArraySize=*/nullptr, Name: "handle");
1846 Handle =
1847 IRBuilder.Builder.CreateAddrSpaceCast(V: Handle, DestTy: IRBuilder.AsyncInfoPtr);
1848
1849 // Add "issue" runtime call declaration:
1850 // declare %struct.tgt_async_info @__tgt_target_data_begin_issue(i64, i32,
1851 // i8**, i8**, i64*, i64*)
1852 FunctionCallee IssueDecl = IRBuilder.getOrCreateRuntimeFunction(
1853 M, FnID: OMPRTL___tgt_target_data_begin_mapper_issue);
1854
1855 // Change RuntimeCall call site for its asynchronous version.
1856 SmallVector<Value *, 16> Args;
1857 for (auto &Arg : RuntimeCall.args())
1858 Args.push_back(Elt: Arg.get());
1859 Args.push_back(Elt: Handle);
1860
1861 CallInst *IssueCallsite = CallInst::Create(Func: IssueDecl, Args, /*NameStr=*/"",
1862 InsertBefore: RuntimeCall.getIterator());
1863 OMPInfoCache.setCallingConvention(Callee: IssueDecl, CI: IssueCallsite);
1864 RuntimeCall.eraseFromParent();
1865
1866 // Add "wait" runtime call declaration:
1867 // declare void @__tgt_target_data_begin_wait(i64, %struct.__tgt_async_info)
1868 FunctionCallee WaitDecl = IRBuilder.getOrCreateRuntimeFunction(
1869 M, FnID: OMPRTL___tgt_target_data_begin_mapper_wait);
1870
1871 Value *WaitParams[2] = {
1872 IssueCallsite->getArgOperand(
1873 i: OffloadArray::DeviceIDArgNum), // device_id.
1874 Handle // handle to wait on.
1875 };
1876 CallInst *WaitCallsite = CallInst::Create(
1877 Func: WaitDecl, Args: WaitParams, /*NameStr=*/"", InsertBefore: WaitMovementPoint.getIterator());
1878 OMPInfoCache.setCallingConvention(Callee: WaitDecl, CI: WaitCallsite);
1879
1880 return true;
1881 }
1882
1883 static Value *combinedIdentStruct(Value *CurrentIdent, Value *NextIdent,
1884 bool GlobalOnly, bool &SingleChoice) {
1885 if (CurrentIdent == NextIdent)
1886 return CurrentIdent;
1887
1888 // TODO: Figure out how to actually combine multiple debug locations. For
1889 // now we just keep an existing one if there is a single choice.
1890 if (!GlobalOnly || isa<GlobalValue>(Val: NextIdent)) {
1891 SingleChoice = !CurrentIdent;
1892 return NextIdent;
1893 }
1894 return nullptr;
1895 }
1896
1897 /// Return an `struct ident_t*` value that represents the ones used in the
1898 /// calls of \p RFI inside of \p F. If \p GlobalOnly is true, we will not
1899 /// return a local `struct ident_t*`. For now, if we cannot find a suitable
1900 /// return value we create one from scratch. We also do not yet combine
1901 /// information, e.g., the source locations, see combinedIdentStruct.
1902 Value *
1903 getCombinedIdentFromCallUsesIn(OMPInformationCache::RuntimeFunctionInfo &RFI,
1904 Function &F, bool GlobalOnly) {
1905 bool SingleChoice = true;
1906 Value *Ident = nullptr;
1907 auto CombineIdentStruct = [&](Use &U, Function &Caller) {
1908 CallInst *CI = getCallIfRegularCall(U, RFI: &RFI);
1909 if (!CI || &F != &Caller)
1910 return false;
1911 Ident = combinedIdentStruct(CurrentIdent: Ident, NextIdent: CI->getArgOperand(i: 0),
1912 /* GlobalOnly */ true, SingleChoice);
1913 return false;
1914 };
1915 RFI.foreachUse(SCC, CB: CombineIdentStruct);
1916
1917 if (!Ident || !SingleChoice) {
1918 // The IRBuilder uses the insertion block to get to the module, this is
1919 // unfortunate but we work around it for now. No instruction is emitted
1920 // here, so there is no debug location to preserve.
1921 if (!OMPInfoCache.OMPBuilder.getInsertionPoint().isValid())
1922 OMPInfoCache.OMPBuilder.updateToLocation(
1923 Loc: {F.getEntryBlock().begin(), DebugLoc()});
1924 // Create a fallback location if non was found.
1925 // TODO: Use the debug locations of the calls instead.
1926 uint32_t SrcLocStrSize;
1927 Constant *Loc =
1928 OMPInfoCache.OMPBuilder.getOrCreateDefaultSrcLocStr(SrcLocStrSize);
1929 Ident = OMPInfoCache.OMPBuilder.getOrCreateIdent(SrcLocStr: Loc, SrcLocStrSize);
1930 }
1931 return Ident;
1932 }
1933
1934 /// Try to eliminate calls of \p RFI in \p F by reusing an existing one or
1935 /// \p ReplVal if given.
1936 bool deduplicateRuntimeCalls(Function &F,
1937 OMPInformationCache::RuntimeFunctionInfo &RFI,
1938 Value *ReplVal = nullptr) {
1939 auto *UV = RFI.getUseVector(F);
1940 if (!UV || UV->size() + (ReplVal != nullptr) < 2)
1941 return false;
1942
1943 LLVM_DEBUG(
1944 dbgs() << TAG << "Deduplicate " << UV->size() << " uses of " << RFI.Name
1945 << (ReplVal ? " with an existing value\n" : "\n") << "\n");
1946
1947 assert((!ReplVal || (isa<Argument>(ReplVal) &&
1948 cast<Argument>(ReplVal)->getParent() == &F)) &&
1949 "Unexpected replacement value!");
1950
1951 // TODO: Use dominance to find a good position instead.
1952 auto CanBeMoved = [this](CallBase &CB) {
1953 unsigned NumArgs = CB.arg_size();
1954 if (NumArgs == 0)
1955 return true;
1956 if (CB.getArgOperand(i: 0)->getType() != OMPInfoCache.OMPBuilder.IdentPtr)
1957 return false;
1958 for (unsigned U = 1; U < NumArgs; ++U)
1959 if (isa<Instruction>(Val: CB.getArgOperand(i: U)))
1960 return false;
1961 return true;
1962 };
1963
1964 if (!ReplVal) {
1965 auto *DT =
1966 OMPInfoCache.getAnalysisResultForFunction<DominatorTreeAnalysis>(F);
1967 if (!DT)
1968 return false;
1969 Instruction *IP = nullptr;
1970 for (Use *U : *UV) {
1971 if (CallInst *CI = getCallIfRegularCall(U&: *U, RFI: &RFI)) {
1972 if (IP)
1973 IP = DT->findNearestCommonDominator(I1: IP, I2: CI);
1974 else
1975 IP = CI;
1976 if (!CanBeMoved(*CI))
1977 continue;
1978 if (!ReplVal)
1979 ReplVal = CI;
1980 }
1981 }
1982 if (!ReplVal)
1983 return false;
1984 assert(IP && "Expected insertion point!");
1985 cast<Instruction>(Val: ReplVal)->moveBefore(InsertPos: IP->getIterator());
1986 }
1987
1988 // If we use a call as a replacement value we need to make sure the ident is
1989 // valid at the new location. For now we just pick a global one, either
1990 // existing and used by one of the calls, or created from scratch.
1991 if (CallBase *CI = dyn_cast<CallBase>(Val: ReplVal)) {
1992 if (!CI->arg_empty() &&
1993 CI->getArgOperand(i: 0)->getType() == OMPInfoCache.OMPBuilder.IdentPtr) {
1994 Value *Ident = getCombinedIdentFromCallUsesIn(RFI, F,
1995 /* GlobalOnly */ true);
1996 CI->setArgOperand(i: 0, v: Ident);
1997 }
1998 }
1999
2000 bool Changed = false;
2001 auto ReplaceAndDeleteCB = [&](Use &U, Function &Caller) {
2002 CallInst *CI = getCallIfRegularCall(U, RFI: &RFI);
2003 if (!CI || CI == ReplVal || &F != &Caller)
2004 return false;
2005 assert(CI->getCaller() == &F && "Unexpected call!");
2006
2007 auto Remark = [&](OptimizationRemark OR) {
2008 return OR << "OpenMP runtime call "
2009 << ore::NV("OpenMPOptRuntime", RFI.Name) << " deduplicated.";
2010 };
2011 if (CI->getDebugLoc())
2012 emitRemark<OptimizationRemark>(I: CI, RemarkName: "OMP170", RemarkCB&: Remark);
2013 else
2014 emitRemark<OptimizationRemark>(F: &F, RemarkName: "OMP170", RemarkCB&: Remark);
2015
2016 CI->replaceAllUsesWith(V: ReplVal);
2017 CI->eraseFromParent();
2018 ++NumOpenMPRuntimeCallsDeduplicated;
2019 Changed = true;
2020 return true;
2021 };
2022 RFI.foreachUse(SCC, CB: ReplaceAndDeleteCB);
2023
2024 return Changed;
2025 }
2026
2027 /// Collect arguments that represent the global thread id in \p GTIdArgs.
2028 void collectGlobalThreadIdArguments(SmallSetVector<Value *, 16> &GTIdArgs) {
2029 // TODO: Below we basically perform a fixpoint iteration with a pessimistic
2030 // initialization. We could define an AbstractAttribute instead and
2031 // run the Attributor here once it can be run as an SCC pass.
2032
2033 // Helper to check the argument \p ArgNo at all call sites of \p F for
2034 // a GTId.
2035 auto CallArgOpIsGTId = [&](Function &F, unsigned ArgNo, CallInst &RefCI) {
2036 if (!F.hasLocalLinkage())
2037 return false;
2038 for (Use &U : F.uses()) {
2039 if (CallInst *CI = getCallIfRegularCall(U)) {
2040 Value *ArgOp = CI->getArgOperand(i: ArgNo);
2041 if (CI == &RefCI || GTIdArgs.count(key: ArgOp) ||
2042 getCallIfRegularCall(
2043 V&: *ArgOp, RFI: &OMPInfoCache.RFIs[OMPRTL___kmpc_global_thread_num]))
2044 continue;
2045 }
2046 return false;
2047 }
2048 return true;
2049 };
2050
2051 // Helper to identify uses of a GTId as GTId arguments.
2052 auto AddUserArgs = [&](Value &GTId) {
2053 for (Use &U : GTId.uses())
2054 if (CallInst *CI = dyn_cast<CallInst>(Val: U.getUser()))
2055 if (CI->isArgOperand(U: &U))
2056 if (Function *Callee = CI->getCalledFunction())
2057 if (CallArgOpIsGTId(*Callee, U.getOperandNo(), *CI))
2058 GTIdArgs.insert(X: Callee->getArg(i: U.getOperandNo()));
2059 };
2060
2061 // The argument users of __kmpc_global_thread_num calls are GTIds.
2062 OMPInformationCache::RuntimeFunctionInfo &GlobThreadNumRFI =
2063 OMPInfoCache.RFIs[OMPRTL___kmpc_global_thread_num];
2064
2065 GlobThreadNumRFI.foreachUse(SCC, CB: [&](Use &U, Function &F) {
2066 if (CallInst *CI = getCallIfRegularCall(U, RFI: &GlobThreadNumRFI))
2067 AddUserArgs(*CI);
2068 return false;
2069 });
2070
2071 // Transitively search for more arguments by looking at the users of the
2072 // ones we know already. During the search the GTIdArgs vector is extended
2073 // so we cannot cache the size nor can we use a range based for.
2074 for (unsigned U = 0; U < GTIdArgs.size(); ++U)
2075 AddUserArgs(*GTIdArgs[U]);
2076 }
2077
2078 /// Kernel (=GPU) optimizations and utility functions
2079 ///
2080 ///{{
2081
2082 /// Cache to remember the unique kernel for a function.
2083 DenseMap<Function *, std::optional<Kernel>> UniqueKernelMap;
2084
2085 /// Find the unique kernel that will execute \p F, if any.
2086 Kernel getUniqueKernelFor(Function &F);
2087
2088 /// Find the unique kernel that will execute \p I, if any.
2089 Kernel getUniqueKernelFor(Instruction &I) {
2090 return getUniqueKernelFor(F&: *I.getFunction());
2091 }
2092
2093 /// Rewrite the device (=GPU) code state machine create in non-SPMD mode in
2094 /// the cases we can avoid taking the address of a function.
2095 bool rewriteDeviceCodeStateMachine();
2096
2097 /// In SPMD kernels the parallel data-sharing wrapper passed to
2098 /// __kmpc_parallel_60 is never used by the runtime; null it out so the dead
2099 /// wrapper (and any LDS it references) can be removed.
2100 bool removeSPMDParallelWrappers();
2101
2102 ///
2103 ///}}
2104
2105 /// Emit a remark generically
2106 ///
2107 /// This template function can be used to generically emit a remark. The
2108 /// RemarkKind should be one of the following:
2109 /// - OptimizationRemark to indicate a successful optimization attempt
2110 /// - OptimizationRemarkMissed to report a failed optimization attempt
2111 /// - OptimizationRemarkAnalysis to provide additional information about an
2112 /// optimization attempt
2113 ///
2114 /// The remark is built using a callback function provided by the caller that
2115 /// takes a RemarkKind as input and returns a RemarkKind.
2116 template <typename RemarkKind, typename RemarkCallBack>
2117 void emitRemark(Instruction *I, StringRef RemarkName,
2118 RemarkCallBack &&RemarkCB) const {
2119 Function *F = I->getParent()->getParent();
2120 auto &ORE = OREGetter(F);
2121
2122 if (RemarkName.starts_with(Prefix: "OMP"))
2123 ORE.emit([&]() {
2124 return RemarkCB(RemarkKind(DEBUG_TYPE, RemarkName, I))
2125 << " [" << RemarkName << "]";
2126 });
2127 else
2128 ORE.emit(
2129 [&]() { return RemarkCB(RemarkKind(DEBUG_TYPE, RemarkName, I)); });
2130 }
2131
2132 /// Emit a remark on a function.
2133 template <typename RemarkKind, typename RemarkCallBack>
2134 void emitRemark(Function *F, StringRef RemarkName,
2135 RemarkCallBack &&RemarkCB) const {
2136 auto &ORE = OREGetter(F);
2137
2138 if (RemarkName.starts_with(Prefix: "OMP"))
2139 ORE.emit([&]() {
2140 return RemarkCB(RemarkKind(DEBUG_TYPE, RemarkName, F))
2141 << " [" << RemarkName << "]";
2142 });
2143 else
2144 ORE.emit(
2145 [&]() { return RemarkCB(RemarkKind(DEBUG_TYPE, RemarkName, F)); });
2146 }
2147
2148 /// The underlying module.
2149 Module &M;
2150
2151 /// The SCC we are operating on.
2152 SmallVectorImpl<Function *> &SCC;
2153
2154 /// Callback to update the call graph, the first argument is a removed call,
2155 /// the second an optional replacement call.
2156 CallGraphUpdater &CGUpdater;
2157
2158 /// Callback to get an OptimizationRemarkEmitter from a Function *
2159 OptimizationRemarkGetter OREGetter;
2160
2161 /// OpenMP-specific information cache. Also Used for Attributor runs.
2162 OMPInformationCache &OMPInfoCache;
2163
2164 /// Attributor instance.
2165 Attributor &A;
2166
2167 /// Helper function to run Attributor on SCC.
2168 bool runAttributor(bool IsModulePass) {
2169 if (SCC.empty())
2170 return false;
2171
2172 registerAAs(IsModulePass);
2173
2174 ChangeStatus Changed = A.run();
2175
2176 LLVM_DEBUG(dbgs() << "[Attributor] Done with " << SCC.size()
2177 << " functions, result: " << Changed << ".\n");
2178
2179 if (Changed == ChangeStatus::CHANGED)
2180 OMPInfoCache.invalidateAnalyses();
2181
2182 return Changed == ChangeStatus::CHANGED;
2183 }
2184
2185 void registerFoldRuntimeCall(RuntimeFunction RF);
2186
2187 /// Populate the Attributor with abstract attribute opportunities in the
2188 /// functions.
2189 void registerAAs(bool IsModulePass);
2190
2191public:
2192 /// Callback to register AAs for live functions, including internal functions
2193 /// marked live during the traversal.
2194 static void registerAAsForFunction(Attributor &A, const Function &F);
2195};
2196
2197Kernel OpenMPOpt::getUniqueKernelFor(Function &F) {
2198 if (OMPInfoCache.CGSCC && !OMPInfoCache.CGSCC->empty() &&
2199 !OMPInfoCache.CGSCC->contains(key: &F))
2200 return nullptr;
2201
2202 // Use a scope to keep the lifetime of the CachedKernel short.
2203 {
2204 std::optional<Kernel> &CachedKernel = UniqueKernelMap[&F];
2205 if (CachedKernel)
2206 return *CachedKernel;
2207
2208 // TODO: We should use an AA to create an (optimistic and callback
2209 // call-aware) call graph. For now we stick to simple patterns that
2210 // are less powerful, basically the worst fixpoint.
2211 if (isOpenMPKernel(Fn&: F)) {
2212 CachedKernel = Kernel(&F);
2213 return *CachedKernel;
2214 }
2215
2216 CachedKernel = nullptr;
2217 if (!F.hasLocalLinkage()) {
2218
2219 // See https://openmp.llvm.org/remarks/OptimizationRemarks.html
2220 auto Remark = [&](OptimizationRemarkAnalysis ORA) {
2221 return ORA << "Potentially unknown OpenMP target region caller.";
2222 };
2223 emitRemark<OptimizationRemarkAnalysis>(F: &F, RemarkName: "OMP100", RemarkCB&: Remark);
2224
2225 return nullptr;
2226 }
2227 }
2228
2229 auto GetUniqueKernelForUse = [&](const Use &U) -> Kernel {
2230 if (auto *Cmp = dyn_cast<ICmpInst>(Val: U.getUser())) {
2231 // Allow use in equality comparisons.
2232 if (Cmp->isEquality())
2233 return getUniqueKernelFor(I&: *Cmp);
2234 return nullptr;
2235 }
2236 if (auto *CB = dyn_cast<CallBase>(Val: U.getUser())) {
2237 // Allow direct calls.
2238 if (CB->isCallee(U: &U))
2239 return getUniqueKernelFor(I&: *CB);
2240
2241 OMPInformationCache::RuntimeFunctionInfo &KernelParallelRFI =
2242 OMPInfoCache.RFIs[OMPRTL___kmpc_parallel_60];
2243 // Allow the use in __kmpc_parallel_60 calls.
2244 if (OpenMPOpt::getCallIfRegularCall(V&: *U.getUser(), RFI: &KernelParallelRFI))
2245 return getUniqueKernelFor(I&: *CB);
2246 return nullptr;
2247 }
2248 // Disallow every other use.
2249 return nullptr;
2250 };
2251
2252 // TODO: In the future we want to track more than just a unique kernel.
2253 SmallPtrSet<Kernel, 2> PotentialKernels;
2254 OMPInformationCache::foreachUse(F, CB: [&](const Use &U) {
2255 PotentialKernels.insert(Ptr: GetUniqueKernelForUse(U));
2256 });
2257
2258 Kernel K = nullptr;
2259 if (PotentialKernels.size() == 1)
2260 K = *PotentialKernels.begin();
2261
2262 // Cache the result.
2263 UniqueKernelMap[&F] = K;
2264
2265 return K;
2266}
2267
2268bool OpenMPOpt::rewriteDeviceCodeStateMachine() {
2269 OMPInformationCache::RuntimeFunctionInfo &KernelParallelRFI =
2270 OMPInfoCache.RFIs[OMPRTL___kmpc_parallel_60];
2271
2272 bool Changed = false;
2273 if (!KernelParallelRFI)
2274 return Changed;
2275
2276 // If we have disabled state machine changes, exit
2277 if (DisableOpenMPOptStateMachineRewrite)
2278 return Changed;
2279
2280 for (Function *F : SCC) {
2281
2282 // Check if the function is a use in a __kmpc_parallel_60 call at
2283 // all.
2284 bool UnknownUse = false;
2285 bool KernelParallelUse = false;
2286 unsigned NumDirectCalls = 0;
2287
2288 SmallVector<Use *, 2> ToBeReplacedStateMachineUses;
2289 OMPInformationCache::foreachUse(F&: *F, CB: [&](Use &U) {
2290 if (auto *CB = dyn_cast<CallBase>(Val: U.getUser()))
2291 if (CB->isCallee(U: &U)) {
2292 ++NumDirectCalls;
2293 return;
2294 }
2295
2296 if (isa<ICmpInst>(Val: U.getUser())) {
2297 ToBeReplacedStateMachineUses.push_back(Elt: &U);
2298 return;
2299 }
2300
2301 // Find wrapper functions that represent parallel kernels.
2302 CallInst *CI =
2303 OpenMPOpt::getCallIfRegularCall(V&: *U.getUser(), RFI: &KernelParallelRFI);
2304 const unsigned int WrapperFunctionArgNo = 6;
2305 if (!KernelParallelUse && CI &&
2306 CI->getArgOperandNo(U: &U) == WrapperFunctionArgNo) {
2307 KernelParallelUse = true;
2308 ToBeReplacedStateMachineUses.push_back(Elt: &U);
2309 return;
2310 }
2311 UnknownUse = true;
2312 });
2313
2314 // Do not emit a remark if we haven't seen a __kmpc_parallel_60
2315 // use.
2316 if (!KernelParallelUse)
2317 continue;
2318
2319 // If this ever hits, we should investigate.
2320 // TODO: Checking the number of uses is not a necessary restriction and
2321 // should be lifted.
2322 if (UnknownUse || NumDirectCalls != 1 ||
2323 ToBeReplacedStateMachineUses.size() > 2) {
2324 auto Remark = [&](OptimizationRemarkAnalysis ORA) {
2325 return ORA << "Parallel region is used in "
2326 << (UnknownUse ? "unknown" : "unexpected")
2327 << " ways. Will not attempt to rewrite the state machine.";
2328 };
2329 emitRemark<OptimizationRemarkAnalysis>(F, RemarkName: "OMP101", RemarkCB&: Remark);
2330 continue;
2331 }
2332
2333 // Even if we have __kmpc_parallel_60 calls, we (for now) give
2334 // up if the function is not called from a unique kernel.
2335 Kernel K = getUniqueKernelFor(F&: *F);
2336 if (!K) {
2337 auto Remark = [&](OptimizationRemarkAnalysis ORA) {
2338 return ORA << "Parallel region is not called from a unique kernel. "
2339 "Will not attempt to rewrite the state machine.";
2340 };
2341 emitRemark<OptimizationRemarkAnalysis>(F, RemarkName: "OMP102", RemarkCB&: Remark);
2342 continue;
2343 }
2344
2345 // We now know F is a parallel body function called only from the kernel K.
2346 // We also identified the state machine uses in which we replace the
2347 // function pointer by a new global symbol for identification purposes. This
2348 // ensures only direct calls to the function are left.
2349
2350 Module &M = *F->getParent();
2351 Type *Int8Ty = Type::getInt8Ty(C&: M.getContext());
2352
2353 auto *ID = new GlobalVariable(
2354 M, Int8Ty, /* isConstant */ true, GlobalValue::PrivateLinkage,
2355 UndefValue::get(T: Int8Ty), F->getName() + ".ID");
2356
2357 for (Use *U : ToBeReplacedStateMachineUses)
2358 U->set(ConstantExpr::getPointerBitCastOrAddrSpaceCast(
2359 C: ID, Ty: U->get()->getType()));
2360
2361 ++NumOpenMPParallelRegionsReplacedInGPUStateMachine;
2362
2363 Changed = true;
2364 }
2365
2366 return Changed;
2367}
2368
2369bool OpenMPOpt::removeSPMDParallelWrappers() {
2370 // Nothing to clean up unless we SPMD-ized at least one kernel.
2371 if (OMPInfoCache.SPMDizedKernels.empty())
2372 return false;
2373
2374 OMPInformationCache::RuntimeFunctionInfo &KernelParallelRFI =
2375 OMPInfoCache.RFIs[OMPRTL___kmpc_parallel_60];
2376 if (!KernelParallelRFI || !KernelParallelRFI.Declaration)
2377 return false;
2378
2379 constexpr unsigned WrapperFunctionArgNo = 6;
2380 bool Changed = false;
2381 for (User *U : KernelParallelRFI.Declaration->users()) {
2382 auto *CI = dyn_cast<CallInst>(Val: U);
2383 if (!CI || CI->getCalledOperand() != KernelParallelRFI.Declaration ||
2384 CI->arg_size() <= WrapperFunctionArgNo)
2385 continue;
2386
2387 Value *Wrapper = CI->getArgOperand(i: WrapperFunctionArgNo);
2388 if (isa<ConstantPointerNull>(Val: Wrapper))
2389 continue;
2390
2391 // Only drop the wrapper for a parallel region reached from a single kernel
2392 // that we transformed to SPMD mode. A region also reachable from a
2393 // generic-mode kernel still needs its wrapper for that kernel's state
2394 // machine, and getUniqueKernelFor conservatively bails on such shared
2395 // regions. (Mirrors the unique-kernel requirement in
2396 // rewriteDeviceCodeStateMachine.)
2397 Kernel K = getUniqueKernelFor(F&: *CI->getFunction());
2398 if (!K || !OMPInfoCache.SPMDizedKernels.contains(Ptr: K))
2399 continue;
2400
2401 CI->setArgOperand(
2402 i: WrapperFunctionArgNo,
2403 v: ConstantPointerNull::get(T: cast<PointerType>(Val: Wrapper->getType())));
2404 Changed = true;
2405 }
2406
2407 return Changed;
2408}
2409
2410/// Abstract Attribute for tracking ICV values.
2411struct AAICVTracker : public StateWrapper<BooleanState, AbstractAttribute> {
2412 using Base = StateWrapper<BooleanState, AbstractAttribute>;
2413 AAICVTracker(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
2414
2415 /// Returns true if value is assumed to be tracked.
2416 bool isAssumedTracked() const { return getAssumed(); }
2417
2418 /// Returns true if value is known to be tracked.
2419 bool isKnownTracked() const { return getAssumed(); }
2420
2421 /// Create an abstract attribute biew for the position \p IRP.
2422 static AAICVTracker &createForPosition(const IRPosition &IRP, Attributor &A);
2423
2424 /// Return the value with which \p I can be replaced for specific \p ICV.
2425 virtual std::optional<Value *> getReplacementValue(InternalControlVar ICV,
2426 const Instruction *I,
2427 Attributor &A) const {
2428 return std::nullopt;
2429 }
2430
2431 /// Return an assumed unique ICV value if a single candidate is found. If
2432 /// there cannot be one, return a nullptr. If it is not clear yet, return
2433 /// std::nullopt.
2434 virtual std::optional<Value *>
2435 getUniqueReplacementValue(InternalControlVar ICV) const = 0;
2436
2437 // Currently only nthreads is being tracked.
2438 // this array will only grow with time.
2439 InternalControlVar TrackableICVs[1] = {ICV_nthreads};
2440
2441 /// See AbstractAttribute::getName()
2442 StringRef getName() const override { return "AAICVTracker"; }
2443
2444 /// See AbstractAttribute::getIdAddr()
2445 const char *getIdAddr() const override { return &ID; }
2446
2447 /// This function should return true if the type of the \p AA is AAICVTracker
2448 static bool classof(const AbstractAttribute *AA) {
2449 return (AA->getIdAddr() == &ID);
2450 }
2451
2452 static const char ID;
2453};
2454
2455struct AAICVTrackerFunction : public AAICVTracker {
2456 AAICVTrackerFunction(const IRPosition &IRP, Attributor &A)
2457 : AAICVTracker(IRP, A) {}
2458
2459 // FIXME: come up with better string.
2460 const std::string getAsStr(Attributor *) const override {
2461 return "ICVTrackerFunction";
2462 }
2463
2464 // FIXME: come up with some stats.
2465 void trackStatistics() const override {}
2466
2467 /// We don't manifest anything for this AA.
2468 ChangeStatus manifest(Attributor &A) override {
2469 return ChangeStatus::UNCHANGED;
2470 }
2471
2472 // Map of ICV to their values at specific program point.
2473 EnumeratedArray<DenseMap<Instruction *, Value *>, InternalControlVar,
2474 InternalControlVar::ICV___last>
2475 ICVReplacementValuesMap;
2476
2477 ChangeStatus updateImpl(Attributor &A) override {
2478 ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
2479
2480 Function *F = getAnchorScope();
2481
2482 auto &OMPInfoCache = static_cast<OMPInformationCache &>(A.getInfoCache());
2483
2484 for (InternalControlVar ICV : TrackableICVs) {
2485 auto &SetterRFI = OMPInfoCache.RFIs[OMPInfoCache.ICVs[ICV].Setter];
2486
2487 auto &ValuesMap = ICVReplacementValuesMap[ICV];
2488 auto TrackValues = [&](Use &U, Function &) {
2489 CallInst *CI = OpenMPOpt::getCallIfRegularCall(U);
2490 if (!CI)
2491 return false;
2492
2493 // FIXME: handle setters with more that 1 arguments.
2494 /// Track new value.
2495 if (ValuesMap.insert(KV: std::make_pair(x&: CI, y: CI->getArgOperand(i: 0))).second)
2496 HasChanged = ChangeStatus::CHANGED;
2497
2498 return false;
2499 };
2500
2501 auto CallCheck = [&](Instruction &I) {
2502 std::optional<Value *> ReplVal = getValueForCall(A, I, ICV);
2503 if (ReplVal && ValuesMap.insert(KV: std::make_pair(x: &I, y&: *ReplVal)).second)
2504 HasChanged = ChangeStatus::CHANGED;
2505
2506 return true;
2507 };
2508
2509 // Track all changes of an ICV.
2510 SetterRFI.foreachUse(CB: TrackValues, F);
2511
2512 bool UsedAssumedInformation = false;
2513 A.checkForAllInstructions(Pred: CallCheck, QueryingAA: *this, Opcodes: {Instruction::Call},
2514 UsedAssumedInformation,
2515 /* CheckBBLivenessOnly */ true);
2516
2517 /// TODO: Figure out a way to avoid adding entry in
2518 /// ICVReplacementValuesMap
2519 Instruction *Entry = &F->getEntryBlock().front();
2520 if (HasChanged == ChangeStatus::CHANGED)
2521 ValuesMap.try_emplace(Key: Entry);
2522 }
2523
2524 return HasChanged;
2525 }
2526
2527 /// Helper to check if \p I is a call and get the value for it if it is
2528 /// unique.
2529 std::optional<Value *> getValueForCall(Attributor &A, const Instruction &I,
2530 InternalControlVar &ICV) const {
2531
2532 const auto *CB = dyn_cast<CallBase>(Val: &I);
2533 if (!CB || CB->hasFnAttr(Kind: "no_openmp") ||
2534 CB->hasFnAttr(Kind: "no_openmp_routines") ||
2535 CB->hasFnAttr(Kind: "no_openmp_constructs"))
2536 return std::nullopt;
2537
2538 auto &OMPInfoCache = static_cast<OMPInformationCache &>(A.getInfoCache());
2539 auto &GetterRFI = OMPInfoCache.RFIs[OMPInfoCache.ICVs[ICV].Getter];
2540 auto &SetterRFI = OMPInfoCache.RFIs[OMPInfoCache.ICVs[ICV].Setter];
2541 Function *CalledFunction = CB->getCalledFunction();
2542
2543 // Indirect call, assume ICV changes.
2544 if (CalledFunction == nullptr)
2545 return nullptr;
2546 if (CalledFunction == GetterRFI.Declaration)
2547 return std::nullopt;
2548 if (CalledFunction == SetterRFI.Declaration) {
2549 if (ICVReplacementValuesMap[ICV].count(Val: &I))
2550 return ICVReplacementValuesMap[ICV].lookup(Val: &I);
2551
2552 return nullptr;
2553 }
2554
2555 // Since we don't know, assume it changes the ICV.
2556 if (CalledFunction->isDeclaration())
2557 return nullptr;
2558
2559 const auto *ICVTrackingAA = A.getAAFor<AAICVTracker>(
2560 QueryingAA: *this, IRP: IRPosition::callsite_returned(CB: *CB), DepClass: DepClassTy::REQUIRED);
2561
2562 if (ICVTrackingAA->isAssumedTracked()) {
2563 std::optional<Value *> URV =
2564 ICVTrackingAA->getUniqueReplacementValue(ICV);
2565 if (!URV || (*URV && AA::isValidAtPosition(VAC: AA::ValueAndContext(**URV, I),
2566 InfoCache&: OMPInfoCache)))
2567 return URV;
2568 }
2569
2570 // If we don't know, assume it changes.
2571 return nullptr;
2572 }
2573
2574 // We don't check unique value for a function, so return std::nullopt.
2575 std::optional<Value *>
2576 getUniqueReplacementValue(InternalControlVar ICV) const override {
2577 return std::nullopt;
2578 }
2579
2580 /// Return the value with which \p I can be replaced for specific \p ICV.
2581 std::optional<Value *> getReplacementValue(InternalControlVar ICV,
2582 const Instruction *I,
2583 Attributor &A) const override {
2584 const auto &ValuesMap = ICVReplacementValuesMap[ICV];
2585 if (ValuesMap.count(Val: I))
2586 return ValuesMap.lookup(Val: I);
2587
2588 SmallVector<const Instruction *, 16> Worklist;
2589 SmallPtrSet<const Instruction *, 16> Visited;
2590 Worklist.push_back(Elt: I);
2591
2592 std::optional<Value *> ReplVal;
2593
2594 while (!Worklist.empty()) {
2595 const Instruction *CurrInst = Worklist.pop_back_val();
2596 if (!Visited.insert(Ptr: CurrInst).second)
2597 continue;
2598
2599 const BasicBlock *CurrBB = CurrInst->getParent();
2600
2601 // Go up and look for all potential setters/calls that might change the
2602 // ICV.
2603 while ((CurrInst = CurrInst->getPrevNode())) {
2604 if (ValuesMap.count(Val: CurrInst)) {
2605 std::optional<Value *> NewReplVal = ValuesMap.lookup(Val: CurrInst);
2606 // Unknown value, track new.
2607 if (!ReplVal) {
2608 ReplVal = NewReplVal;
2609 break;
2610 }
2611
2612 // If we found a new value, we can't know the icv value anymore.
2613 if (NewReplVal)
2614 if (ReplVal != NewReplVal)
2615 return nullptr;
2616
2617 break;
2618 }
2619
2620 std::optional<Value *> NewReplVal = getValueForCall(A, I: *CurrInst, ICV);
2621 if (!NewReplVal)
2622 continue;
2623
2624 // Unknown value, track new.
2625 if (!ReplVal) {
2626 ReplVal = NewReplVal;
2627 break;
2628 }
2629
2630 // if (NewReplVal.hasValue())
2631 // We found a new value, we can't know the icv value anymore.
2632 if (ReplVal != NewReplVal)
2633 return nullptr;
2634 }
2635
2636 // If we are in the same BB and we have a value, we are done.
2637 if (CurrBB == I->getParent() && ReplVal)
2638 return ReplVal;
2639
2640 // Go through all predecessors and add terminators for analysis.
2641 for (const BasicBlock *Pred : predecessors(BB: CurrBB))
2642 Worklist.push_back(Elt: Pred->getTerminator());
2643 }
2644
2645 return ReplVal;
2646 }
2647};
2648
2649struct AAICVTrackerFunctionReturned : AAICVTracker {
2650 AAICVTrackerFunctionReturned(const IRPosition &IRP, Attributor &A)
2651 : AAICVTracker(IRP, A) {}
2652
2653 // FIXME: come up with better string.
2654 const std::string getAsStr(Attributor *) const override {
2655 return "ICVTrackerFunctionReturned";
2656 }
2657
2658 // FIXME: come up with some stats.
2659 void trackStatistics() const override {}
2660
2661 /// We don't manifest anything for this AA.
2662 ChangeStatus manifest(Attributor &A) override {
2663 return ChangeStatus::UNCHANGED;
2664 }
2665
2666 // Map of ICV to their values at specific program point.
2667 EnumeratedArray<std::optional<Value *>, InternalControlVar,
2668 InternalControlVar::ICV___last>
2669 ICVReplacementValuesMap;
2670
2671 /// Return the value with which \p I can be replaced for specific \p ICV.
2672 std::optional<Value *>
2673 getUniqueReplacementValue(InternalControlVar ICV) const override {
2674 return ICVReplacementValuesMap[ICV];
2675 }
2676
2677 ChangeStatus updateImpl(Attributor &A) override {
2678 ChangeStatus Changed = ChangeStatus::UNCHANGED;
2679 const auto *ICVTrackingAA = A.getAAFor<AAICVTracker>(
2680 QueryingAA: *this, IRP: IRPosition::function(F: *getAnchorScope()), DepClass: DepClassTy::REQUIRED);
2681
2682 if (!ICVTrackingAA->isAssumedTracked())
2683 return indicatePessimisticFixpoint();
2684
2685 for (InternalControlVar ICV : TrackableICVs) {
2686 std::optional<Value *> &ReplVal = ICVReplacementValuesMap[ICV];
2687 std::optional<Value *> UniqueICVValue;
2688
2689 auto CheckReturnInst = [&](Instruction &I) {
2690 std::optional<Value *> NewReplVal =
2691 ICVTrackingAA->getReplacementValue(ICV, I: &I, A);
2692
2693 // If we found a second ICV value there is no unique returned value.
2694 if (UniqueICVValue && UniqueICVValue != NewReplVal)
2695 return false;
2696
2697 UniqueICVValue = NewReplVal;
2698
2699 return true;
2700 };
2701
2702 bool UsedAssumedInformation = false;
2703 if (!A.checkForAllInstructions(Pred: CheckReturnInst, QueryingAA: *this, Opcodes: {Instruction::Ret},
2704 UsedAssumedInformation,
2705 /* CheckBBLivenessOnly */ true))
2706 UniqueICVValue = nullptr;
2707
2708 if (UniqueICVValue == ReplVal)
2709 continue;
2710
2711 ReplVal = UniqueICVValue;
2712 Changed = ChangeStatus::CHANGED;
2713 }
2714
2715 return Changed;
2716 }
2717};
2718
2719struct AAICVTrackerCallSite : AAICVTracker {
2720 AAICVTrackerCallSite(const IRPosition &IRP, Attributor &A)
2721 : AAICVTracker(IRP, A) {}
2722
2723 void initialize(Attributor &A) override {
2724 assert(getAnchorScope() && "Expected anchor function");
2725
2726 // We only initialize this AA for getters, so we need to know which ICV it
2727 // gets.
2728 auto &OMPInfoCache = static_cast<OMPInformationCache &>(A.getInfoCache());
2729 for (InternalControlVar ICV : TrackableICVs) {
2730 auto ICVInfo = OMPInfoCache.ICVs[ICV];
2731 auto &Getter = OMPInfoCache.RFIs[ICVInfo.Getter];
2732 if (Getter.Declaration == getAssociatedFunction()) {
2733 AssociatedICV = ICVInfo.Kind;
2734 return;
2735 }
2736 }
2737
2738 /// Unknown ICV.
2739 indicatePessimisticFixpoint();
2740 }
2741
2742 ChangeStatus manifest(Attributor &A) override {
2743 if (!ReplVal || !*ReplVal)
2744 return ChangeStatus::UNCHANGED;
2745
2746 A.changeAfterManifest(IRP: IRPosition::inst(I: *getCtxI()), NV&: **ReplVal);
2747 A.deleteAfterManifest(I&: *getCtxI());
2748
2749 return ChangeStatus::CHANGED;
2750 }
2751
2752 // FIXME: come up with better string.
2753 const std::string getAsStr(Attributor *) const override {
2754 return "ICVTrackerCallSite";
2755 }
2756
2757 // FIXME: come up with some stats.
2758 void trackStatistics() const override {}
2759
2760 InternalControlVar AssociatedICV;
2761 std::optional<Value *> ReplVal;
2762
2763 ChangeStatus updateImpl(Attributor &A) override {
2764 const auto *ICVTrackingAA = A.getAAFor<AAICVTracker>(
2765 QueryingAA: *this, IRP: IRPosition::function(F: *getAnchorScope()), DepClass: DepClassTy::REQUIRED);
2766
2767 // We don't have any information, so we assume it changes the ICV.
2768 if (!ICVTrackingAA->isAssumedTracked())
2769 return indicatePessimisticFixpoint();
2770
2771 std::optional<Value *> NewReplVal =
2772 ICVTrackingAA->getReplacementValue(ICV: AssociatedICV, I: getCtxI(), A);
2773
2774 if (ReplVal == NewReplVal)
2775 return ChangeStatus::UNCHANGED;
2776
2777 ReplVal = NewReplVal;
2778 return ChangeStatus::CHANGED;
2779 }
2780
2781 // Return the value with which associated value can be replaced for specific
2782 // \p ICV.
2783 std::optional<Value *>
2784 getUniqueReplacementValue(InternalControlVar ICV) const override {
2785 return ReplVal;
2786 }
2787};
2788
2789struct AAICVTrackerCallSiteReturned : AAICVTracker {
2790 AAICVTrackerCallSiteReturned(const IRPosition &IRP, Attributor &A)
2791 : AAICVTracker(IRP, A) {}
2792
2793 // FIXME: come up with better string.
2794 const std::string getAsStr(Attributor *) const override {
2795 return "ICVTrackerCallSiteReturned";
2796 }
2797
2798 // FIXME: come up with some stats.
2799 void trackStatistics() const override {}
2800
2801 /// We don't manifest anything for this AA.
2802 ChangeStatus manifest(Attributor &A) override {
2803 return ChangeStatus::UNCHANGED;
2804 }
2805
2806 // Map of ICV to their values at specific program point.
2807 EnumeratedArray<std::optional<Value *>, InternalControlVar,
2808 InternalControlVar::ICV___last>
2809 ICVReplacementValuesMap;
2810
2811 /// Return the value with which associated value can be replaced for specific
2812 /// \p ICV.
2813 std::optional<Value *>
2814 getUniqueReplacementValue(InternalControlVar ICV) const override {
2815 return ICVReplacementValuesMap[ICV];
2816 }
2817
2818 ChangeStatus updateImpl(Attributor &A) override {
2819 ChangeStatus Changed = ChangeStatus::UNCHANGED;
2820 const auto *ICVTrackingAA = A.getAAFor<AAICVTracker>(
2821 QueryingAA: *this, IRP: IRPosition::returned(F: *getAssociatedFunction()),
2822 DepClass: DepClassTy::REQUIRED);
2823
2824 // We don't have any information, so we assume it changes the ICV.
2825 if (!ICVTrackingAA->isAssumedTracked())
2826 return indicatePessimisticFixpoint();
2827
2828 for (InternalControlVar ICV : TrackableICVs) {
2829 std::optional<Value *> &ReplVal = ICVReplacementValuesMap[ICV];
2830 std::optional<Value *> NewReplVal =
2831 ICVTrackingAA->getUniqueReplacementValue(ICV);
2832
2833 if (ReplVal == NewReplVal)
2834 continue;
2835
2836 ReplVal = NewReplVal;
2837 Changed = ChangeStatus::CHANGED;
2838 }
2839 return Changed;
2840 }
2841};
2842
2843/// Determines if \p BB exits the function unconditionally itself or reaches a
2844/// block that does through only unique successors.
2845static bool hasFunctionEndAsUniqueSuccessor(const BasicBlock *BB) {
2846 if (succ_empty(BB))
2847 return true;
2848 const BasicBlock *const Successor = BB->getUniqueSuccessor();
2849 if (!Successor)
2850 return false;
2851 return hasFunctionEndAsUniqueSuccessor(BB: Successor);
2852}
2853
2854struct AAExecutionDomainFunction : public AAExecutionDomain {
2855 AAExecutionDomainFunction(const IRPosition &IRP, Attributor &A)
2856 : AAExecutionDomain(IRP, A) {}
2857
2858 ~AAExecutionDomainFunction() override { delete RPOT; }
2859
2860 void initialize(Attributor &A) override {
2861 Function *F = getAnchorScope();
2862 assert(F && "Expected anchor function");
2863 RPOT = new ReversePostOrderTraversal<Function *>(F);
2864 }
2865
2866 const std::string getAsStr(Attributor *) const override {
2867 unsigned TotalBlocks = 0, InitialThreadBlocks = 0, AlignedBlocks = 0;
2868 for (auto &It : BEDMap) {
2869 if (!It.getFirst())
2870 continue;
2871 TotalBlocks++;
2872 InitialThreadBlocks += It.getSecond().IsExecutedByInitialThreadOnly;
2873 AlignedBlocks += It.getSecond().IsReachedFromAlignedBarrierOnly &&
2874 It.getSecond().IsReachingAlignedBarrierOnly;
2875 }
2876 return "[AAExecutionDomain] " + std::to_string(val: InitialThreadBlocks) + "/" +
2877 std::to_string(val: AlignedBlocks) + " of " +
2878 std::to_string(val: TotalBlocks) +
2879 " executed by initial thread / aligned";
2880 }
2881
2882 /// See AbstractAttribute::trackStatistics().
2883 void trackStatistics() const override {}
2884
2885 ChangeStatus manifest(Attributor &A) override {
2886 LLVM_DEBUG({
2887 for (const BasicBlock &BB : *getAnchorScope()) {
2888 if (!isExecutedByInitialThreadOnly(BB))
2889 continue;
2890 dbgs() << TAG << " Basic block @" << getAnchorScope()->getName() << " "
2891 << BB.getName() << " is executed by a single thread.\n";
2892 }
2893 });
2894
2895 ChangeStatus Changed = ChangeStatus::UNCHANGED;
2896
2897 if (DisableOpenMPOptBarrierElimination)
2898 return Changed;
2899
2900 SmallPtrSet<CallBase *, 16> DeletedBarriers;
2901 auto HandleAlignedBarrier = [&](CallBase *CB) {
2902 const ExecutionDomainTy &ED = CB ? CEDMap[{CB, PRE}] : BEDMap[nullptr];
2903 if (!ED.IsReachedFromAlignedBarrierOnly ||
2904 ED.EncounteredNonLocalSideEffect)
2905 return;
2906 if (!ED.EncounteredAssumes.empty() && !A.isModulePass())
2907 return;
2908
2909 // We can remove this barrier, if it is one, or aligned barriers reaching
2910 // the kernel end (if CB is nullptr). Aligned barriers reaching the kernel
2911 // end should only be removed if the kernel end is their unique successor;
2912 // otherwise, they may have side-effects that aren't accounted for in the
2913 // kernel end in their other successors. If those barriers have other
2914 // barriers reaching them, those can be transitively removed as well as
2915 // long as the kernel end is also their unique successor.
2916 if (CB) {
2917 DeletedBarriers.insert(Ptr: CB);
2918 A.deleteAfterManifest(I&: *CB);
2919 ++NumBarriersEliminated;
2920 Changed = ChangeStatus::CHANGED;
2921 } else if (!ED.AlignedBarriers.empty()) {
2922 Changed = ChangeStatus::CHANGED;
2923 SmallVector<CallBase *> Worklist(ED.AlignedBarriers.begin(),
2924 ED.AlignedBarriers.end());
2925 SmallSetVector<CallBase *, 16> Visited;
2926 while (!Worklist.empty()) {
2927 CallBase *LastCB = Worklist.pop_back_val();
2928 if (!Visited.insert(X: LastCB))
2929 continue;
2930 if (LastCB->getFunction() != getAnchorScope())
2931 continue;
2932 if (!hasFunctionEndAsUniqueSuccessor(BB: LastCB->getParent()))
2933 continue;
2934 if (!DeletedBarriers.count(Ptr: LastCB)) {
2935 ++NumBarriersEliminated;
2936 A.deleteAfterManifest(I&: *LastCB);
2937 continue;
2938 }
2939 // The final aligned barrier (LastCB) reaching the kernel end was
2940 // removed already. This means we can go one step further and remove
2941 // the barriers encoutered last before (LastCB).
2942 const ExecutionDomainTy &LastED = CEDMap[{LastCB, PRE}];
2943 Worklist.append(in_start: LastED.AlignedBarriers.begin(),
2944 in_end: LastED.AlignedBarriers.end());
2945 }
2946 }
2947
2948 // If we actually eliminated a barrier we need to eliminate the associated
2949 // llvm.assumes as well to avoid creating UB.
2950 if (!ED.EncounteredAssumes.empty() && (CB || !ED.AlignedBarriers.empty()))
2951 for (auto *AssumeCB : ED.EncounteredAssumes)
2952 A.deleteAfterManifest(I&: *AssumeCB);
2953 };
2954
2955 for (auto *CB : AlignedBarriers)
2956 HandleAlignedBarrier(CB);
2957
2958 // Handle the "kernel end barrier" for kernels too.
2959 if (omp::isOpenMPKernel(Fn&: *getAnchorScope()))
2960 HandleAlignedBarrier(nullptr);
2961
2962 return Changed;
2963 }
2964
2965 bool isNoOpFence(const FenceInst &FI) const override {
2966 return getState().isValidState() && !NonNoOpFences.count(Ptr: &FI);
2967 }
2968
2969 /// Merge barrier and assumption information from \p PredED into the successor
2970 /// \p ED.
2971 void
2972 mergeInPredecessorBarriersAndAssumptions(Attributor &A, ExecutionDomainTy &ED,
2973 const ExecutionDomainTy &PredED);
2974
2975 /// Merge all information from \p PredED into the successor \p ED. If
2976 /// \p InitialEdgeOnly is set, only the initial edge will enter the block
2977 /// represented by \p ED from this predecessor.
2978 bool mergeInPredecessor(Attributor &A, ExecutionDomainTy &ED,
2979 const ExecutionDomainTy &PredED,
2980 bool InitialEdgeOnly = false);
2981
2982 /// Accumulate information for the entry block in \p EntryBBED.
2983 bool handleCallees(Attributor &A, ExecutionDomainTy &EntryBBED);
2984
2985 /// See AbstractAttribute::updateImpl.
2986 ChangeStatus updateImpl(Attributor &A) override;
2987
2988 /// Query interface, see AAExecutionDomain
2989 ///{
2990 bool isExecutedByInitialThreadOnly(const BasicBlock &BB) const override {
2991 if (!isValidState())
2992 return false;
2993 assert(BB.getParent() == getAnchorScope() && "Block is out of scope!");
2994 return BEDMap.lookup(Val: &BB).IsExecutedByInitialThreadOnly;
2995 }
2996
2997 bool isExecutedInAlignedRegion(Attributor &A,
2998 const Instruction &I) const override {
2999 assert(I.getFunction() == getAnchorScope() &&
3000 "Instruction is out of scope!");
3001 if (!isValidState())
3002 return false;
3003
3004 bool ForwardIsOk = true;
3005 const Instruction *CurI;
3006
3007 // Check forward until a call or the block end is reached.
3008 CurI = &I;
3009 do {
3010 auto *CB = dyn_cast<CallBase>(Val: CurI);
3011 if (!CB)
3012 continue;
3013 if (CB != &I && AlignedBarriers.contains(key: const_cast<CallBase *>(CB)))
3014 return true;
3015 const auto &It = CEDMap.find(Val: {CB, PRE});
3016 if (It == CEDMap.end())
3017 continue;
3018 if (!It->getSecond().IsReachingAlignedBarrierOnly)
3019 ForwardIsOk = false;
3020 break;
3021 } while ((CurI = CurI->getNextNode()));
3022
3023 if (!CurI && !BEDMap.lookup(Val: I.getParent()).IsReachingAlignedBarrierOnly)
3024 ForwardIsOk = false;
3025
3026 // Check backward until a call or the block beginning is reached.
3027 CurI = &I;
3028 do {
3029 auto *CB = dyn_cast<CallBase>(Val: CurI);
3030 if (!CB)
3031 continue;
3032 if (CB != &I && AlignedBarriers.contains(key: const_cast<CallBase *>(CB)))
3033 return true;
3034 const auto &It = CEDMap.find(Val: {CB, POST});
3035 if (It == CEDMap.end())
3036 continue;
3037 if (It->getSecond().IsReachedFromAlignedBarrierOnly)
3038 break;
3039 return false;
3040 } while ((CurI = CurI->getPrevNode()));
3041
3042 // Delayed decision on the forward pass to allow aligned barrier detection
3043 // in the backwards traversal.
3044 if (!ForwardIsOk)
3045 return false;
3046
3047 if (!CurI) {
3048 const BasicBlock *BB = I.getParent();
3049 if (BB == &BB->getParent()->getEntryBlock())
3050 return BEDMap.lookup(Val: nullptr).IsReachedFromAlignedBarrierOnly;
3051 if (!llvm::all_of(Range: predecessors(BB), P: [&](const BasicBlock *PredBB) {
3052 return BEDMap.lookup(Val: PredBB).IsReachedFromAlignedBarrierOnly;
3053 })) {
3054 return false;
3055 }
3056 }
3057
3058 // On neither traversal we found a anything but aligned barriers.
3059 return true;
3060 }
3061
3062 ExecutionDomainTy getExecutionDomain(const BasicBlock &BB) const override {
3063 assert(isValidState() &&
3064 "No request should be made against an invalid state!");
3065 return BEDMap.lookup(Val: &BB);
3066 }
3067 std::pair<ExecutionDomainTy, ExecutionDomainTy>
3068 getExecutionDomain(const CallBase &CB) const override {
3069 assert(isValidState() &&
3070 "No request should be made against an invalid state!");
3071 return {CEDMap.lookup(Val: {&CB, PRE}), CEDMap.lookup(Val: {&CB, POST})};
3072 }
3073 ExecutionDomainTy getFunctionExecutionDomain() const override {
3074 assert(isValidState() &&
3075 "No request should be made against an invalid state!");
3076 return InterProceduralED;
3077 }
3078 ///}
3079
3080 // Check if the edge into the successor block contains a condition that only
3081 // lets the main thread execute it.
3082 static bool isInitialThreadOnlyEdge(Attributor &A, CondBrInst *Edge,
3083 BasicBlock &SuccessorBB) {
3084 if (!Edge)
3085 return false;
3086 if (Edge->getSuccessor(i: 0) != &SuccessorBB)
3087 return false;
3088
3089 auto *Cmp = dyn_cast<CmpInst>(Val: Edge->getCondition());
3090 if (!Cmp || !Cmp->isTrueWhenEqual() || !Cmp->isEquality())
3091 return false;
3092
3093 ConstantInt *C = dyn_cast<ConstantInt>(Val: Cmp->getOperand(i_nocapture: 1));
3094 if (!C)
3095 return false;
3096
3097 // Match: -1 == __kmpc_target_init (for non-SPMD kernels only!)
3098 if (C->isAllOnesValue()) {
3099 auto *CB = dyn_cast<CallBase>(Val: Cmp->getOperand(i_nocapture: 0));
3100 auto &OMPInfoCache = static_cast<OMPInformationCache &>(A.getInfoCache());
3101 auto &RFI = OMPInfoCache.RFIs[OMPRTL___kmpc_target_init];
3102 CB = CB ? OpenMPOpt::getCallIfRegularCall(V&: *CB, RFI: &RFI) : nullptr;
3103 if (!CB)
3104 return false;
3105 ConstantStruct *KernelEnvC =
3106 KernelInfo::getKernelEnvironementFromKernelInitCB(KernelInitCB: CB);
3107 ConstantInt *ExecModeC =
3108 KernelInfo::getExecModeFromKernelEnvironment(KernelEnvC);
3109 return ExecModeC->getSExtValue() & OMP_TGT_EXEC_MODE_GENERIC;
3110 }
3111
3112 if (C->isZero()) {
3113 // Match: 0 == llvm.nvvm.read.ptx.sreg.tid.x()
3114 if (auto *II = dyn_cast<IntrinsicInst>(Val: Cmp->getOperand(i_nocapture: 0)))
3115 if (II->getIntrinsicID() == Intrinsic::nvvm_read_ptx_sreg_tid_x)
3116 return true;
3117
3118 // Match: 0 == llvm.amdgcn.workitem.id.x()
3119 if (auto *II = dyn_cast<IntrinsicInst>(Val: Cmp->getOperand(i_nocapture: 0)))
3120 if (II->getIntrinsicID() == Intrinsic::amdgcn_workitem_id_x)
3121 return true;
3122 }
3123
3124 return false;
3125 };
3126
3127 /// Mapping containing information about the function for other AAs.
3128 ExecutionDomainTy InterProceduralED;
3129
3130 enum Direction { PRE = 0, POST = 1 };
3131 /// Mapping containing information per block.
3132 DenseMap<const BasicBlock *, ExecutionDomainTy> BEDMap;
3133 DenseMap<PointerIntPair<const CallBase *, 1, Direction>, ExecutionDomainTy>
3134 CEDMap;
3135 SmallSetVector<CallBase *, 16> AlignedBarriers;
3136
3137 ReversePostOrderTraversal<Function *> *RPOT = nullptr;
3138
3139 /// Set \p R to \V and report true if that changed \p R.
3140 static bool setAndRecord(bool &R, bool V) {
3141 bool Eq = (R == V);
3142 R = V;
3143 return !Eq;
3144 }
3145
3146 /// Collection of fences known to be non-no-opt. All fences not in this set
3147 /// can be assumed no-opt.
3148 SmallPtrSet<const FenceInst *, 8> NonNoOpFences;
3149};
3150
3151void AAExecutionDomainFunction::mergeInPredecessorBarriersAndAssumptions(
3152 Attributor &A, ExecutionDomainTy &ED, const ExecutionDomainTy &PredED) {
3153 for (auto *EA : PredED.EncounteredAssumes)
3154 ED.addAssumeInst(A, AI&: *EA);
3155
3156 for (auto *AB : PredED.AlignedBarriers)
3157 ED.addAlignedBarrier(A, CB&: *AB);
3158}
3159
3160bool AAExecutionDomainFunction::mergeInPredecessor(
3161 Attributor &A, ExecutionDomainTy &ED, const ExecutionDomainTy &PredED,
3162 bool InitialEdgeOnly) {
3163
3164 bool Changed = false;
3165 Changed |=
3166 setAndRecord(R&: ED.IsExecutedByInitialThreadOnly,
3167 V: InitialEdgeOnly || (PredED.IsExecutedByInitialThreadOnly &&
3168 ED.IsExecutedByInitialThreadOnly));
3169
3170 Changed |= setAndRecord(R&: ED.IsReachedFromAlignedBarrierOnly,
3171 V: ED.IsReachedFromAlignedBarrierOnly &&
3172 PredED.IsReachedFromAlignedBarrierOnly);
3173 Changed |= setAndRecord(R&: ED.EncounteredNonLocalSideEffect,
3174 V: ED.EncounteredNonLocalSideEffect |
3175 PredED.EncounteredNonLocalSideEffect);
3176 // Do not track assumptions and barriers as part of Changed.
3177 if (ED.IsReachedFromAlignedBarrierOnly)
3178 mergeInPredecessorBarriersAndAssumptions(A, ED, PredED);
3179 else
3180 ED.clearAssumeInstAndAlignedBarriers();
3181 return Changed;
3182}
3183
3184bool AAExecutionDomainFunction::handleCallees(Attributor &A,
3185 ExecutionDomainTy &EntryBBED) {
3186 SmallVector<std::pair<ExecutionDomainTy, ExecutionDomainTy>, 4> CallSiteEDs;
3187 auto PredForCallSite = [&](AbstractCallSite ACS) {
3188 const auto *EDAA = A.getAAFor<AAExecutionDomain>(
3189 QueryingAA: *this, IRP: IRPosition::function(F: *ACS.getInstruction()->getFunction()),
3190 DepClass: DepClassTy::OPTIONAL);
3191 if (!EDAA || !EDAA->getState().isValidState())
3192 return false;
3193 CallSiteEDs.emplace_back(
3194 Args: EDAA->getExecutionDomain(CB: *cast<CallBase>(Val: ACS.getInstruction())));
3195 return true;
3196 };
3197
3198 ExecutionDomainTy ExitED;
3199 bool AllCallSitesKnown;
3200 if (A.checkForAllCallSites(Pred: PredForCallSite, QueryingAA: *this,
3201 /* RequiresAllCallSites */ RequireAllCallSites: true,
3202 UsedAssumedInformation&: AllCallSitesKnown)) {
3203 for (const auto &[CSInED, CSOutED] : CallSiteEDs) {
3204 mergeInPredecessor(A, ED&: EntryBBED, PredED: CSInED);
3205 ExitED.IsReachingAlignedBarrierOnly &=
3206 CSOutED.IsReachingAlignedBarrierOnly;
3207 }
3208
3209 } else {
3210 // We could not find all predecessors, so this is either a kernel or a
3211 // function with external linkage (or with some other weird uses).
3212 if (omp::isOpenMPKernel(Fn&: *getAnchorScope())) {
3213 EntryBBED.IsExecutedByInitialThreadOnly = false;
3214 EntryBBED.IsReachedFromAlignedBarrierOnly = true;
3215 EntryBBED.EncounteredNonLocalSideEffect = false;
3216 ExitED.IsReachingAlignedBarrierOnly = false;
3217 } else {
3218 EntryBBED.IsExecutedByInitialThreadOnly = false;
3219 EntryBBED.IsReachedFromAlignedBarrierOnly = false;
3220 EntryBBED.EncounteredNonLocalSideEffect = true;
3221 ExitED.IsReachingAlignedBarrierOnly = false;
3222 }
3223 }
3224
3225 bool Changed = false;
3226 auto &FnED = BEDMap[nullptr];
3227 Changed |= setAndRecord(R&: FnED.IsReachedFromAlignedBarrierOnly,
3228 V: FnED.IsReachedFromAlignedBarrierOnly &
3229 EntryBBED.IsReachedFromAlignedBarrierOnly);
3230 Changed |= setAndRecord(R&: FnED.IsReachingAlignedBarrierOnly,
3231 V: FnED.IsReachingAlignedBarrierOnly &
3232 ExitED.IsReachingAlignedBarrierOnly);
3233 Changed |= setAndRecord(R&: FnED.IsExecutedByInitialThreadOnly,
3234 V: EntryBBED.IsExecutedByInitialThreadOnly);
3235 return Changed;
3236}
3237
3238ChangeStatus AAExecutionDomainFunction::updateImpl(Attributor &A) {
3239
3240 bool Changed = false;
3241
3242 // Helper to deal with an aligned barrier encountered during the forward
3243 // traversal. \p CB is the aligned barrier, \p ED is the execution domain when
3244 // it was encountered.
3245 auto HandleAlignedBarrier = [&](CallBase &CB, ExecutionDomainTy &ED) {
3246 Changed |= AlignedBarriers.insert(X: &CB);
3247 // First, update the barrier ED kept in the separate CEDMap.
3248 auto &CallInED = CEDMap[{&CB, PRE}];
3249 Changed |= mergeInPredecessor(A, ED&: CallInED, PredED: ED);
3250 CallInED.IsReachingAlignedBarrierOnly = true;
3251 // Next adjust the ED we use for the traversal.
3252 ED.EncounteredNonLocalSideEffect = false;
3253 ED.IsReachedFromAlignedBarrierOnly = true;
3254 // Aligned barrier collection has to come last.
3255 ED.clearAssumeInstAndAlignedBarriers();
3256 ED.addAlignedBarrier(A, CB);
3257 auto &CallOutED = CEDMap[{&CB, POST}];
3258 Changed |= mergeInPredecessor(A, ED&: CallOutED, PredED: ED);
3259 };
3260
3261 auto *LivenessAA =
3262 A.getAAFor<AAIsDead>(QueryingAA: *this, IRP: getIRPosition(), DepClass: DepClassTy::OPTIONAL);
3263
3264 Function *F = getAnchorScope();
3265 BasicBlock &EntryBB = F->getEntryBlock();
3266 bool IsKernel = omp::isOpenMPKernel(Fn&: *F);
3267
3268 SmallVector<Instruction *> SyncInstWorklist;
3269 for (auto &RIt : *RPOT) {
3270 BasicBlock &BB = *RIt;
3271
3272 bool IsEntryBB = &BB == &EntryBB;
3273 // TODO: We use local reasoning since we don't have a divergence analysis
3274 // running as well. We could basically allow uniform branches here.
3275 bool AlignedBarrierLastInBlock = IsEntryBB && IsKernel;
3276 bool IsExplicitlyAligned = IsEntryBB && IsKernel;
3277 ExecutionDomainTy ED;
3278 // Propagate "incoming edges" into information about this block.
3279 if (IsEntryBB) {
3280 Changed |= handleCallees(A, EntryBBED&: ED);
3281 } else {
3282 // For live non-entry blocks we only propagate
3283 // information via live edges.
3284 if (LivenessAA && LivenessAA->isAssumedDead(BB: &BB))
3285 continue;
3286
3287 for (auto *PredBB : predecessors(BB: &BB)) {
3288 if (LivenessAA && LivenessAA->isEdgeDead(From: PredBB, To: &BB))
3289 continue;
3290 bool InitialEdgeOnly = isInitialThreadOnlyEdge(
3291 A, Edge: dyn_cast<CondBrInst>(Val: PredBB->getTerminator()), SuccessorBB&: BB);
3292 mergeInPredecessor(A, ED, PredED: BEDMap[PredBB], InitialEdgeOnly);
3293 }
3294 }
3295
3296 // Now we traverse the block, accumulate effects in ED and attach
3297 // information to calls.
3298 for (Instruction &I : BB) {
3299 bool UsedAssumedInformation;
3300 if (A.isAssumedDead(I, QueryingAA: *this, LivenessAA, UsedAssumedInformation,
3301 /* CheckBBLivenessOnly */ false, DepClass: DepClassTy::OPTIONAL,
3302 /* CheckForDeadStore */ true))
3303 continue;
3304
3305 // Asummes and "assume-like" (dbg, lifetime, ...) are handled first, the
3306 // former is collected the latter is ignored.
3307 if (auto *II = dyn_cast<IntrinsicInst>(Val: &I)) {
3308 if (auto *AI = dyn_cast_or_null<AssumeInst>(Val: II)) {
3309 ED.addAssumeInst(A, AI&: *AI);
3310 continue;
3311 }
3312 // TODO: Should we also collect and delete lifetime markers?
3313 if (II->isAssumeLikeIntrinsic())
3314 continue;
3315 }
3316
3317 if (auto *FI = dyn_cast<FenceInst>(Val: &I)) {
3318 if (!ED.EncounteredNonLocalSideEffect) {
3319 // An aligned fence without non-local side-effects is a no-op.
3320 if (ED.IsReachedFromAlignedBarrierOnly)
3321 continue;
3322 // A non-aligned fence without non-local side-effects is a no-op
3323 // if the ordering only publishes non-local side-effects (or less).
3324 switch (FI->getOrdering()) {
3325 case AtomicOrdering::NotAtomic:
3326 continue;
3327 case AtomicOrdering::Unordered:
3328 continue;
3329 case AtomicOrdering::Monotonic:
3330 continue;
3331 case AtomicOrdering::Acquire:
3332 break;
3333 case AtomicOrdering::Release:
3334 continue;
3335 case AtomicOrdering::AcquireRelease:
3336 break;
3337 case AtomicOrdering::SequentiallyConsistent:
3338 break;
3339 };
3340 }
3341 NonNoOpFences.insert(Ptr: FI);
3342 }
3343
3344 auto *CB = dyn_cast<CallBase>(Val: &I);
3345 bool IsNoSync = AA::isNoSyncInst(A, I, QueryingAA: *this);
3346 bool IsAlignedBarrier =
3347 !IsNoSync && CB &&
3348 AANoSync::isAlignedBarrier(CB: *CB, ExecutedAligned: AlignedBarrierLastInBlock);
3349
3350 AlignedBarrierLastInBlock &= IsNoSync;
3351 IsExplicitlyAligned &= IsNoSync;
3352
3353 // Next we check for calls. Aligned barriers are handled
3354 // explicitly, everything else is kept for the backward traversal and will
3355 // also affect our state.
3356 if (CB) {
3357 if (IsAlignedBarrier) {
3358 HandleAlignedBarrier(*CB, ED);
3359 AlignedBarrierLastInBlock = true;
3360 IsExplicitlyAligned = true;
3361 continue;
3362 }
3363
3364 // Check the pointer(s) of a memory intrinsic explicitly.
3365 if (isa<MemIntrinsic>(Val: &I)) {
3366 if (!ED.EncounteredNonLocalSideEffect &&
3367 AA::isPotentiallyAffectedByBarrier(A, I, QueryingAA: *this))
3368 ED.EncounteredNonLocalSideEffect = true;
3369 if (!IsNoSync) {
3370 ED.IsReachedFromAlignedBarrierOnly = false;
3371 SyncInstWorklist.push_back(Elt: &I);
3372 }
3373 continue;
3374 }
3375
3376 // Record how we entered the call, then accumulate the effect of the
3377 // call in ED for potential use by the callee.
3378 auto &CallInED = CEDMap[{CB, PRE}];
3379 Changed |= mergeInPredecessor(A, ED&: CallInED, PredED: ED);
3380
3381 // If we have a sync-definition we can check if it starts/ends in an
3382 // aligned barrier. If we are unsure we assume any sync breaks
3383 // alignment.
3384 Function *Callee = CB->getCalledFunction();
3385 if (!IsNoSync && Callee && !Callee->isDeclaration()) {
3386 const auto *EDAA = A.getAAFor<AAExecutionDomain>(
3387 QueryingAA: *this, IRP: IRPosition::function(F: *Callee), DepClass: DepClassTy::OPTIONAL);
3388 if (EDAA && EDAA->getState().isValidState()) {
3389 const auto &CalleeED = EDAA->getFunctionExecutionDomain();
3390 ED.IsReachedFromAlignedBarrierOnly =
3391 CalleeED.IsReachedFromAlignedBarrierOnly;
3392 AlignedBarrierLastInBlock = ED.IsReachedFromAlignedBarrierOnly;
3393 if (IsNoSync || !CalleeED.IsReachedFromAlignedBarrierOnly)
3394 ED.EncounteredNonLocalSideEffect |=
3395 CalleeED.EncounteredNonLocalSideEffect;
3396 else
3397 ED.EncounteredNonLocalSideEffect =
3398 CalleeED.EncounteredNonLocalSideEffect;
3399 if (!CalleeED.IsReachingAlignedBarrierOnly) {
3400 Changed |=
3401 setAndRecord(R&: CallInED.IsReachingAlignedBarrierOnly, V: false);
3402 SyncInstWorklist.push_back(Elt: &I);
3403 }
3404 if (CalleeED.IsReachedFromAlignedBarrierOnly)
3405 mergeInPredecessorBarriersAndAssumptions(A, ED, PredED: CalleeED);
3406 auto &CallOutED = CEDMap[{CB, POST}];
3407 Changed |= mergeInPredecessor(A, ED&: CallOutED, PredED: ED);
3408 continue;
3409 }
3410 }
3411 if (!IsNoSync) {
3412 ED.IsReachedFromAlignedBarrierOnly = false;
3413 Changed |= setAndRecord(R&: CallInED.IsReachingAlignedBarrierOnly, V: false);
3414 SyncInstWorklist.push_back(Elt: &I);
3415 }
3416 AlignedBarrierLastInBlock &= ED.IsReachedFromAlignedBarrierOnly;
3417 ED.EncounteredNonLocalSideEffect |= !CB->doesNotAccessMemory();
3418 auto &CallOutED = CEDMap[{CB, POST}];
3419 Changed |= mergeInPredecessor(A, ED&: CallOutED, PredED: ED);
3420 }
3421
3422 if (!I.mayHaveSideEffects() && !I.mayReadFromMemory())
3423 continue;
3424
3425 // If we have a callee we try to use fine-grained information to
3426 // determine local side-effects.
3427 if (CB) {
3428 const auto *MemAA = A.getAAFor<AAMemoryLocation>(
3429 QueryingAA: *this, IRP: IRPosition::callsite_function(CB: *CB), DepClass: DepClassTy::OPTIONAL);
3430
3431 auto AccessPred = [&](const Instruction *I, const Value *Ptr,
3432 AAMemoryLocation::AccessKind,
3433 AAMemoryLocation::MemoryLocationsKind) {
3434 return !AA::isPotentiallyAffectedByBarrier(A, Ptrs: {Ptr}, QueryingAA: *this, CtxI: I);
3435 };
3436 if (MemAA && MemAA->getState().isValidState() &&
3437 MemAA->checkForAllAccessesToMemoryKind(
3438 Pred: AccessPred, MLK: AAMemoryLocation::ALL_LOCATIONS))
3439 continue;
3440 }
3441
3442 auto &InfoCache = A.getInfoCache();
3443 if (!I.mayHaveSideEffects() && InfoCache.isOnlyUsedByAssume(I))
3444 continue;
3445
3446 if (auto *LI = dyn_cast<LoadInst>(Val: &I))
3447 if (LI->hasMetadata(KindID: LLVMContext::MD_invariant_load))
3448 continue;
3449
3450 if (!ED.EncounteredNonLocalSideEffect &&
3451 AA::isPotentiallyAffectedByBarrier(A, I, QueryingAA: *this))
3452 ED.EncounteredNonLocalSideEffect = true;
3453 }
3454
3455 bool IsEndAndNotReachingAlignedBarriersOnly = false;
3456 if (!isa<UnreachableInst>(Val: BB.getTerminator()) &&
3457 !BB.getTerminator()->getNumSuccessors()) {
3458
3459 Changed |= mergeInPredecessor(A, ED&: InterProceduralED, PredED: ED);
3460
3461 auto &FnED = BEDMap[nullptr];
3462 if (IsKernel && !IsExplicitlyAligned)
3463 FnED.IsReachingAlignedBarrierOnly = false;
3464 Changed |= mergeInPredecessor(A, ED&: FnED, PredED: ED);
3465
3466 if (!FnED.IsReachingAlignedBarrierOnly) {
3467 IsEndAndNotReachingAlignedBarriersOnly = true;
3468 SyncInstWorklist.push_back(Elt: BB.getTerminator());
3469 auto &BBED = BEDMap[&BB];
3470 Changed |= setAndRecord(R&: BBED.IsReachingAlignedBarrierOnly, V: false);
3471 }
3472 }
3473
3474 ExecutionDomainTy &StoredED = BEDMap[&BB];
3475 ED.IsReachingAlignedBarrierOnly = StoredED.IsReachingAlignedBarrierOnly &&
3476 !IsEndAndNotReachingAlignedBarriersOnly;
3477
3478 // Check if we computed anything different as part of the forward
3479 // traversal. We do not take assumptions and aligned barriers into account
3480 // as they do not influence the state we iterate. Backward traversal values
3481 // are handled later on.
3482 if (ED.IsExecutedByInitialThreadOnly !=
3483 StoredED.IsExecutedByInitialThreadOnly ||
3484 ED.IsReachedFromAlignedBarrierOnly !=
3485 StoredED.IsReachedFromAlignedBarrierOnly ||
3486 ED.EncounteredNonLocalSideEffect !=
3487 StoredED.EncounteredNonLocalSideEffect)
3488 Changed = true;
3489
3490 // Update the state with the new value.
3491 StoredED = std::move(ED);
3492 }
3493
3494 // Propagate (non-aligned) sync instruction effects backwards until the
3495 // entry is hit or an aligned barrier.
3496 SmallSetVector<BasicBlock *, 16> Visited;
3497 while (!SyncInstWorklist.empty()) {
3498 Instruction *SyncInst = SyncInstWorklist.pop_back_val();
3499 Instruction *CurInst = SyncInst;
3500 bool HitAlignedBarrierOrKnownEnd = false;
3501 while ((CurInst = CurInst->getPrevNode())) {
3502 auto *CB = dyn_cast<CallBase>(Val: CurInst);
3503 if (!CB)
3504 continue;
3505 auto &CallOutED = CEDMap[{CB, POST}];
3506 Changed |= setAndRecord(R&: CallOutED.IsReachingAlignedBarrierOnly, V: false);
3507 auto &CallInED = CEDMap[{CB, PRE}];
3508 HitAlignedBarrierOrKnownEnd =
3509 AlignedBarriers.count(key: CB) || !CallInED.IsReachingAlignedBarrierOnly;
3510 if (HitAlignedBarrierOrKnownEnd)
3511 break;
3512 Changed |= setAndRecord(R&: CallInED.IsReachingAlignedBarrierOnly, V: false);
3513 }
3514 if (HitAlignedBarrierOrKnownEnd)
3515 continue;
3516 BasicBlock *SyncBB = SyncInst->getParent();
3517 for (auto *PredBB : predecessors(BB: SyncBB)) {
3518 if (LivenessAA && LivenessAA->isEdgeDead(From: PredBB, To: SyncBB))
3519 continue;
3520 if (!Visited.insert(X: PredBB))
3521 continue;
3522 auto &PredED = BEDMap[PredBB];
3523 if (setAndRecord(R&: PredED.IsReachingAlignedBarrierOnly, V: false)) {
3524 Changed = true;
3525 SyncInstWorklist.push_back(Elt: PredBB->getTerminator());
3526 }
3527 }
3528 if (SyncBB != &EntryBB)
3529 continue;
3530 Changed |=
3531 setAndRecord(R&: InterProceduralED.IsReachingAlignedBarrierOnly, V: false);
3532 }
3533
3534 return Changed ? ChangeStatus::CHANGED : ChangeStatus::UNCHANGED;
3535}
3536
3537/// Try to replace memory allocation calls called by a single thread with a
3538/// static buffer of shared memory.
3539struct AAHeapToShared : public StateWrapper<BooleanState, AbstractAttribute> {
3540 using Base = StateWrapper<BooleanState, AbstractAttribute>;
3541 AAHeapToShared(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
3542
3543 /// Create an abstract attribute view for the position \p IRP.
3544 static AAHeapToShared &createForPosition(const IRPosition &IRP,
3545 Attributor &A);
3546
3547 /// Returns true if HeapToShared conversion is assumed to be possible.
3548 virtual bool isAssumedHeapToShared(CallBase &CB) const = 0;
3549
3550 /// Returns true if HeapToShared conversion is assumed and the CB is a
3551 /// callsite to a free operation to be removed.
3552 virtual bool isAssumedHeapToSharedRemovedFree(CallBase &CB) const = 0;
3553
3554 /// See AbstractAttribute::getName().
3555 StringRef getName() const override { return "AAHeapToShared"; }
3556
3557 /// See AbstractAttribute::getIdAddr().
3558 const char *getIdAddr() const override { return &ID; }
3559
3560 /// This function should return true if the type of the \p AA is
3561 /// AAHeapToShared.
3562 static bool classof(const AbstractAttribute *AA) {
3563 return (AA->getIdAddr() == &ID);
3564 }
3565
3566 /// Unique ID (due to the unique address)
3567 static const char ID;
3568};
3569
3570struct AAHeapToSharedFunction : public AAHeapToShared {
3571 AAHeapToSharedFunction(const IRPosition &IRP, Attributor &A)
3572 : AAHeapToShared(IRP, A) {}
3573
3574 const std::string getAsStr(Attributor *) const override {
3575 return "[AAHeapToShared] " + std::to_string(val: MallocCalls.size()) +
3576 " malloc calls eligible.";
3577 }
3578
3579 /// See AbstractAttribute::trackStatistics().
3580 void trackStatistics() const override {}
3581
3582 /// This functions finds free calls that will be removed by the
3583 /// HeapToShared transformation.
3584 void findPotentialRemovedFreeCalls(Attributor &A) {
3585 auto &OMPInfoCache = static_cast<OMPInformationCache &>(A.getInfoCache());
3586 auto &FreeRFI = OMPInfoCache.RFIs[OMPRTL___kmpc_free_shared];
3587
3588 PotentialRemovedFreeCalls.clear();
3589 // Update free call users of found malloc calls.
3590 for (CallBase *CB : MallocCalls) {
3591 SmallVector<CallBase *, 4> FreeCalls;
3592 for (auto *U : CB->users()) {
3593 CallBase *C = dyn_cast<CallBase>(Val: U);
3594 if (C && C->getCalledFunction() == FreeRFI.Declaration)
3595 FreeCalls.push_back(Elt: C);
3596 }
3597
3598 if (FreeCalls.size() != 1)
3599 continue;
3600
3601 PotentialRemovedFreeCalls.insert(Ptr: FreeCalls.front());
3602 }
3603 }
3604
3605 void initialize(Attributor &A) override {
3606 if (DisableOpenMPOptDeglobalization) {
3607 indicatePessimisticFixpoint();
3608 return;
3609 }
3610
3611 auto &OMPInfoCache = static_cast<OMPInformationCache &>(A.getInfoCache());
3612 auto &RFI = OMPInfoCache.RFIs[OMPRTL___kmpc_alloc_shared];
3613 if (!RFI.Declaration)
3614 return;
3615
3616 Attributor::SimplifictionCallbackTy SCB =
3617 [](const IRPosition &, const AbstractAttribute *,
3618 bool &) -> std::optional<Value *> { return nullptr; };
3619
3620 Function *F = getAnchorScope();
3621 const OMPInformationCache::RuntimeFunctionInfo::UseVector *Uses =
3622 RFI.getUseVector(F&: *F);
3623 if (!Uses)
3624 return;
3625
3626 for (Use *U : *Uses)
3627 if (CallBase *CB = dyn_cast<CallBase>(Val: U->getUser())) {
3628 MallocCalls.insert(X: CB);
3629 A.registerSimplificationCallback(IRP: IRPosition::callsite_returned(CB: *CB),
3630 CB: SCB);
3631 }
3632
3633 findPotentialRemovedFreeCalls(A);
3634 }
3635
3636 bool isAssumedHeapToShared(CallBase &CB) const override {
3637 return isValidState() && MallocCalls.count(key: &CB);
3638 }
3639
3640 bool isAssumedHeapToSharedRemovedFree(CallBase &CB) const override {
3641 return isValidState() && PotentialRemovedFreeCalls.count(Ptr: &CB);
3642 }
3643
3644 ChangeStatus manifest(Attributor &A) override {
3645 if (MallocCalls.empty())
3646 return ChangeStatus::UNCHANGED;
3647
3648 auto &OMPInfoCache = static_cast<OMPInformationCache &>(A.getInfoCache());
3649 auto &FreeCall = OMPInfoCache.RFIs[OMPRTL___kmpc_free_shared];
3650
3651 Function *F = getAnchorScope();
3652 auto *HS = A.lookupAAFor<AAHeapToStack>(IRP: IRPosition::function(F: *F), QueryingAA: this,
3653 DepClass: DepClassTy::OPTIONAL);
3654
3655 ChangeStatus Changed = ChangeStatus::UNCHANGED;
3656 for (CallBase *CB : MallocCalls) {
3657 // Skip replacing this if HeapToStack has already claimed it.
3658 if (HS && HS->isAssumedHeapToStack(CB: *CB))
3659 continue;
3660
3661 // Find the unique free call to remove it.
3662 SmallVector<CallBase *, 4> FreeCalls;
3663 for (auto *U : CB->users()) {
3664 CallBase *C = dyn_cast<CallBase>(Val: U);
3665 if (C && C->getCalledFunction() == FreeCall.Declaration)
3666 FreeCalls.push_back(Elt: C);
3667 }
3668 if (FreeCalls.size() != 1)
3669 continue;
3670
3671 auto *AllocSize = cast<ConstantInt>(Val: CB->getArgOperand(i: 0));
3672
3673 if (AllocSize->getZExtValue() + SharedMemoryUsed > SharedMemoryLimit) {
3674 LLVM_DEBUG(dbgs() << TAG << "Cannot replace call " << *CB
3675 << " with shared memory."
3676 << " Shared memory usage is limited to "
3677 << SharedMemoryLimit << " bytes\n");
3678 continue;
3679 }
3680
3681 LLVM_DEBUG(dbgs() << TAG << "Replace globalization call " << *CB
3682 << " with " << AllocSize->getZExtValue()
3683 << " bytes of shared memory\n");
3684
3685 // Create a new shared memory buffer of the same size as the allocation
3686 // and replace all the uses of the original allocation with it.
3687 Module *M = CB->getModule();
3688 Type *Int8Ty = Type::getInt8Ty(C&: M->getContext());
3689 Type *Int8ArrTy = ArrayType::get(ElementType: Int8Ty, NumElements: AllocSize->getZExtValue());
3690 auto *SharedMem = new GlobalVariable(
3691 *M, Int8ArrTy, /* IsConstant */ false, GlobalValue::InternalLinkage,
3692 PoisonValue::get(T: Int8ArrTy), CB->getName() + "_shared", nullptr,
3693 GlobalValue::NotThreadLocal,
3694 static_cast<unsigned>(AddressSpace::Shared));
3695 auto *NewBuffer = ConstantExpr::getPointerCast(
3696 C: SharedMem, Ty: PointerType::getUnqual(C&: M->getContext()));
3697
3698 auto Remark = [&](OptimizationRemark OR) {
3699 return OR << "Replaced globalized variable with "
3700 << ore::NV("SharedMemory", AllocSize->getZExtValue())
3701 << (AllocSize->isOne() ? " byte " : " bytes ")
3702 << "of shared memory.";
3703 };
3704 A.emitRemark<OptimizationRemark>(I: CB, RemarkName: "OMP111", RemarkCB&: Remark);
3705
3706 MaybeAlign Alignment = CB->getRetAlign();
3707 assert(Alignment &&
3708 "HeapToShared on allocation without alignment attribute");
3709 SharedMem->setAlignment(*Alignment);
3710
3711 A.changeAfterManifest(IRP: IRPosition::callsite_returned(CB: *CB), NV&: *NewBuffer);
3712 A.deleteAfterManifest(I&: *CB);
3713 A.deleteAfterManifest(I&: *FreeCalls.front());
3714
3715 SharedMemoryUsed += AllocSize->getZExtValue();
3716 NumBytesMovedToSharedMemory = SharedMemoryUsed;
3717 Changed = ChangeStatus::CHANGED;
3718 }
3719
3720 return Changed;
3721 }
3722
3723 ChangeStatus updateImpl(Attributor &A) override {
3724 if (MallocCalls.empty())
3725 return indicatePessimisticFixpoint();
3726 auto &OMPInfoCache = static_cast<OMPInformationCache &>(A.getInfoCache());
3727 auto &RFI = OMPInfoCache.RFIs[OMPRTL___kmpc_alloc_shared];
3728 if (!RFI.Declaration)
3729 return ChangeStatus::UNCHANGED;
3730
3731 Function *F = getAnchorScope();
3732
3733 auto NumMallocCalls = MallocCalls.size();
3734
3735 // Only consider malloc calls executed by a single thread with a constant.
3736 for (User *U : RFI.Declaration->users()) {
3737 if (CallBase *CB = dyn_cast<CallBase>(Val: U)) {
3738 if (CB->getCaller() != F)
3739 continue;
3740 if (!MallocCalls.count(key: CB))
3741 continue;
3742 if (!isa<ConstantInt>(Val: CB->getArgOperand(i: 0))) {
3743 MallocCalls.remove(X: CB);
3744 continue;
3745 }
3746 const auto *ED = A.getAAFor<AAExecutionDomain>(
3747 QueryingAA: *this, IRP: IRPosition::function(F: *F), DepClass: DepClassTy::REQUIRED);
3748 if (!ED || !ED->isExecutedByInitialThreadOnly(I: *CB))
3749 MallocCalls.remove(X: CB);
3750 }
3751 }
3752
3753 findPotentialRemovedFreeCalls(A);
3754
3755 if (NumMallocCalls != MallocCalls.size())
3756 return ChangeStatus::CHANGED;
3757
3758 return ChangeStatus::UNCHANGED;
3759 }
3760
3761 /// Collection of all malloc calls in a function.
3762 SmallSetVector<CallBase *, 4> MallocCalls;
3763 /// Collection of potentially removed free calls in a function.
3764 SmallPtrSet<CallBase *, 4> PotentialRemovedFreeCalls;
3765 /// The total amount of shared memory that has been used for HeapToShared.
3766 unsigned SharedMemoryUsed = 0;
3767};
3768
3769struct AAKernelInfo : public StateWrapper<KernelInfoState, AbstractAttribute> {
3770 using Base = StateWrapper<KernelInfoState, AbstractAttribute>;
3771 AAKernelInfo(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
3772
3773 /// The callee value is tracked beyond a simple stripPointerCasts, so we allow
3774 /// unknown callees.
3775 static bool requiresCalleeForCallBase() { return false; }
3776
3777 /// Statistics are tracked as part of manifest for now.
3778 void trackStatistics() const override {}
3779
3780 /// See AbstractAttribute::getAsStr()
3781 const std::string getAsStr(Attributor *) const override {
3782 if (!isValidState())
3783 return "<invalid>";
3784 return std::string(SPMDCompatibilityTracker.isAssumed() ? "SPMD"
3785 : "generic") +
3786 std::string(SPMDCompatibilityTracker.isAtFixpoint() ? " [FIX]"
3787 : "") +
3788 std::string(" #PRs: ") +
3789 (ReachedKnownParallelRegions.isValidState()
3790 ? std::to_string(val: ReachedKnownParallelRegions.size())
3791 : "<invalid>") +
3792 ", #Unknown PRs: " +
3793 (ReachedUnknownParallelRegions.isValidState()
3794 ? std::to_string(val: ReachedUnknownParallelRegions.size())
3795 : "<invalid>") +
3796 ", #Reaching Kernels: " +
3797 (ReachingKernelEntries.isValidState()
3798 ? std::to_string(val: ReachingKernelEntries.size())
3799 : "<invalid>") +
3800 ", #ParLevels: " +
3801 (ParallelLevels.isValidState()
3802 ? std::to_string(val: ParallelLevels.size())
3803 : "<invalid>") +
3804 ", NestedPar: " + (NestedParallelism ? "yes" : "no");
3805 }
3806
3807 /// Create an abstract attribute biew for the position \p IRP.
3808 static AAKernelInfo &createForPosition(const IRPosition &IRP, Attributor &A);
3809
3810 /// See AbstractAttribute::getName()
3811 StringRef getName() const override { return "AAKernelInfo"; }
3812
3813 /// See AbstractAttribute::getIdAddr()
3814 const char *getIdAddr() const override { return &ID; }
3815
3816 /// This function should return true if the type of the \p AA is AAKernelInfo
3817 static bool classof(const AbstractAttribute *AA) {
3818 return (AA->getIdAddr() == &ID);
3819 }
3820
3821 static const char ID;
3822};
3823
3824// Fences stronger than a workgroup order memory the SPMD barrier does not.
3825static bool isStrictFence(const Instruction &I) {
3826 const auto *FI = dyn_cast<FenceInst>(Val: &I);
3827 if (!FI)
3828 return false;
3829 SyncScope::ID SS = FI->getSyncScopeID();
3830 if (SS == SyncScope::SingleThread)
3831 return false;
3832 if (SS == SyncScope::System)
3833 return true;
3834 std::optional<StringRef> Name = FI->getContext().getSyncScopeName(Id: SS);
3835 if (!Name)
3836 return true;
3837 auto Parsed =
3838 parseAtomicScopeIRString(T: FI->getModule()->getTargetTriple(), Name: *Name);
3839 if (!Parsed)
3840 return true;
3841 switch (Parsed->first) {
3842 case AtomicScope::Single:
3843 case AtomicScope::Wavefront:
3844 case AtomicScope::Workgroup:
3845 return false;
3846 case AtomicScope::Cluster:
3847 case AtomicScope::Device:
3848 case AtomicScope::System:
3849 return true;
3850 }
3851 return true;
3852}
3853
3854/// The function kernel info abstract attribute, basically, what can we say
3855/// about a function with regards to the KernelInfoState.
3856struct AAKernelInfoFunction : AAKernelInfo {
3857 AAKernelInfoFunction(const IRPosition &IRP, Attributor &A)
3858 : AAKernelInfo(IRP, A) {}
3859
3860 SmallPtrSet<Instruction *, 4> GuardedInstructions;
3861
3862 SmallPtrSetImpl<Instruction *> &getGuardedInstructions() {
3863 return GuardedInstructions;
3864 }
3865
3866 void setConfigurationOfKernelEnvironment(ConstantStruct *ConfigC) {
3867 Constant *NewKernelEnvC = ConstantFoldInsertValueInstruction(
3868 Agg: KernelEnvC, Val: ConfigC, Idxs: {KernelInfo::ConfigurationIdx});
3869 assert(NewKernelEnvC && "Failed to create new kernel environment");
3870 KernelEnvC = cast<ConstantStruct>(Val: NewKernelEnvC);
3871 }
3872
3873#define KERNEL_ENVIRONMENT_CONFIGURATION_SETTER(MEMBER) \
3874 void set##MEMBER##OfKernelEnvironment(ConstantInt *NewVal) { \
3875 ConstantStruct *ConfigC = \
3876 KernelInfo::getConfigurationFromKernelEnvironment(KernelEnvC); \
3877 Constant *NewConfigC = ConstantFoldInsertValueInstruction( \
3878 ConfigC, NewVal, {KernelInfo::MEMBER##Idx}); \
3879 assert(NewConfigC && "Failed to create new configuration environment"); \
3880 setConfigurationOfKernelEnvironment(cast<ConstantStruct>(NewConfigC)); \
3881 }
3882
3883 KERNEL_ENVIRONMENT_CONFIGURATION_SETTER(UseGenericStateMachine)
3884 KERNEL_ENVIRONMENT_CONFIGURATION_SETTER(MayUseNestedParallelism)
3885 KERNEL_ENVIRONMENT_CONFIGURATION_SETTER(ExecMode)
3886 KERNEL_ENVIRONMENT_CONFIGURATION_SETTER(MinThreads)
3887 KERNEL_ENVIRONMENT_CONFIGURATION_SETTER(MaxThreads)
3888 KERNEL_ENVIRONMENT_CONFIGURATION_SETTER(MinTeams)
3889 KERNEL_ENVIRONMENT_CONFIGURATION_SETTER(MaxTeams)
3890
3891#undef KERNEL_ENVIRONMENT_CONFIGURATION_SETTER
3892
3893 /// See AbstractAttribute::initialize(...).
3894 void initialize(Attributor &A) override {
3895 // This is a high-level transform that might change the constant arguments
3896 // of the init and dinit calls. We need to tell the Attributor about this
3897 // to avoid other parts using the current constant value for simpliication.
3898 auto &OMPInfoCache = static_cast<OMPInformationCache &>(A.getInfoCache());
3899
3900 Function *Fn = getAnchorScope();
3901
3902 OMPInformationCache::RuntimeFunctionInfo &InitRFI =
3903 OMPInfoCache.RFIs[OMPRTL___kmpc_target_init];
3904 OMPInformationCache::RuntimeFunctionInfo &DeinitRFI =
3905 OMPInfoCache.RFIs[OMPRTL___kmpc_target_deinit];
3906
3907 // For kernels we perform more initialization work, first we find the init
3908 // and deinit calls.
3909 auto StoreCallBase = [](Use &U,
3910 OMPInformationCache::RuntimeFunctionInfo &RFI,
3911 CallBase *&Storage) {
3912 CallBase *CB = OpenMPOpt::getCallIfRegularCall(U, RFI: &RFI);
3913 assert(CB &&
3914 "Unexpected use of __kmpc_target_init or __kmpc_target_deinit!");
3915 assert(!Storage &&
3916 "Multiple uses of __kmpc_target_init or __kmpc_target_deinit!");
3917 Storage = CB;
3918 return false;
3919 };
3920 InitRFI.foreachUse(
3921 CB: [&](Use &U, Function &) {
3922 StoreCallBase(U, InitRFI, KernelInitCB);
3923 return false;
3924 },
3925 F: Fn);
3926 DeinitRFI.foreachUse(
3927 CB: [&](Use &U, Function &) {
3928 StoreCallBase(U, DeinitRFI, KernelDeinitCB);
3929 return false;
3930 },
3931 F: Fn);
3932
3933 // Ignore kernels without initializers such as global constructors.
3934 if (!KernelInitCB || !KernelDeinitCB)
3935 return;
3936
3937 // Add itself to the reaching kernel and set IsKernelEntry.
3938 ReachingKernelEntries.insert(Elem: Fn);
3939 IsKernelEntry = true;
3940
3941 KernelEnvC =
3942 KernelInfo::getKernelEnvironementFromKernelInitCB(KernelInitCB);
3943 GlobalVariable *KernelEnvGV =
3944 KernelInfo::getKernelEnvironementGVFromKernelInitCB(KernelInitCB);
3945
3946 Attributor::GlobalVariableSimplifictionCallbackTy
3947 KernelConfigurationSimplifyCB =
3948 [&](const GlobalVariable &GV, const AbstractAttribute *AA,
3949 bool &UsedAssumedInformation) -> std::optional<Constant *> {
3950 if (!isAtFixpoint()) {
3951 if (!AA)
3952 return nullptr;
3953 UsedAssumedInformation = true;
3954 A.recordDependence(FromAA: *this, ToAA: *AA, DepClass: DepClassTy::OPTIONAL);
3955 }
3956 return KernelEnvC;
3957 };
3958
3959 A.registerGlobalVariableSimplificationCallback(
3960 GV: *KernelEnvGV, CB: KernelConfigurationSimplifyCB);
3961
3962 // We cannot change to SPMD mode if the runtime functions aren't availible.
3963 bool CanChangeToSPMD = OMPInfoCache.runtimeFnsAvailable(
3964 Fns: {OMPRTL___kmpc_get_hardware_thread_id_in_block,
3965 OMPRTL___kmpc_barrier_simple_spmd});
3966
3967 // Check if we know we are in SPMD-mode already.
3968 ConstantInt *ExecModeC =
3969 KernelInfo::getExecModeFromKernelEnvironment(KernelEnvC);
3970 ConstantInt *AssumedExecModeC = ConstantInt::get(
3971 Ty: ExecModeC->getIntegerType(),
3972 V: ExecModeC->getSExtValue() | OMP_TGT_EXEC_MODE_GENERIC_SPMD);
3973 if (ExecModeC->getSExtValue() & OMP_TGT_EXEC_MODE_SPMD)
3974 SPMDCompatibilityTracker.indicateOptimisticFixpoint();
3975 else if (DisableOpenMPOptSPMDization || !CanChangeToSPMD)
3976 // This is a generic region but SPMDization is disabled so stop
3977 // tracking.
3978 SPMDCompatibilityTracker.indicatePessimisticFixpoint();
3979 else
3980 setExecModeOfKernelEnvironment(AssumedExecModeC);
3981
3982 const Triple T(Fn->getParent()->getTargetTriple());
3983 auto *Int32Ty = Type::getInt32Ty(C&: Fn->getContext());
3984 auto [MinThreads, MaxThreads] =
3985 OpenMPIRBuilder::readThreadBoundsForKernel(T, Kernel&: *Fn);
3986 if (MinThreads)
3987 setMinThreadsOfKernelEnvironment(ConstantInt::get(Ty: Int32Ty, V: MinThreads));
3988 if (MaxThreads)
3989 setMaxThreadsOfKernelEnvironment(ConstantInt::get(Ty: Int32Ty, V: MaxThreads));
3990 auto [MinTeams, MaxTeams] =
3991 OpenMPIRBuilder::readTeamBoundsForKernel(T, Kernel&: *Fn);
3992 if (MinTeams)
3993 setMinTeamsOfKernelEnvironment(ConstantInt::get(Ty: Int32Ty, V: MinTeams));
3994 if (MaxTeams)
3995 setMaxTeamsOfKernelEnvironment(ConstantInt::get(Ty: Int32Ty, V: MaxTeams));
3996
3997 ConstantInt *MayUseNestedParallelismC =
3998 KernelInfo::getMayUseNestedParallelismFromKernelEnvironment(KernelEnvC);
3999 ConstantInt *AssumedMayUseNestedParallelismC = ConstantInt::get(
4000 Ty: MayUseNestedParallelismC->getIntegerType(), V: NestedParallelism);
4001 setMayUseNestedParallelismOfKernelEnvironment(
4002 AssumedMayUseNestedParallelismC);
4003
4004 if (!DisableOpenMPOptStateMachineRewrite) {
4005 ConstantInt *UseGenericStateMachineC =
4006 KernelInfo::getUseGenericStateMachineFromKernelEnvironment(
4007 KernelEnvC);
4008 ConstantInt *AssumedUseGenericStateMachineC =
4009 ConstantInt::get(Ty: UseGenericStateMachineC->getIntegerType(), V: false);
4010 setUseGenericStateMachineOfKernelEnvironment(
4011 AssumedUseGenericStateMachineC);
4012 }
4013
4014 // Register virtual uses of functions we might need to preserve.
4015 auto RegisterVirtualUse = [&](RuntimeFunction RFKind,
4016 Attributor::VirtualUseCallbackTy &CB) {
4017 if (!OMPInfoCache.RFIs[RFKind].Declaration)
4018 return;
4019 A.registerVirtualUseCallback(V: *OMPInfoCache.RFIs[RFKind].Declaration, CB);
4020 };
4021
4022 // Add a dependence to ensure updates if the state changes.
4023 auto AddDependence = [](Attributor &A, const AAKernelInfo *KI,
4024 const AbstractAttribute *QueryingAA) {
4025 if (QueryingAA) {
4026 A.recordDependence(FromAA: *KI, ToAA: *QueryingAA, DepClass: DepClassTy::OPTIONAL);
4027 }
4028 return true;
4029 };
4030
4031 Attributor::VirtualUseCallbackTy CustomStateMachineUseCB =
4032 [&](Attributor &A, const AbstractAttribute *QueryingAA) {
4033 // Whenever we create a custom state machine we will insert calls to
4034 // __kmpc_get_max_team_threads,
4035 // __kmpc_barrier_simple_generic,
4036 // __kmpc_kernel_parallel, and
4037 // __kmpc_kernel_end_parallel.
4038 // Not needed if we are on track for SPMDzation.
4039 if (SPMDCompatibilityTracker.isValidState())
4040 return AddDependence(A, this, QueryingAA);
4041 // Not needed if we can't rewrite due to an invalid state.
4042 if (!ReachedKnownParallelRegions.isValidState())
4043 return AddDependence(A, this, QueryingAA);
4044 return false;
4045 };
4046
4047 // Not needed if we are pre-runtime merge.
4048 if (!KernelInitCB->getCalledFunction()->isDeclaration()) {
4049 RegisterVirtualUse(OMPRTL___kmpc_get_max_team_threads,
4050 CustomStateMachineUseCB);
4051 RegisterVirtualUse(OMPRTL___kmpc_barrier_simple_generic,
4052 CustomStateMachineUseCB);
4053 RegisterVirtualUse(OMPRTL___kmpc_kernel_parallel,
4054 CustomStateMachineUseCB);
4055 RegisterVirtualUse(OMPRTL___kmpc_kernel_end_parallel,
4056 CustomStateMachineUseCB);
4057 }
4058
4059 // If we do not perform SPMDzation we do not need the virtual uses below.
4060 if (SPMDCompatibilityTracker.isAtFixpoint())
4061 return;
4062
4063 Attributor::VirtualUseCallbackTy HWThreadIdUseCB =
4064 [&](Attributor &A, const AbstractAttribute *QueryingAA) {
4065 // Whenever we perform SPMDzation we will insert
4066 // __kmpc_get_hardware_thread_id_in_block calls.
4067 if (!SPMDCompatibilityTracker.isValidState())
4068 return AddDependence(A, this, QueryingAA);
4069 return false;
4070 };
4071 RegisterVirtualUse(OMPRTL___kmpc_get_hardware_thread_id_in_block,
4072 HWThreadIdUseCB);
4073
4074 Attributor::VirtualUseCallbackTy SPMDBarrierUseCB =
4075 [&](Attributor &A, const AbstractAttribute *QueryingAA) {
4076 // Whenever we perform SPMDzation with guarding we will insert
4077 // __kmpc_simple_barrier_spmd calls. If SPMDzation failed, there is
4078 // nothing to guard, or there are no parallel regions, we don't need
4079 // the calls.
4080 if (!SPMDCompatibilityTracker.isValidState())
4081 return AddDependence(A, this, QueryingAA);
4082 if (SPMDCompatibilityTracker.empty())
4083 return AddDependence(A, this, QueryingAA);
4084 if (!mayContainParallelRegion())
4085 return AddDependence(A, this, QueryingAA);
4086 return false;
4087 };
4088 RegisterVirtualUse(OMPRTL___kmpc_barrier_simple_spmd, SPMDBarrierUseCB);
4089 }
4090
4091 /// Sanitize the string \p S such that it is a suitable global symbol name.
4092 static std::string sanitizeForGlobalName(std::string S) {
4093 std::replace_if(
4094 first: S.begin(), last: S.end(),
4095 pred: [](const char C) {
4096 return !((C >= 'a' && C <= 'z') || (C >= 'A' && C <= 'Z') ||
4097 (C >= '0' && C <= '9') || C == '_');
4098 },
4099 new_value: '.');
4100 return S;
4101 }
4102
4103 /// Modify the IR based on the KernelInfoState as the fixpoint iteration is
4104 /// finished now.
4105 ChangeStatus manifest(Attributor &A) override {
4106 // If we are not looking at a kernel with __kmpc_target_init and
4107 // __kmpc_target_deinit call we cannot actually manifest the information.
4108 if (!KernelInitCB || !KernelDeinitCB)
4109 return ChangeStatus::UNCHANGED;
4110
4111 ChangeStatus Changed = ChangeStatus::UNCHANGED;
4112
4113 bool HasBuiltStateMachine = true;
4114 if (!changeToSPMDMode(A, Changed)) {
4115 if (!KernelInitCB->getCalledFunction()->isDeclaration())
4116 HasBuiltStateMachine = buildCustomStateMachine(A, Changed);
4117 else
4118 HasBuiltStateMachine = false;
4119 }
4120
4121 // We need to reset KernelEnvC if specific rewriting is not done.
4122 ConstantStruct *ExistingKernelEnvC =
4123 KernelInfo::getKernelEnvironementFromKernelInitCB(KernelInitCB);
4124 ConstantInt *OldUseGenericStateMachineVal =
4125 KernelInfo::getUseGenericStateMachineFromKernelEnvironment(
4126 KernelEnvC: ExistingKernelEnvC);
4127 if (!HasBuiltStateMachine)
4128 setUseGenericStateMachineOfKernelEnvironment(
4129 OldUseGenericStateMachineVal);
4130
4131 // At last, update the KernelEnvc
4132 GlobalVariable *KernelEnvGV =
4133 KernelInfo::getKernelEnvironementGVFromKernelInitCB(KernelInitCB);
4134 if (KernelEnvGV->getInitializer() != KernelEnvC) {
4135 KernelEnvGV->setInitializer(KernelEnvC);
4136 Changed = ChangeStatus::CHANGED;
4137 }
4138
4139 return Changed;
4140 }
4141
4142 void insertInstructionGuardsHelper(Attributor &A) {
4143 auto &OMPInfoCache = static_cast<OMPInformationCache &>(A.getInfoCache());
4144
4145 auto CreateGuardedRegion = [&](Instruction *RegionStartI,
4146 Instruction *RegionEndI) {
4147 LoopInfo *LI = nullptr;
4148 DominatorTree *DT = nullptr;
4149 MemorySSAUpdater *MSU = nullptr;
4150
4151 BasicBlock *ParentBB = RegionStartI->getParent();
4152 Function *Fn = ParentBB->getParent();
4153 Module &M = *Fn->getParent();
4154
4155 // Create all the blocks and logic.
4156 // ParentBB:
4157 // goto RegionCheckTidBB
4158 // RegionCheckTidBB:
4159 // Tid = __kmpc_hardware_thread_id()
4160 // if (Tid != 0)
4161 // goto RegionBarrierBB
4162 // RegionStartBB:
4163 // <execute instructions guarded>
4164 // goto RegionEndBB
4165 // RegionEndBB:
4166 // <store escaping values to shared mem>
4167 // goto RegionBarrierBB
4168 // RegionBarrierBB:
4169 // __kmpc_simple_barrier_spmd()
4170 // // second barrier is omitted if lacking escaping values.
4171 // <load escaping values from shared mem>
4172 // __kmpc_simple_barrier_spmd()
4173 // goto RegionExitBB
4174 // RegionExitBB:
4175 // <execute rest of instructions>
4176
4177 BasicBlock *RegionEndBB = SplitBlock(Old: ParentBB, SplitPt: RegionEndI->getNextNode(),
4178 DT, LI, MSSAU: MSU, BBName: "region.guarded.end");
4179 BasicBlock *RegionBarrierBB =
4180 SplitBlock(Old: RegionEndBB, SplitPt: &*RegionEndBB->getFirstInsertionPt(), DT, LI,
4181 MSSAU: MSU, BBName: "region.barrier");
4182 BasicBlock *RegionExitBB =
4183 SplitBlock(Old: RegionBarrierBB, SplitPt: &*RegionBarrierBB->getFirstInsertionPt(),
4184 DT, LI, MSSAU: MSU, BBName: "region.exit");
4185 BasicBlock *RegionStartBB =
4186 SplitBlock(Old: ParentBB, SplitPt: RegionStartI, DT, LI, MSSAU: MSU, BBName: "region.guarded");
4187
4188 assert(ParentBB->getUniqueSuccessor() == RegionStartBB &&
4189 "Expected a different CFG");
4190
4191 BasicBlock *RegionCheckTidBB = SplitBlock(
4192 Old: ParentBB, SplitPt: ParentBB->getTerminator(), DT, LI, MSSAU: MSU, BBName: "region.check.tid");
4193
4194 // Register basic blocks with the Attributor.
4195 A.registerManifestAddedBasicBlock(BB&: *RegionEndBB);
4196 A.registerManifestAddedBasicBlock(BB&: *RegionBarrierBB);
4197 A.registerManifestAddedBasicBlock(BB&: *RegionExitBB);
4198 A.registerManifestAddedBasicBlock(BB&: *RegionStartBB);
4199 A.registerManifestAddedBasicBlock(BB&: *RegionCheckTidBB);
4200
4201 bool HasBroadcastValues = false;
4202 // Find escaping outputs from the guarded region to outside users and
4203 // broadcast their values to them.
4204 for (Instruction &I : *RegionStartBB) {
4205 SmallVector<Use *, 4> OutsideUses;
4206 for (Use &U : I.uses()) {
4207 Instruction &UsrI = *cast<Instruction>(Val: U.getUser());
4208 if (UsrI.getParent() != RegionStartBB)
4209 OutsideUses.push_back(Elt: &U);
4210 }
4211
4212 if (OutsideUses.empty())
4213 continue;
4214
4215 HasBroadcastValues = true;
4216
4217 // Emit a global variable in shared memory to store the broadcasted
4218 // value.
4219 auto *SharedMem = new GlobalVariable(
4220 M, I.getType(), /* IsConstant */ false,
4221 GlobalValue::InternalLinkage, UndefValue::get(T: I.getType()),
4222 sanitizeForGlobalName(
4223 S: (I.getName() + ".guarded.output.alloc").str()),
4224 nullptr, GlobalValue::NotThreadLocal,
4225 static_cast<unsigned>(AddressSpace::Shared));
4226
4227 // Emit a store instruction to update the value.
4228 new StoreInst(&I, SharedMem,
4229 RegionEndBB->getTerminator()->getIterator());
4230
4231 LoadInst *LoadI = new LoadInst(
4232 I.getType(), SharedMem, I.getName() + ".guarded.output.load",
4233 RegionBarrierBB->getTerminator()->getIterator());
4234
4235 // Emit a load instruction and replace uses of the output value.
4236 for (Use *U : OutsideUses)
4237 A.changeUseAfterManifest(U&: *U, NV&: *LoadI);
4238 }
4239
4240 auto &OMPInfoCache = static_cast<OMPInformationCache &>(A.getInfoCache());
4241
4242 // Go to tid check BB in ParentBB.
4243 const DebugLoc DL = ParentBB->getTerminator()->getDebugLoc();
4244 ParentBB->getTerminator()->eraseFromParent();
4245 OpenMPIRBuilder::LocationDescription Loc(ParentBB->end(), DL);
4246 OMPInfoCache.OMPBuilder.updateToLocation(Loc);
4247 uint32_t SrcLocStrSize;
4248 auto *SrcLocStr =
4249 OMPInfoCache.OMPBuilder.getOrCreateSrcLocStr(Loc, SrcLocStrSize);
4250 Value *Ident =
4251 OMPInfoCache.OMPBuilder.getOrCreateIdent(SrcLocStr, SrcLocStrSize);
4252 UncondBrInst::Create(Target: RegionCheckTidBB, InsertBefore: ParentBB)->setDebugLoc(DL);
4253
4254 // Add check for Tid in RegionCheckTidBB
4255 RegionCheckTidBB->getTerminator()->eraseFromParent();
4256 OpenMPIRBuilder::LocationDescription LocRegionCheckTid(
4257 RegionCheckTidBB->end(), DL);
4258 OMPInfoCache.OMPBuilder.updateToLocation(Loc: LocRegionCheckTid);
4259 FunctionCallee HardwareTidFn =
4260 OMPInfoCache.OMPBuilder.getOrCreateRuntimeFunction(
4261 M, FnID: OMPRTL___kmpc_get_hardware_thread_id_in_block);
4262 CallInst *Tid =
4263 OMPInfoCache.OMPBuilder.Builder.CreateCall(Callee: HardwareTidFn, Args: {});
4264 Tid->setDebugLoc(DL);
4265 OMPInfoCache.setCallingConvention(Callee: HardwareTidFn, CI: Tid);
4266 Value *TidCheck = OMPInfoCache.OMPBuilder.Builder.CreateIsNull(Arg: Tid);
4267 OMPInfoCache.OMPBuilder.Builder
4268 .CreateCondBr(Cond: TidCheck, True: RegionStartBB, False: RegionBarrierBB)
4269 ->setDebugLoc(DL);
4270
4271 // First barrier for synchronization, ensures main thread has updated
4272 // values.
4273 FunctionCallee BarrierFn =
4274 OMPInfoCache.OMPBuilder.getOrCreateRuntimeFunction(
4275 M, FnID: OMPRTL___kmpc_barrier_simple_spmd);
4276 OMPInfoCache.OMPBuilder.updateToLocation(
4277 Loc: {RegionBarrierBB->getFirstInsertionPt(), DL});
4278 CallInst *Barrier =
4279 OMPInfoCache.OMPBuilder.Builder.CreateCall(Callee: BarrierFn, Args: {Ident, Tid});
4280 OMPInfoCache.setCallingConvention(Callee: BarrierFn, CI: Barrier);
4281
4282 // Second barrier ensures workers have read broadcast values.
4283 if (HasBroadcastValues) {
4284 CallInst *Barrier =
4285 CallInst::Create(Func: BarrierFn, Args: {Ident, Tid}, NameStr: "",
4286 InsertBefore: RegionBarrierBB->getTerminator()->getIterator());
4287 Barrier->setDebugLoc(DL);
4288 OMPInfoCache.setCallingConvention(Callee: BarrierFn, CI: Barrier);
4289 }
4290 };
4291
4292 auto &AllocSharedRFI = OMPInfoCache.RFIs[OMPRTL___kmpc_alloc_shared];
4293 SmallPtrSet<BasicBlock *, 8> Visited;
4294 for (Instruction *GuardedI : SPMDCompatibilityTracker) {
4295 BasicBlock *BB = GuardedI->getParent();
4296 if (!Visited.insert(Ptr: BB).second)
4297 continue;
4298
4299 SmallVector<std::pair<Instruction *, Instruction *>> Reorders;
4300 Instruction *LastEffect = nullptr;
4301 BasicBlock::reverse_iterator IP = BB->rbegin(), IPEnd = BB->rend();
4302 while (++IP != IPEnd) {
4303 if (!IP->mayHaveSideEffects() && !IP->mayReadFromMemory())
4304 continue;
4305 Instruction *I = &*IP;
4306 if (OpenMPOpt::getCallIfRegularCall(V&: *I, RFI: &AllocSharedRFI))
4307 continue;
4308 // Nothing tracked is sunk across a strict fence.
4309 if (isStrictFence(I: *I) || !I->user_empty() ||
4310 !SPMDCompatibilityTracker.contains(Elem: I)) {
4311 LastEffect = nullptr;
4312 continue;
4313 }
4314 if (LastEffect)
4315 Reorders.push_back(Elt: {I, LastEffect});
4316 LastEffect = &*IP;
4317 }
4318 for (auto &Reorder : Reorders)
4319 Reorder.first->moveBefore(InsertPos: Reorder.second->getIterator());
4320 }
4321
4322 SmallVector<std::pair<Instruction *, Instruction *>, 4> GuardedRegions;
4323
4324 for (Instruction *GuardedI : SPMDCompatibilityTracker) {
4325 BasicBlock *BB = GuardedI->getParent();
4326 auto *CalleeAA = A.lookupAAFor<AAKernelInfo>(
4327 IRP: IRPosition::function(F: *GuardedI->getFunction()), QueryingAA: nullptr,
4328 DepClass: DepClassTy::NONE);
4329 assert(CalleeAA != nullptr && "Expected Callee AAKernelInfo");
4330 auto &CalleeAAFunction = *cast<AAKernelInfoFunction>(Val: CalleeAA);
4331 // Continue if instruction is already guarded.
4332 if (CalleeAAFunction.getGuardedInstructions().contains(Ptr: GuardedI))
4333 continue;
4334
4335 Instruction *GuardedRegionStart = nullptr, *GuardedRegionEnd = nullptr;
4336 for (Instruction &I : *BB) {
4337 // A strict fence splits a guarded region so it stays outside it.
4338 if (isStrictFence(I)) {
4339 if (SPMDCompatibilityTracker.contains(Elem: &I))
4340 CalleeAAFunction.getGuardedInstructions().insert(Ptr: &I);
4341 if (GuardedRegionStart) {
4342 GuardedRegions.push_back(
4343 Elt: std::make_pair(x&: GuardedRegionStart, y&: GuardedRegionEnd));
4344 GuardedRegionStart = nullptr;
4345 GuardedRegionEnd = nullptr;
4346 }
4347 continue;
4348 }
4349
4350 // If instruction I needs to be guarded update the guarded region
4351 // bounds.
4352 if (SPMDCompatibilityTracker.contains(Elem: &I)) {
4353 CalleeAAFunction.getGuardedInstructions().insert(Ptr: &I);
4354 if (GuardedRegionStart)
4355 GuardedRegionEnd = &I;
4356 else
4357 GuardedRegionStart = GuardedRegionEnd = &I;
4358
4359 continue;
4360 }
4361
4362 // Instruction I does not need guarding, store
4363 // any region found and reset bounds.
4364 if (GuardedRegionStart) {
4365 GuardedRegions.push_back(
4366 Elt: std::make_pair(x&: GuardedRegionStart, y&: GuardedRegionEnd));
4367 GuardedRegionStart = nullptr;
4368 GuardedRegionEnd = nullptr;
4369 }
4370 }
4371 }
4372
4373 for (auto &GR : GuardedRegions)
4374 CreateGuardedRegion(GR.first, GR.second);
4375 }
4376
4377 void forceSingleThreadPerWorkgroupHelper(Attributor &A) {
4378 // Only allow 1 thread per workgroup to continue executing the user code.
4379 //
4380 // InitCB = __kmpc_target_init(...)
4381 // ThreadIdInBlock = __kmpc_get_hardware_thread_id_in_block();
4382 // if (ThreadIdInBlock != 0) return;
4383 // UserCode:
4384 // // user code
4385 //
4386 auto &Ctx = getAnchorValue().getContext();
4387 Function *Kernel = getAssociatedFunction();
4388 assert(Kernel && "Expected an associated function!");
4389
4390 // Create block for user code to branch to from initial block.
4391 BasicBlock *InitBB = KernelInitCB->getParent();
4392 BasicBlock *UserCodeBB = InitBB->splitBasicBlock(
4393 I: KernelInitCB->getNextNode(), BBName: "main.thread.user_code");
4394 BasicBlock *ReturnBB =
4395 BasicBlock::Create(Context&: Ctx, Name: "exit.threads", Parent: Kernel, InsertBefore: UserCodeBB);
4396
4397 // Register blocks with attributor:
4398 A.registerManifestAddedBasicBlock(BB&: *InitBB);
4399 A.registerManifestAddedBasicBlock(BB&: *UserCodeBB);
4400 A.registerManifestAddedBasicBlock(BB&: *ReturnBB);
4401
4402 // Debug location:
4403 const DebugLoc &DLoc = KernelInitCB->getDebugLoc();
4404 ReturnInst::Create(C&: Ctx, InsertAtEnd: ReturnBB)->setDebugLoc(DLoc);
4405 InitBB->getTerminator()->eraseFromParent();
4406
4407 // Prepare call to OMPRTL___kmpc_get_hardware_thread_id_in_block.
4408 Module &M = *Kernel->getParent();
4409 auto &OMPInfoCache = static_cast<OMPInformationCache &>(A.getInfoCache());
4410 FunctionCallee ThreadIdInBlockFn =
4411 OMPInfoCache.OMPBuilder.getOrCreateRuntimeFunction(
4412 M, FnID: OMPRTL___kmpc_get_hardware_thread_id_in_block);
4413
4414 // Get thread ID in block.
4415 CallInst *ThreadIdInBlock =
4416 CallInst::Create(Func: ThreadIdInBlockFn, NameStr: "thread_id.in.block", InsertBefore: InitBB);
4417 OMPInfoCache.setCallingConvention(Callee: ThreadIdInBlockFn, CI: ThreadIdInBlock);
4418 ThreadIdInBlock->setDebugLoc(DLoc);
4419
4420 // Eliminate all threads in the block with ID not equal to 0:
4421 Instruction *IsMainThread =
4422 ICmpInst::Create(Op: ICmpInst::ICmp, Pred: CmpInst::ICMP_NE, S1: ThreadIdInBlock,
4423 S2: ConstantInt::get(Ty: ThreadIdInBlock->getType(), V: 0),
4424 Name: "thread.is_main", InsertBefore: InitBB);
4425 IsMainThread->setDebugLoc(DLoc);
4426 CondBrInst::Create(Cond: IsMainThread, IfTrue: ReturnBB, IfFalse: UserCodeBB, InsertBefore: InitBB);
4427 }
4428
4429 bool changeToSPMDMode(Attributor &A, ChangeStatus &Changed) {
4430 auto &OMPInfoCache = static_cast<OMPInformationCache &>(A.getInfoCache());
4431
4432 if (!SPMDCompatibilityTracker.isAssumed()) {
4433 for (Instruction *NonCompatibleI : SPMDCompatibilityTracker) {
4434 if (!NonCompatibleI)
4435 continue;
4436
4437 // Skip diagnostics on calls to known OpenMP runtime functions for now.
4438 if (auto *CB = dyn_cast<CallBase>(Val: NonCompatibleI))
4439 if (OMPInfoCache.RTLFunctions.contains(V: CB->getCalledFunction()))
4440 continue;
4441
4442 auto Remark = [&](OptimizationRemarkAnalysis ORA) {
4443 ORA << "Value has potential side effects preventing SPMD-mode "
4444 "execution";
4445 if (isa<CallBase>(Val: NonCompatibleI)) {
4446 ORA << ". Add `[[omp::assume(\"ompx_spmd_amenable\")]]` to "
4447 "the called function to override";
4448 }
4449 return ORA << ".";
4450 };
4451 A.emitRemark<OptimizationRemarkAnalysis>(I: NonCompatibleI, RemarkName: "OMP121",
4452 RemarkCB&: Remark);
4453
4454 LLVM_DEBUG(dbgs() << TAG << "SPMD-incompatible side-effect: "
4455 << *NonCompatibleI << "\n");
4456 }
4457
4458 return false;
4459 }
4460
4461 // Get the actual kernel, could be the caller of the anchor scope if we have
4462 // a debug wrapper.
4463 Function *Kernel = getAnchorScope();
4464 if (Kernel->hasLocalLinkage()) {
4465 assert(Kernel->hasOneUse() && "Unexpected use of debug kernel wrapper.");
4466 auto *CB = cast<CallBase>(Val: Kernel->user_back());
4467 Kernel = CB->getCaller();
4468 }
4469 assert(omp::isOpenMPKernel(*Kernel) && "Expected kernel function!");
4470
4471 // Check if the kernel is already in SPMD mode, if so, return success.
4472 ConstantStruct *ExistingKernelEnvC =
4473 KernelInfo::getKernelEnvironementFromKernelInitCB(KernelInitCB);
4474 auto *ExecModeC =
4475 KernelInfo::getExecModeFromKernelEnvironment(KernelEnvC: ExistingKernelEnvC);
4476 const int8_t ExecModeVal = ExecModeC->getSExtValue();
4477 if (ExecModeVal != OMP_TGT_EXEC_MODE_GENERIC)
4478 return true;
4479
4480 // We will now unconditionally modify the IR, indicate a change.
4481 Changed = ChangeStatus::CHANGED;
4482
4483 // Do not use instruction guards when no parallel is present inside
4484 // the target region. Instead, only the main thread of each team executes
4485 // the user code, so there is no need to launch more threads.
4486 if (mayContainParallelRegion()) {
4487 insertInstructionGuardsHelper(A);
4488 } else {
4489 forceSingleThreadPerWorkgroupHelper(A);
4490 setMaxThreadsOfKernelEnvironment(
4491 ConstantInt::get(Ty: Type::getInt32Ty(C&: Kernel->getContext()), V: 1));
4492 }
4493
4494 // Adjust the global exec mode flag that tells the runtime what mode this
4495 // kernel is executed in.
4496 assert(ExecModeVal == OMP_TGT_EXEC_MODE_GENERIC &&
4497 "Initially non-SPMD kernel has SPMD exec mode!");
4498 setExecModeOfKernelEnvironment(
4499 ConstantInt::get(Ty: ExecModeC->getIntegerType(),
4500 V: ExecModeVal | OMP_TGT_EXEC_MODE_GENERIC_SPMD));
4501
4502 ++NumOpenMPTargetRegionKernelsSPMD;
4503
4504 // Record that this kernel now runs SPMD so post-Attributor cleanup can drop
4505 // the now-dead parallel data-sharing wrapper without re-deriving the mode.
4506 OMPInfoCache.SPMDizedKernels.insert(Ptr: Kernel);
4507
4508 auto Remark = [&](OptimizationRemark OR) {
4509 return OR << "Transformed generic-mode kernel to SPMD-mode.";
4510 };
4511 A.emitRemark<OptimizationRemark>(I: KernelInitCB, RemarkName: "OMP120", RemarkCB&: Remark);
4512 return true;
4513 };
4514
4515 bool buildCustomStateMachine(Attributor &A, ChangeStatus &Changed) {
4516 // If we have disabled state machine rewrites, don't make a custom one
4517 if (DisableOpenMPOptStateMachineRewrite)
4518 return false;
4519
4520 // Don't rewrite the state machine if we are not in a valid state.
4521 if (!ReachedKnownParallelRegions.isValidState())
4522 return false;
4523
4524 auto &OMPInfoCache = static_cast<OMPInformationCache &>(A.getInfoCache());
4525 if (!OMPInfoCache.runtimeFnsAvailable(Fns: {OMPRTL___kmpc_get_max_team_threads,
4526 OMPRTL___kmpc_barrier_simple_generic,
4527 OMPRTL___kmpc_kernel_parallel,
4528 OMPRTL___kmpc_kernel_end_parallel}))
4529 return false;
4530
4531 ConstantStruct *ExistingKernelEnvC =
4532 KernelInfo::getKernelEnvironementFromKernelInitCB(KernelInitCB);
4533
4534 // Check if the current configuration is non-SPMD and generic state machine.
4535 // If we already have SPMD mode or a custom state machine we do not need to
4536 // go any further. If it is anything but a constant something is weird and
4537 // we give up.
4538 ConstantInt *UseStateMachineC =
4539 KernelInfo::getUseGenericStateMachineFromKernelEnvironment(
4540 KernelEnvC: ExistingKernelEnvC);
4541 ConstantInt *ModeC =
4542 KernelInfo::getExecModeFromKernelEnvironment(KernelEnvC: ExistingKernelEnvC);
4543
4544 // If we are stuck with generic mode, try to create a custom device (=GPU)
4545 // state machine which is specialized for the parallel regions that are
4546 // reachable by the kernel.
4547 if (UseStateMachineC->isZero() ||
4548 (ModeC->getSExtValue() & OMP_TGT_EXEC_MODE_SPMD))
4549 return false;
4550
4551 Changed = ChangeStatus::CHANGED;
4552
4553 // If not SPMD mode, indicate we use a custom state machine now.
4554 setUseGenericStateMachineOfKernelEnvironment(
4555 ConstantInt::get(Ty: UseStateMachineC->getIntegerType(), V: false));
4556
4557 // If we don't actually need a state machine we are done here. This can
4558 // happen if there simply are no parallel regions. In the resulting kernel
4559 // all worker threads will simply exit right away, leaving the main thread
4560 // to do the work alone.
4561 if (!mayContainParallelRegion()) {
4562 ++NumOpenMPTargetRegionKernelsWithoutStateMachine;
4563
4564 auto Remark = [&](OptimizationRemark OR) {
4565 return OR << "Removing unused state machine from generic-mode kernel.";
4566 };
4567 A.emitRemark<OptimizationRemark>(I: KernelInitCB, RemarkName: "OMP130", RemarkCB&: Remark);
4568
4569 return true;
4570 }
4571
4572 // Keep track in the statistics of our new shiny custom state machine.
4573 if (ReachedUnknownParallelRegions.empty()) {
4574 ++NumOpenMPTargetRegionKernelsCustomStateMachineWithoutFallback;
4575
4576 auto Remark = [&](OptimizationRemark OR) {
4577 return OR << "Rewriting generic-mode kernel with a customized state "
4578 "machine.";
4579 };
4580 A.emitRemark<OptimizationRemark>(I: KernelInitCB, RemarkName: "OMP131", RemarkCB&: Remark);
4581 } else {
4582 ++NumOpenMPTargetRegionKernelsCustomStateMachineWithFallback;
4583
4584 auto Remark = [&](OptimizationRemarkAnalysis OR) {
4585 return OR << "Generic-mode kernel is executed with a customized state "
4586 "machine that requires a fallback.";
4587 };
4588 A.emitRemark<OptimizationRemarkAnalysis>(I: KernelInitCB, RemarkName: "OMP132", RemarkCB&: Remark);
4589
4590 // Tell the user why we ended up with a fallback.
4591 for (CallBase *UnknownParallelRegionCB : ReachedUnknownParallelRegions) {
4592 if (!UnknownParallelRegionCB)
4593 continue;
4594 auto Remark = [&](OptimizationRemarkAnalysis ORA) {
4595 return ORA << "Call may contain unknown parallel regions. Use "
4596 << "`[[omp::assume(\"omp_no_parallelism\")]]` to "
4597 "override.";
4598 };
4599 A.emitRemark<OptimizationRemarkAnalysis>(I: UnknownParallelRegionCB,
4600 RemarkName: "OMP133", RemarkCB&: Remark);
4601 }
4602 }
4603
4604 // Create all the blocks:
4605 //
4606 // InitCB = __kmpc_target_init(...)
4607 // MaxTeamThreads =
4608 // __kmpc_get_max_team_threads(/*IsSPMD=*/false);
4609 // IsWorkerCheckBB: bool IsWorker = InitCB != -1;
4610 // if (IsWorker) {
4611 // if (InitCB >= MaxTeamThreads) return;
4612 // SMBeginBB: __kmpc_barrier_simple_generic(...);
4613 // void *WorkFn;
4614 // bool Active = __kmpc_kernel_parallel(&WorkFn);
4615 // if (!WorkFn) return;
4616 // SMIsActiveCheckBB: if (Active) {
4617 // SMIfCascadeCurrentBB: if (WorkFn == <ParFn0>)
4618 // ParFn0(...);
4619 // SMIfCascadeCurrentBB: else if (WorkFn == <ParFn1>)
4620 // ParFn1(...);
4621 // ...
4622 // SMIfCascadeCurrentBB: else
4623 // ((WorkFnTy*)WorkFn)(...);
4624 // SMEndParallelBB: __kmpc_kernel_end_parallel(...);
4625 // }
4626 // SMDoneBB: __kmpc_barrier_simple_generic(...);
4627 // goto SMBeginBB;
4628 // }
4629 // UserCodeEntryBB: // user code
4630 // __kmpc_target_deinit(...)
4631 //
4632 auto &Ctx = getAnchorValue().getContext();
4633 Function *Kernel = getAssociatedFunction();
4634 assert(Kernel && "Expected an associated function!");
4635
4636 BasicBlock *InitBB = KernelInitCB->getParent();
4637 BasicBlock *UserCodeEntryBB = InitBB->splitBasicBlock(
4638 I: KernelInitCB->getNextNode(), BBName: "thread.user_code.check");
4639 BasicBlock *IsWorkerCheckBB =
4640 BasicBlock::Create(Context&: Ctx, Name: "is_worker_check", Parent: Kernel, InsertBefore: UserCodeEntryBB);
4641 BasicBlock *StateMachineBeginBB = BasicBlock::Create(
4642 Context&: Ctx, Name: "worker_state_machine.begin", Parent: Kernel, InsertBefore: UserCodeEntryBB);
4643 BasicBlock *StateMachineFinishedBB = BasicBlock::Create(
4644 Context&: Ctx, Name: "worker_state_machine.finished", Parent: Kernel, InsertBefore: UserCodeEntryBB);
4645 BasicBlock *StateMachineIsActiveCheckBB = BasicBlock::Create(
4646 Context&: Ctx, Name: "worker_state_machine.is_active.check", Parent: Kernel, InsertBefore: UserCodeEntryBB);
4647 BasicBlock *StateMachineIfCascadeCurrentBB =
4648 BasicBlock::Create(Context&: Ctx, Name: "worker_state_machine.parallel_region.check",
4649 Parent: Kernel, InsertBefore: UserCodeEntryBB);
4650 BasicBlock *StateMachineEndParallelBB =
4651 BasicBlock::Create(Context&: Ctx, Name: "worker_state_machine.parallel_region.end",
4652 Parent: Kernel, InsertBefore: UserCodeEntryBB);
4653 BasicBlock *StateMachineDoneBarrierBB = BasicBlock::Create(
4654 Context&: Ctx, Name: "worker_state_machine.done.barrier", Parent: Kernel, InsertBefore: UserCodeEntryBB);
4655 A.registerManifestAddedBasicBlock(BB&: *InitBB);
4656 A.registerManifestAddedBasicBlock(BB&: *UserCodeEntryBB);
4657 A.registerManifestAddedBasicBlock(BB&: *IsWorkerCheckBB);
4658 A.registerManifestAddedBasicBlock(BB&: *StateMachineBeginBB);
4659 A.registerManifestAddedBasicBlock(BB&: *StateMachineFinishedBB);
4660 A.registerManifestAddedBasicBlock(BB&: *StateMachineIsActiveCheckBB);
4661 A.registerManifestAddedBasicBlock(BB&: *StateMachineIfCascadeCurrentBB);
4662 A.registerManifestAddedBasicBlock(BB&: *StateMachineEndParallelBB);
4663 A.registerManifestAddedBasicBlock(BB&: *StateMachineDoneBarrierBB);
4664
4665 const DebugLoc &DLoc = KernelInitCB->getDebugLoc();
4666 ReturnInst::Create(C&: Ctx, InsertAtEnd: StateMachineFinishedBB)->setDebugLoc(DLoc);
4667 InitBB->getTerminator()->eraseFromParent();
4668
4669 Instruction *IsWorker =
4670 ICmpInst::Create(Op: ICmpInst::ICmp, Pred: llvm::CmpInst::ICMP_NE, S1: KernelInitCB,
4671 S2: ConstantInt::getAllOnesValue(Ty: KernelInitCB->getType()),
4672 Name: "thread.is_worker", InsertBefore: InitBB);
4673 IsWorker->setDebugLoc(DLoc);
4674 CondBrInst::Create(Cond: IsWorker, IfTrue: IsWorkerCheckBB, IfFalse: UserCodeEntryBB, InsertBefore: InitBB);
4675
4676 // How much of the block the main thread takes is the runtime's to know, so
4677 // ask it rather than subtracting a warp here. The mode is passed in because
4678 // this runs before the barrier that would make the shared one visible; it
4679 // is a constant, a custom state machine being built only for generic mode.
4680 Module &M = *Kernel->getParent();
4681 FunctionCallee MaxTeamThreadsFn =
4682 OMPInfoCache.OMPBuilder.getOrCreateRuntimeFunction(
4683 M, FnID: OMPRTL___kmpc_get_max_team_threads);
4684 Constant *IsSPMDArg = ConstantInt::get(Ty: OMPInfoCache.OMPBuilder.Int32, V: 0);
4685 CallInst *MaxTeamThreads = CallInst::Create(
4686 Func: MaxTeamThreadsFn, Args: {IsSPMDArg}, NameStr: "max_team_threads", InsertBefore: IsWorkerCheckBB);
4687 OMPInfoCache.setCallingConvention(Callee: MaxTeamThreadsFn, CI: MaxTeamThreads);
4688 MaxTeamThreads->setDebugLoc(DLoc);
4689 Instruction *IsMainOrWorker = ICmpInst::Create(
4690 Op: ICmpInst::ICmp, Pred: llvm::CmpInst::ICMP_SLT, S1: KernelInitCB, S2: MaxTeamThreads,
4691 Name: "thread.is_main_or_worker", InsertBefore: IsWorkerCheckBB);
4692 IsMainOrWorker->setDebugLoc(DLoc);
4693 CondBrInst::Create(Cond: IsMainOrWorker, IfTrue: StateMachineBeginBB,
4694 IfFalse: StateMachineFinishedBB, InsertBefore: IsWorkerCheckBB);
4695
4696 // Create local storage for the work function pointer.
4697 const DataLayout &DL = M.getDataLayout();
4698 Type *VoidPtrTy = PointerType::getUnqual(C&: Ctx);
4699 Instruction *WorkFnAI =
4700 new AllocaInst(VoidPtrTy, DL.getAllocaAddrSpace(), nullptr,
4701 "worker.work_fn.addr", Kernel->getEntryBlock().begin());
4702 WorkFnAI->setDebugLoc(DLoc);
4703
4704 OMPInfoCache.OMPBuilder.updateToLocation(
4705 Loc: OpenMPIRBuilder::LocationDescription(StateMachineBeginBB->end(), DLoc));
4706
4707 Value *Ident = KernelInfo::getIdentFromKernelEnvironment(KernelEnvC);
4708 Value *GTid = KernelInitCB;
4709
4710 FunctionCallee BarrierFn =
4711 OMPInfoCache.OMPBuilder.getOrCreateRuntimeFunction(
4712 M, FnID: OMPRTL___kmpc_barrier_simple_generic);
4713 CallInst *Barrier =
4714 CallInst::Create(Func: BarrierFn, Args: {Ident, GTid}, NameStr: "", InsertBefore: StateMachineBeginBB);
4715 OMPInfoCache.setCallingConvention(Callee: BarrierFn, CI: Barrier);
4716 Barrier->setDebugLoc(DLoc);
4717
4718 if (WorkFnAI->getType()->getPointerAddressSpace() !=
4719 (unsigned int)AddressSpace::Generic) {
4720 WorkFnAI = new AddrSpaceCastInst(
4721 WorkFnAI, PointerType::get(C&: Ctx, AddressSpace: (unsigned int)AddressSpace::Generic),
4722 WorkFnAI->getName() + ".generic", StateMachineBeginBB);
4723 WorkFnAI->setDebugLoc(DLoc);
4724 }
4725
4726 FunctionCallee KernelParallelFn =
4727 OMPInfoCache.OMPBuilder.getOrCreateRuntimeFunction(
4728 M, FnID: OMPRTL___kmpc_kernel_parallel);
4729 CallInst *IsActiveWorker = CallInst::Create(
4730 Func: KernelParallelFn, Args: {WorkFnAI}, NameStr: "worker.is_active", InsertBefore: StateMachineBeginBB);
4731 OMPInfoCache.setCallingConvention(Callee: KernelParallelFn, CI: IsActiveWorker);
4732 IsActiveWorker->setDebugLoc(DLoc);
4733 Instruction *WorkFn = new LoadInst(VoidPtrTy, WorkFnAI, "worker.work_fn",
4734 StateMachineBeginBB);
4735 WorkFn->setDebugLoc(DLoc);
4736
4737 FunctionType *ParallelRegionFnTy = FunctionType::get(
4738 Result: Type::getVoidTy(C&: Ctx), Params: {Type::getInt16Ty(C&: Ctx), Type::getInt32Ty(C&: Ctx)},
4739 isVarArg: false);
4740
4741 Instruction *IsDone =
4742 ICmpInst::Create(Op: ICmpInst::ICmp, Pred: llvm::CmpInst::ICMP_EQ, S1: WorkFn,
4743 S2: Constant::getNullValue(Ty: VoidPtrTy), Name: "worker.is_done",
4744 InsertBefore: StateMachineBeginBB);
4745 IsDone->setDebugLoc(DLoc);
4746 CondBrInst::Create(Cond: IsDone, IfTrue: StateMachineFinishedBB,
4747 IfFalse: StateMachineIsActiveCheckBB, InsertBefore: StateMachineBeginBB)
4748 ->setDebugLoc(DLoc);
4749
4750 CondBrInst::Create(Cond: IsActiveWorker, IfTrue: StateMachineIfCascadeCurrentBB,
4751 IfFalse: StateMachineDoneBarrierBB, InsertBefore: StateMachineIsActiveCheckBB)
4752 ->setDebugLoc(DLoc);
4753
4754 Value *ZeroArg =
4755 Constant::getNullValue(Ty: ParallelRegionFnTy->getParamType(i: 0));
4756
4757 const unsigned int WrapperFunctionArgNo = 6;
4758
4759 // Now that we have most of the CFG skeleton it is time for the if-cascade
4760 // that checks the function pointer we got from the runtime against the
4761 // parallel regions we expect, if there are any.
4762 for (int I = 0, E = ReachedKnownParallelRegions.size(); I < E; ++I) {
4763 auto *CB = ReachedKnownParallelRegions[I];
4764 auto *ParallelRegion = dyn_cast<Function>(
4765 Val: CB->getArgOperand(i: WrapperFunctionArgNo)->stripPointerCasts());
4766 BasicBlock *PRExecuteBB = BasicBlock::Create(
4767 Context&: Ctx, Name: "worker_state_machine.parallel_region.execute", Parent: Kernel,
4768 InsertBefore: StateMachineEndParallelBB);
4769 CallInst::Create(Func: ParallelRegion, Args: {ZeroArg, GTid}, NameStr: "", InsertBefore: PRExecuteBB)
4770 ->setDebugLoc(DLoc);
4771 UncondBrInst::Create(Target: StateMachineEndParallelBB, InsertBefore: PRExecuteBB)
4772 ->setDebugLoc(DLoc);
4773
4774 BasicBlock *PRNextBB =
4775 BasicBlock::Create(Context&: Ctx, Name: "worker_state_machine.parallel_region.check",
4776 Parent: Kernel, InsertBefore: StateMachineEndParallelBB);
4777 A.registerManifestAddedBasicBlock(BB&: *PRExecuteBB);
4778 A.registerManifestAddedBasicBlock(BB&: *PRNextBB);
4779
4780 // Check if we need to compare the pointer at all or if we can just
4781 // call the parallel region function.
4782 Value *IsPR;
4783 if (I + 1 < E || !ReachedUnknownParallelRegions.empty()) {
4784 Instruction *CmpI = ICmpInst::Create(
4785 Op: ICmpInst::ICmp, Pred: llvm::CmpInst::ICMP_EQ, S1: WorkFn, S2: ParallelRegion,
4786 Name: "worker.check_parallel_region", InsertBefore: StateMachineIfCascadeCurrentBB);
4787 CmpI->setDebugLoc(DLoc);
4788 IsPR = CmpI;
4789 } else {
4790 IsPR = ConstantInt::getTrue(Context&: Ctx);
4791 }
4792
4793 CondBrInst::Create(Cond: IsPR, IfTrue: PRExecuteBB, IfFalse: PRNextBB,
4794 InsertBefore: StateMachineIfCascadeCurrentBB)
4795 ->setDebugLoc(DLoc);
4796 StateMachineIfCascadeCurrentBB = PRNextBB;
4797 }
4798
4799 // At the end of the if-cascade we place the indirect function pointer call
4800 // in case we might need it, that is if there can be parallel regions we
4801 // have not handled in the if-cascade above.
4802 if (!ReachedUnknownParallelRegions.empty()) {
4803 StateMachineIfCascadeCurrentBB->setName(
4804 "worker_state_machine.parallel_region.fallback.execute");
4805 CallInst::Create(Ty: ParallelRegionFnTy, Func: WorkFn, Args: {ZeroArg, GTid}, NameStr: "",
4806 InsertBefore: StateMachineIfCascadeCurrentBB)
4807 ->setDebugLoc(DLoc);
4808 }
4809 UncondBrInst::Create(Target: StateMachineEndParallelBB,
4810 InsertBefore: StateMachineIfCascadeCurrentBB)
4811 ->setDebugLoc(DLoc);
4812
4813 FunctionCallee EndParallelFn =
4814 OMPInfoCache.OMPBuilder.getOrCreateRuntimeFunction(
4815 M, FnID: OMPRTL___kmpc_kernel_end_parallel);
4816 CallInst *EndParallel =
4817 CallInst::Create(Func: EndParallelFn, Args: {}, NameStr: "", InsertBefore: StateMachineEndParallelBB);
4818 OMPInfoCache.setCallingConvention(Callee: EndParallelFn, CI: EndParallel);
4819 EndParallel->setDebugLoc(DLoc);
4820 UncondBrInst::Create(Target: StateMachineDoneBarrierBB, InsertBefore: StateMachineEndParallelBB)
4821 ->setDebugLoc(DLoc);
4822
4823 CallInst::Create(Func: BarrierFn, Args: {Ident, GTid}, NameStr: "", InsertBefore: StateMachineDoneBarrierBB)
4824 ->setDebugLoc(DLoc);
4825 UncondBrInst::Create(Target: StateMachineBeginBB, InsertBefore: StateMachineDoneBarrierBB)
4826 ->setDebugLoc(DLoc);
4827
4828 return true;
4829 }
4830
4831 /// Fixpoint iteration update function. Will be called every time a dependence
4832 /// changed its state (and in the beginning).
4833 ChangeStatus updateImpl(Attributor &A) override {
4834 KernelInfoState StateBefore = getState();
4835
4836 // When we leave this function this RAII will make sure the member
4837 // KernelEnvC is updated properly depending on the state. That member is
4838 // used for simplification of values and needs to be up to date at all
4839 // times.
4840 struct UpdateKernelEnvCRAII {
4841 AAKernelInfoFunction &AA;
4842
4843 UpdateKernelEnvCRAII(AAKernelInfoFunction &AA) : AA(AA) {}
4844
4845 ~UpdateKernelEnvCRAII() {
4846 if (!AA.KernelEnvC)
4847 return;
4848
4849 ConstantStruct *ExistingKernelEnvC =
4850 KernelInfo::getKernelEnvironementFromKernelInitCB(KernelInitCB: AA.KernelInitCB);
4851
4852 if (!AA.isValidState()) {
4853 AA.KernelEnvC = ExistingKernelEnvC;
4854 return;
4855 }
4856
4857 if (!AA.ReachedKnownParallelRegions.isValidState())
4858 AA.setUseGenericStateMachineOfKernelEnvironment(
4859 KernelInfo::getUseGenericStateMachineFromKernelEnvironment(
4860 KernelEnvC: ExistingKernelEnvC));
4861
4862 if (!AA.SPMDCompatibilityTracker.isValidState())
4863 AA.setExecModeOfKernelEnvironment(
4864 KernelInfo::getExecModeFromKernelEnvironment(KernelEnvC: ExistingKernelEnvC));
4865
4866 ConstantInt *MayUseNestedParallelismC =
4867 KernelInfo::getMayUseNestedParallelismFromKernelEnvironment(
4868 KernelEnvC: AA.KernelEnvC);
4869 ConstantInt *NewMayUseNestedParallelismC = ConstantInt::get(
4870 Ty: MayUseNestedParallelismC->getIntegerType(), V: AA.NestedParallelism);
4871 AA.setMayUseNestedParallelismOfKernelEnvironment(
4872 NewMayUseNestedParallelismC);
4873 }
4874 } RAII(*this);
4875
4876 // Callback to check a read/write instruction.
4877 auto CheckRWInst = [&](Instruction &I) {
4878 // We handle calls later.
4879 if (isa<CallBase>(Val: I))
4880 return true;
4881 // We only care about write effects.
4882 if (!I.mayWriteToMemory())
4883 return true;
4884 if (auto *SI = dyn_cast<StoreInst>(Val: &I)) {
4885 const auto *UnderlyingObjsAA = A.getAAFor<AAUnderlyingObjects>(
4886 QueryingAA: *this, IRP: IRPosition::value(V: *SI->getPointerOperand()),
4887 DepClass: DepClassTy::OPTIONAL);
4888 auto *HS = A.getAAFor<AAHeapToStack>(
4889 QueryingAA: *this, IRP: IRPosition::function(F: *I.getFunction()),
4890 DepClass: DepClassTy::OPTIONAL);
4891 if (UnderlyingObjsAA &&
4892 UnderlyingObjsAA->forallUnderlyingObjects(Pred: [&](Value &Obj) {
4893 if (AA::isAssumedThreadLocalObject(A, Obj, QueryingAA: *this))
4894 return true;
4895 // Check for AAHeapToStack moved objects which must not be
4896 // guarded.
4897 auto *CB = dyn_cast<CallBase>(Val: &Obj);
4898 return CB && HS && HS->isAssumedHeapToStack(CB: *CB);
4899 }))
4900 return true;
4901 }
4902
4903 // Insert instruction that needs guarding.
4904 SPMDCompatibilityTracker.insert(Elem: &I);
4905 return true;
4906 };
4907
4908 bool UsedAssumedInformationInCheckRWInst = false;
4909 if (!SPMDCompatibilityTracker.isAtFixpoint())
4910 if (!A.checkForAllReadWriteInstructions(
4911 Pred: CheckRWInst, QueryingAA&: *this, UsedAssumedInformation&: UsedAssumedInformationInCheckRWInst))
4912 SPMDCompatibilityTracker.indicatePessimisticFixpoint();
4913
4914 bool UsedAssumedInformationFromReachingKernels = false;
4915 if (!IsKernelEntry) {
4916 updateParallelLevels(A);
4917
4918 bool AllReachingKernelsKnown = true;
4919 updateReachingKernelEntries(A, AllReachingKernelsKnown);
4920 UsedAssumedInformationFromReachingKernels = !AllReachingKernelsKnown;
4921
4922 if (!SPMDCompatibilityTracker.empty()) {
4923 if (!ParallelLevels.isValidState())
4924 SPMDCompatibilityTracker.indicatePessimisticFixpoint();
4925 else if (!ReachingKernelEntries.isValidState())
4926 SPMDCompatibilityTracker.indicatePessimisticFixpoint();
4927 else {
4928 // Check if all reaching kernels agree on the mode as we can otherwise
4929 // not guard instructions. We might not be sure about the mode so we
4930 // we cannot fix the internal spmd-zation state either.
4931 int SPMD = 0, Generic = 0;
4932 for (auto *Kernel : ReachingKernelEntries) {
4933 auto *CBAA = A.getAAFor<AAKernelInfo>(
4934 QueryingAA: *this, IRP: IRPosition::function(F: *Kernel), DepClass: DepClassTy::OPTIONAL);
4935 if (CBAA && CBAA->SPMDCompatibilityTracker.isValidState() &&
4936 CBAA->SPMDCompatibilityTracker.isAssumed())
4937 ++SPMD;
4938 else
4939 ++Generic;
4940 if (!CBAA || !CBAA->SPMDCompatibilityTracker.isAtFixpoint())
4941 UsedAssumedInformationFromReachingKernels = true;
4942 }
4943 if (SPMD != 0 && Generic != 0)
4944 SPMDCompatibilityTracker.indicatePessimisticFixpoint();
4945 }
4946 }
4947 }
4948
4949 // Callback to check a call instruction.
4950 bool AllParallelRegionStatesWereFixed = true;
4951 bool AllSPMDStatesWereFixed = true;
4952 auto CheckCallInst = [&](Instruction &I) {
4953 auto &CB = cast<CallBase>(Val&: I);
4954 // A runtime function that takes a callback runs the user's code inside
4955 // it, so whatever the callback reaches this kernel reaches too. Fold the
4956 // callback's state in; without this the call tells us nothing about the
4957 // parallel regions on the other side of it.
4958 if (Function *Callback = OMPInformationCache::getAnalyzableCallback(CB)) {
4959 LLVM_DEBUG(dbgs() << TAG << "folding in callback "
4960 << Callback->getName() << " of " << CB << "\n");
4961 if (auto *CallbackAA = A.getAAFor<AAKernelInfo>(
4962 QueryingAA: *this, IRP: IRPosition::function(F: *Callback), DepClass: DepClassTy::OPTIONAL)) {
4963 getState() ^= CallbackAA->getState();
4964 AllSPMDStatesWereFixed &=
4965 CallbackAA->SPMDCompatibilityTracker.isAtFixpoint();
4966 AllParallelRegionStatesWereFixed &=
4967 CallbackAA->ReachedKnownParallelRegions.isAtFixpoint();
4968 AllParallelRegionStatesWereFixed &=
4969 CallbackAA->ReachedUnknownParallelRegions.isAtFixpoint();
4970 }
4971 }
4972 auto *CBAA = A.getAAFor<AAKernelInfo>(
4973 QueryingAA: *this, IRP: IRPosition::callsite_function(CB), DepClass: DepClassTy::OPTIONAL);
4974 if (!CBAA)
4975 return false;
4976 getState() ^= CBAA->getState();
4977 AllSPMDStatesWereFixed &= CBAA->SPMDCompatibilityTracker.isAtFixpoint();
4978 AllParallelRegionStatesWereFixed &=
4979 CBAA->ReachedKnownParallelRegions.isAtFixpoint();
4980 AllParallelRegionStatesWereFixed &=
4981 CBAA->ReachedUnknownParallelRegions.isAtFixpoint();
4982 return true;
4983 };
4984
4985 bool UsedAssumedInformationInCheckCallInst = false;
4986 if (!A.checkForAllCallLikeInstructions(
4987 Pred: CheckCallInst, QueryingAA: *this, UsedAssumedInformation&: UsedAssumedInformationInCheckCallInst)) {
4988 LLVM_DEBUG(dbgs() << TAG
4989 << "Failed to visit all call-like instructions!\n";);
4990 return indicatePessimisticFixpoint();
4991 }
4992
4993 // If we haven't used any assumed information for the reached parallel
4994 // region states we can fix it.
4995 if (!UsedAssumedInformationInCheckCallInst &&
4996 AllParallelRegionStatesWereFixed) {
4997 ReachedKnownParallelRegions.indicateOptimisticFixpoint();
4998 ReachedUnknownParallelRegions.indicateOptimisticFixpoint();
4999 }
5000
5001 // If we haven't used any assumed information for the SPMD state we can fix
5002 // it.
5003 if (!UsedAssumedInformationInCheckRWInst &&
5004 !UsedAssumedInformationInCheckCallInst &&
5005 !UsedAssumedInformationFromReachingKernels && AllSPMDStatesWereFixed)
5006 SPMDCompatibilityTracker.indicateOptimisticFixpoint();
5007
5008 return StateBefore == getState() ? ChangeStatus::UNCHANGED
5009 : ChangeStatus::CHANGED;
5010 }
5011
5012private:
5013 /// Update info regarding reaching kernels.
5014 void updateReachingKernelEntries(Attributor &A,
5015 bool &AllReachingKernelsKnown) {
5016 auto PredCallSite = [&](AbstractCallSite ACS) {
5017 Function *Caller = ACS.getInstruction()->getFunction();
5018
5019 assert(Caller && "Caller is nullptr");
5020
5021 auto *CAA = A.getOrCreateAAFor<AAKernelInfo>(
5022 IRP: IRPosition::function(F: *Caller), QueryingAA: this, DepClass: DepClassTy::REQUIRED);
5023 if (CAA && CAA->ReachingKernelEntries.isValidState()) {
5024 ReachingKernelEntries ^= CAA->ReachingKernelEntries;
5025 return true;
5026 }
5027
5028 // We lost track of the caller of the associated function, any kernel
5029 // could reach now.
5030 ReachingKernelEntries.indicatePessimisticFixpoint();
5031
5032 return true;
5033 };
5034
5035 if (!A.checkForAllCallSites(Pred: PredCallSite, QueryingAA: *this,
5036 RequireAllCallSites: true /* RequireAllCallSites */,
5037 UsedAssumedInformation&: AllReachingKernelsKnown))
5038 ReachingKernelEntries.indicatePessimisticFixpoint();
5039 }
5040
5041 /// Update info regarding parallel levels.
5042 void updateParallelLevels(Attributor &A) {
5043 auto &OMPInfoCache = static_cast<OMPInformationCache &>(A.getInfoCache());
5044 OMPInformationCache::RuntimeFunctionInfo &Parallel60RFI =
5045 OMPInfoCache.RFIs[OMPRTL___kmpc_parallel_60];
5046
5047 auto PredCallSite = [&](AbstractCallSite ACS) {
5048 Function *Caller = ACS.getInstruction()->getFunction();
5049
5050 assert(Caller && "Caller is nullptr");
5051
5052 auto *CAA =
5053 A.getOrCreateAAFor<AAKernelInfo>(IRP: IRPosition::function(F: *Caller));
5054 if (CAA && CAA->ParallelLevels.isValidState()) {
5055 // Any function that is called by `__kmpc_parallel_60` will not be
5056 // folded as the parallel level in the function is updated. In order to
5057 // get it right, all the analysis would depend on the implentation. That
5058 // said, if in the future any change to the implementation, the analysis
5059 // could be wrong. As a consequence, we are just conservative here.
5060 if (Caller == Parallel60RFI.Declaration) {
5061 ParallelLevels.indicatePessimisticFixpoint();
5062 return true;
5063 }
5064
5065 ParallelLevels ^= CAA->ParallelLevels;
5066
5067 return true;
5068 }
5069
5070 // We lost track of the caller of the associated function, any kernel
5071 // could reach now.
5072 ParallelLevels.indicatePessimisticFixpoint();
5073
5074 return true;
5075 };
5076
5077 bool AllCallSitesKnown = true;
5078 if (!A.checkForAllCallSites(Pred: PredCallSite, QueryingAA: *this,
5079 RequireAllCallSites: true /* RequireAllCallSites */,
5080 UsedAssumedInformation&: AllCallSitesKnown))
5081 ParallelLevels.indicatePessimisticFixpoint();
5082 }
5083};
5084
5085/// The call site kernel info abstract attribute, basically, what can we say
5086/// about a call site with regards to the KernelInfoState. For now this simply
5087/// forwards the information from the callee.
5088struct AAKernelInfoCallSite : AAKernelInfo {
5089 AAKernelInfoCallSite(const IRPosition &IRP, Attributor &A)
5090 : AAKernelInfo(IRP, A) {}
5091
5092 /// See AbstractAttribute::initialize(...).
5093 void initialize(Attributor &A) override {
5094 AAKernelInfo::initialize(A);
5095
5096 CallBase &CB = cast<CallBase>(Val&: getAssociatedValue());
5097 auto *AssumptionAA = A.getAAFor<AAAssumptionInfo>(
5098 QueryingAA: *this, IRP: IRPosition::callsite_function(CB), DepClass: DepClassTy::OPTIONAL);
5099
5100 // Check for SPMD-mode assumptions.
5101 if (AssumptionAA && AssumptionAA->hasAssumption(Assumption: "ompx_spmd_amenable")) {
5102 indicateOptimisticFixpoint();
5103 return;
5104 }
5105
5106 // First weed out calls we do not care about, that is readonly/readnone
5107 // calls, intrinsics, and "no_openmp" calls. Neither of these can reach a
5108 // parallel region or anything else we are looking for.
5109 if (!CB.mayWriteToMemory() || isa<IntrinsicInst>(Val: CB)) {
5110 indicateOptimisticFixpoint();
5111 return;
5112 }
5113
5114 // Next we check if we know the callee. If it is a known OpenMP function
5115 // we will handle them explicitly in the switch below. If it is not, we
5116 // will use an AAKernelInfo object on the callee to gather information and
5117 // merge that into the current state. The latter happens in the updateImpl.
5118 auto CheckCallee = [&](Function *Callee, unsigned NumCallees) {
5119 auto &OMPInfoCache = static_cast<OMPInformationCache &>(A.getInfoCache());
5120 const auto &It = OMPInfoCache.RuntimeFunctionIDMap.find(Val: Callee);
5121 if (It == OMPInfoCache.RuntimeFunctionIDMap.end()) {
5122 // Unknown caller or declarations are not analyzable, we give up.
5123 if (!Callee || !A.isFunctionIPOAmendable(F: *Callee)) {
5124
5125 // Unknown callees might contain parallel regions, except if they have
5126 // an appropriate assumption attached.
5127 if (!AssumptionAA ||
5128 !(AssumptionAA->hasAssumption(Assumption: "omp_no_openmp") ||
5129 AssumptionAA->hasAssumption(Assumption: "omp_no_parallelism")))
5130 ReachedUnknownParallelRegions.insert(Elem: &CB);
5131
5132 // If SPMDCompatibilityTracker is not fixed, we need to give up on the
5133 // idea we can run something unknown in SPMD-mode.
5134 if (!SPMDCompatibilityTracker.isAtFixpoint()) {
5135 SPMDCompatibilityTracker.indicatePessimisticFixpoint();
5136 SPMDCompatibilityTracker.insert(Elem: &CB);
5137 }
5138
5139 // We have updated the state for this unknown call properly, there
5140 // won't be any change so we indicate a fixpoint.
5141 indicateOptimisticFixpoint();
5142 }
5143 // If the callee is known and can be used in IPO, we will update the
5144 // state based on the callee state in updateImpl.
5145 return;
5146 }
5147 // More than one callee normally means an indirect call we cannot resolve.
5148 // A runtime function carrying !callback is the exception: the extra edge
5149 // is the callback, which we analyze rather than give up on.
5150 if (NumCallees > 1 && !Callee->hasMetadata(KindID: LLVMContext::MD_callback)) {
5151 indicatePessimisticFixpoint();
5152 return;
5153 }
5154
5155 RuntimeFunction RF = It->getSecond();
5156 switch (RF) {
5157 // All the functions we know are compatible with SPMD mode.
5158 case OMPRTL___kmpc_is_spmd_exec_mode:
5159 case OMPRTL___kmpc_distribute_static_fini:
5160 case OMPRTL___kmpc_for_static_fini:
5161 case OMPRTL___kmpc_global_thread_num:
5162 case OMPRTL___kmpc_get_hardware_num_threads_in_block:
5163 case OMPRTL___kmpc_get_hardware_num_blocks:
5164 case OMPRTL___kmpc_single:
5165 case OMPRTL___kmpc_end_single:
5166 case OMPRTL___kmpc_master:
5167 case OMPRTL___kmpc_end_master:
5168 case OMPRTL___kmpc_barrier:
5169 case OMPRTL___kmpc_nvptx_parallel_reduce_nowait_v2:
5170 case OMPRTL___kmpc_gpu_xteam_reduce_nowait:
5171 case OMPRTL___kmpc_error:
5172 case OMPRTL___kmpc_flush:
5173 case OMPRTL___kmpc_get_hardware_thread_id_in_block:
5174 case OMPRTL___kmpc_get_warp_size:
5175 case OMPRTL_omp_get_thread_num:
5176 case OMPRTL_omp_get_num_threads:
5177 case OMPRTL_omp_get_max_threads:
5178 case OMPRTL_omp_in_parallel:
5179 case OMPRTL_omp_get_dynamic:
5180 case OMPRTL_omp_get_cancellation:
5181 case OMPRTL_omp_get_nested:
5182 case OMPRTL_omp_get_schedule:
5183 case OMPRTL_omp_get_thread_limit:
5184 case OMPRTL_omp_get_supported_active_levels:
5185 case OMPRTL_omp_get_max_active_levels:
5186 case OMPRTL_omp_get_level:
5187 case OMPRTL_omp_get_ancestor_thread_num:
5188 case OMPRTL_omp_get_team_size:
5189 case OMPRTL_omp_get_active_level:
5190 case OMPRTL_omp_in_final:
5191 case OMPRTL_omp_get_proc_bind:
5192 case OMPRTL_omp_get_num_places:
5193 case OMPRTL_omp_get_num_procs:
5194 case OMPRTL_omp_get_place_proc_ids:
5195 case OMPRTL_omp_get_place_num:
5196 case OMPRTL_omp_get_partition_num_places:
5197 case OMPRTL_omp_get_partition_place_nums:
5198 case OMPRTL_omp_get_wtime:
5199 break;
5200 case OMPRTL___kmpc_distribute_static_init_4:
5201 case OMPRTL___kmpc_distribute_static_init_4u:
5202 case OMPRTL___kmpc_distribute_static_init_8:
5203 case OMPRTL___kmpc_distribute_static_init_8u:
5204 case OMPRTL___kmpc_for_static_init_4:
5205 case OMPRTL___kmpc_for_static_init_4u:
5206 case OMPRTL___kmpc_for_static_init_8:
5207 case OMPRTL___kmpc_for_static_init_8u: {
5208 // Check the schedule and allow static schedule in SPMD mode.
5209 unsigned ScheduleArgOpNo = 2;
5210 auto *ScheduleTypeCI =
5211 dyn_cast<ConstantInt>(Val: CB.getArgOperand(i: ScheduleArgOpNo));
5212 unsigned ScheduleTypeVal =
5213 ScheduleTypeCI ? ScheduleTypeCI->getZExtValue() : 0;
5214 switch (OMPScheduleType(ScheduleTypeVal)) {
5215 case OMPScheduleType::UnorderedStatic:
5216 case OMPScheduleType::UnorderedStaticChunked:
5217 case OMPScheduleType::OrderedDistribute:
5218 case OMPScheduleType::OrderedDistributeChunked:
5219 break;
5220 default:
5221 SPMDCompatibilityTracker.indicatePessimisticFixpoint();
5222 SPMDCompatibilityTracker.insert(Elem: &CB);
5223 break;
5224 };
5225 } break;
5226 case OMPRTL___kmpc_target_init:
5227 KernelInitCB = &CB;
5228 break;
5229 case OMPRTL___kmpc_target_deinit:
5230 KernelDeinitCB = &CB;
5231 break;
5232 case OMPRTL___kmpc_parallel_60:
5233 if (!handleParallel60(A, CB))
5234 indicatePessimisticFixpoint();
5235 return;
5236 case OMPRTL___kmpc_omp_task:
5237 // We do not look into tasks right now, just give up.
5238 SPMDCompatibilityTracker.indicatePessimisticFixpoint();
5239 SPMDCompatibilityTracker.insert(Elem: &CB);
5240 ReachedUnknownParallelRegions.insert(Elem: &CB);
5241 break;
5242 case OMPRTL___kmpc_alloc_shared:
5243 case OMPRTL___kmpc_free_shared:
5244 // Return without setting a fixpoint, to be resolved in updateImpl.
5245 return;
5246 // The twelve static-loop entry points split into the two groups below.
5247 // Both come out SPMD-incompatible, but for different reasons: the first
5248 // because the call is single-threaded by construction, the second only
5249 // because SPMD-ization cannot yet guard per iteration. They are kept
5250 // apart so the second can be relaxed on its own once it can.
5251 case OMPRTL___kmpc_distribute_static_loop_4:
5252 case OMPRTL___kmpc_distribute_static_loop_4u:
5253 case OMPRTL___kmpc_distribute_static_loop_8:
5254 case OMPRTL___kmpc_distribute_static_loop_8u:
5255 // A plain `distribute` spreads its iterations over the teams, not over
5256 // the threads of a team: the runtime runs it with TId 0 and a team size
5257 // of one, and asserts the kernel is at parallel level 0. One thread per
5258 // block calls it, which is what generic mode gives it. In SPMD mode
5259 // every thread would call it, each running the whole of its block's
5260 // share of the loop body, so the kernel cannot be SPMD-ized however
5261 // analyzable the body is.
5262 if (!OMPInformationCache::getAnalyzableCallback(CB))
5263 ReachedUnknownParallelRegions.insert(Elem: &CB);
5264 SPMDCompatibilityTracker.indicatePessimisticFixpoint();
5265 SPMDCompatibilityTracker.insert(Elem: &CB);
5266 break;
5267 case OMPRTL___kmpc_distribute_for_static_loop_4:
5268 case OMPRTL___kmpc_distribute_for_static_loop_4u:
5269 case OMPRTL___kmpc_distribute_for_static_loop_8:
5270 case OMPRTL___kmpc_distribute_for_static_loop_8u:
5271 case OMPRTL___kmpc_for_static_loop_4:
5272 case OMPRTL___kmpc_for_static_loop_4u:
5273 case OMPRTL___kmpc_for_static_loop_8:
5274 case OMPRTL___kmpc_for_static_loop_8u:
5275 // These index by the thread's own id, so unlike a plain distribute they
5276 // are meant to be called by every thread of the block, and a kernel
5277 // reaching one is not SPMD-incompatible for that reason alone. What
5278 // stops us is the transform rather than the analysis: SPMD-ization
5279 // guards whatever has to stay single-threaded with a block-wide
5280 // barrier, and a barrier placed inside a loop body only some threads
5281 // run is divergent. Until guarding can express "the thread that owns
5282 // this iteration", stay conservative here too.
5283 if (!OMPInformationCache::getAnalyzableCallback(CB))
5284 ReachedUnknownParallelRegions.insert(Elem: &CB);
5285 SPMDCompatibilityTracker.indicatePessimisticFixpoint();
5286 SPMDCompatibilityTracker.insert(Elem: &CB);
5287 break;
5288 default:
5289 // Unknown OpenMP runtime calls cannot be executed in SPMD-mode,
5290 // generally. However, they do not hide parallel regions.
5291 SPMDCompatibilityTracker.indicatePessimisticFixpoint();
5292 SPMDCompatibilityTracker.insert(Elem: &CB);
5293 break;
5294 }
5295 // All other OpenMP runtime calls will not reach parallel regions so they
5296 // can be safely ignored for now. Since it is a known OpenMP runtime call
5297 // we have now modeled all effects and there is no need for any update.
5298 indicateOptimisticFixpoint();
5299 };
5300
5301 const auto *AACE =
5302 A.getAAFor<AACallEdges>(QueryingAA: *this, IRP: getIRPosition(), DepClass: DepClassTy::OPTIONAL);
5303 if (!AACE || !AACE->getState().isValidState() || AACE->hasUnknownCallee()) {
5304 CheckCallee(getAssociatedFunction(), 1);
5305 return;
5306 }
5307 const auto &OptimisticEdges = AACE->getOptimisticEdges();
5308 for (auto *Callee : OptimisticEdges) {
5309 CheckCallee(Callee, OptimisticEdges.size());
5310 if (isAtFixpoint())
5311 break;
5312 }
5313 }
5314
5315 ChangeStatus updateImpl(Attributor &A) override {
5316 // TODO: Once we have call site specific value information we can provide
5317 // call site specific liveness information and then it makes
5318 // sense to specialize attributes for call sites arguments instead of
5319 // redirecting requests to the callee argument.
5320 auto &OMPInfoCache = static_cast<OMPInformationCache &>(A.getInfoCache());
5321 KernelInfoState StateBefore = getState();
5322
5323 auto CheckCallee = [&](Function *F, int NumCallees) {
5324 const auto &It = OMPInfoCache.RuntimeFunctionIDMap.find(Val: F);
5325
5326 // If F is not a runtime function, propagate the AAKernelInfo of the
5327 // callee.
5328 if (It == OMPInfoCache.RuntimeFunctionIDMap.end()) {
5329 const IRPosition &FnPos = IRPosition::function(F: *F);
5330 auto *FnAA =
5331 A.getAAFor<AAKernelInfo>(QueryingAA: *this, IRP: FnPos, DepClass: DepClassTy::REQUIRED);
5332 if (!FnAA)
5333 return indicatePessimisticFixpoint();
5334 if (getState() == FnAA->getState())
5335 return ChangeStatus::UNCHANGED;
5336 getState() = FnAA->getState();
5337 return ChangeStatus::CHANGED;
5338 }
5339 // See the matching check in initialize: a !callback runtime function has
5340 // a second call edge by construction, and it is one we can analyze.
5341 if (NumCallees > 1 && !F->hasMetadata(KindID: LLVMContext::MD_callback))
5342 return indicatePessimisticFixpoint();
5343
5344 CallBase &CB = cast<CallBase>(Val&: getAssociatedValue());
5345 if (It->getSecond() == OMPRTL___kmpc_parallel_60) {
5346 if (!handleParallel60(A, CB))
5347 return indicatePessimisticFixpoint();
5348 return StateBefore == getState() ? ChangeStatus::UNCHANGED
5349 : ChangeStatus::CHANGED;
5350 }
5351
5352 // F is a runtime function that allocates or frees memory, check
5353 // AAHeapToStack and AAHeapToShared.
5354 assert(
5355 (It->getSecond() == OMPRTL___kmpc_alloc_shared ||
5356 It->getSecond() == OMPRTL___kmpc_free_shared) &&
5357 "Expected a __kmpc_alloc_shared or __kmpc_free_shared runtime call");
5358
5359 auto *HeapToStackAA = A.getAAFor<AAHeapToStack>(
5360 QueryingAA: *this, IRP: IRPosition::function(F: *CB.getCaller()), DepClass: DepClassTy::OPTIONAL);
5361 auto *HeapToSharedAA = A.getAAFor<AAHeapToShared>(
5362 QueryingAA: *this, IRP: IRPosition::function(F: *CB.getCaller()), DepClass: DepClassTy::OPTIONAL);
5363
5364 RuntimeFunction RF = It->getSecond();
5365
5366 switch (RF) {
5367 // If neither HeapToStack nor HeapToShared assume the call is removed,
5368 // assume SPMD incompatibility.
5369 case OMPRTL___kmpc_alloc_shared:
5370 if ((!HeapToStackAA || !HeapToStackAA->isAssumedHeapToStack(CB)) &&
5371 (!HeapToSharedAA || !HeapToSharedAA->isAssumedHeapToShared(CB)))
5372 SPMDCompatibilityTracker.insert(Elem: &CB);
5373 break;
5374 case OMPRTL___kmpc_free_shared:
5375 if ((!HeapToStackAA ||
5376 !HeapToStackAA->isAssumedHeapToStackRemovedFree(CB)) &&
5377 (!HeapToSharedAA ||
5378 !HeapToSharedAA->isAssumedHeapToSharedRemovedFree(CB)))
5379 SPMDCompatibilityTracker.insert(Elem: &CB);
5380 break;
5381 default:
5382 SPMDCompatibilityTracker.indicatePessimisticFixpoint();
5383 SPMDCompatibilityTracker.insert(Elem: &CB);
5384 }
5385 return ChangeStatus::CHANGED;
5386 };
5387
5388 const auto *AACE =
5389 A.getAAFor<AACallEdges>(QueryingAA: *this, IRP: getIRPosition(), DepClass: DepClassTy::OPTIONAL);
5390 if (!AACE || !AACE->getState().isValidState() || AACE->hasUnknownCallee()) {
5391 if (Function *F = getAssociatedFunction())
5392 CheckCallee(F, /*NumCallees=*/1);
5393 } else {
5394 const auto &OptimisticEdges = AACE->getOptimisticEdges();
5395 for (auto *Callee : OptimisticEdges) {
5396 CheckCallee(Callee, OptimisticEdges.size());
5397 if (isAtFixpoint())
5398 break;
5399 }
5400 }
5401
5402 return StateBefore == getState() ? ChangeStatus::UNCHANGED
5403 : ChangeStatus::CHANGED;
5404 }
5405
5406 /// Deal with a __kmpc_parallel_60 call (\p CB). Returns true if the call was
5407 /// handled, if a problem occurred, false is returned.
5408 bool handleParallel60(Attributor &A, CallBase &CB) {
5409 const unsigned int NonWrapperFunctionArgNo = 5;
5410 const unsigned int WrapperFunctionArgNo = 6;
5411 auto ParallelRegionOpArgNo = SPMDCompatibilityTracker.isAssumed()
5412 ? NonWrapperFunctionArgNo
5413 : WrapperFunctionArgNo;
5414
5415 auto *ParallelRegion = dyn_cast<Function>(
5416 Val: CB.getArgOperand(i: ParallelRegionOpArgNo)->stripPointerCasts());
5417 if (!ParallelRegion)
5418 return false;
5419
5420 ReachedKnownParallelRegions.insert(Elem: &CB);
5421 /// Check nested parallelism
5422 auto *FnAA = A.getAAFor<AAKernelInfo>(
5423 QueryingAA: *this, IRP: IRPosition::function(F: *ParallelRegion), DepClass: DepClassTy::OPTIONAL);
5424 NestedParallelism |= !FnAA || !FnAA->getState().isValidState() ||
5425 !FnAA->ReachedKnownParallelRegions.empty() ||
5426 !FnAA->ReachedKnownParallelRegions.isValidState() ||
5427 !FnAA->ReachedUnknownParallelRegions.isValidState() ||
5428 !FnAA->ReachedUnknownParallelRegions.empty();
5429 return true;
5430 }
5431};
5432
5433struct AAFoldRuntimeCall
5434 : public StateWrapper<BooleanState, AbstractAttribute> {
5435 using Base = StateWrapper<BooleanState, AbstractAttribute>;
5436
5437 AAFoldRuntimeCall(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
5438
5439 /// Statistics are tracked as part of manifest for now.
5440 void trackStatistics() const override {}
5441
5442 /// Create an abstract attribute biew for the position \p IRP.
5443 static AAFoldRuntimeCall &createForPosition(const IRPosition &IRP,
5444 Attributor &A);
5445
5446 /// See AbstractAttribute::getName()
5447 StringRef getName() const override { return "AAFoldRuntimeCall"; }
5448
5449 /// See AbstractAttribute::getIdAddr()
5450 const char *getIdAddr() const override { return &ID; }
5451
5452 /// This function should return true if the type of the \p AA is
5453 /// AAFoldRuntimeCall
5454 static bool classof(const AbstractAttribute *AA) {
5455 return (AA->getIdAddr() == &ID);
5456 }
5457
5458 static const char ID;
5459};
5460
5461struct AAFoldRuntimeCallCallSiteReturned : AAFoldRuntimeCall {
5462 AAFoldRuntimeCallCallSiteReturned(const IRPosition &IRP, Attributor &A)
5463 : AAFoldRuntimeCall(IRP, A) {}
5464
5465 /// See AbstractAttribute::getAsStr()
5466 const std::string getAsStr(Attributor *) const override {
5467 if (!isValidState())
5468 return "<invalid>";
5469
5470 std::string Str("simplified value: ");
5471
5472 if (!SimplifiedValue)
5473 return Str + std::string("none");
5474
5475 if (!*SimplifiedValue)
5476 return Str + std::string("nullptr");
5477
5478 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: *SimplifiedValue))
5479 return Str + std::to_string(val: CI->getSExtValue());
5480
5481 return Str + std::string("unknown");
5482 }
5483
5484 void initialize(Attributor &A) override {
5485 if (DisableOpenMPOptFolding)
5486 indicatePessimisticFixpoint();
5487
5488 Function *Callee = getAssociatedFunction();
5489
5490 auto &OMPInfoCache = static_cast<OMPInformationCache &>(A.getInfoCache());
5491 const auto &It = OMPInfoCache.RuntimeFunctionIDMap.find(Val: Callee);
5492 assert(It != OMPInfoCache.RuntimeFunctionIDMap.end() &&
5493 "Expected a known OpenMP runtime function");
5494
5495 RFKind = It->getSecond();
5496
5497 CallBase &CB = cast<CallBase>(Val&: getAssociatedValue());
5498 A.registerSimplificationCallback(
5499 IRP: IRPosition::callsite_returned(CB),
5500 CB: [&](const IRPosition &IRP, const AbstractAttribute *AA,
5501 bool &UsedAssumedInformation) -> std::optional<Value *> {
5502 assert((isValidState() || SimplifiedValue == nullptr) &&
5503 "Unexpected invalid state!");
5504
5505 if (!isAtFixpoint()) {
5506 UsedAssumedInformation = true;
5507 if (AA)
5508 A.recordDependence(FromAA: *this, ToAA: *AA, DepClass: DepClassTy::OPTIONAL);
5509 }
5510 return SimplifiedValue;
5511 });
5512 }
5513
5514 ChangeStatus updateImpl(Attributor &A) override {
5515 ChangeStatus Changed = ChangeStatus::UNCHANGED;
5516 switch (RFKind) {
5517 case OMPRTL___kmpc_is_spmd_exec_mode:
5518 Changed |= foldIsSPMDExecMode(A);
5519 break;
5520 case OMPRTL___kmpc_parallel_level:
5521 Changed |= foldParallelLevel(A);
5522 break;
5523 case OMPRTL___kmpc_get_hardware_num_threads_in_block:
5524 Changed = Changed | foldKernelFnAttribute(A, Attr: "omp_target_thread_limit");
5525 break;
5526 case OMPRTL___kmpc_get_hardware_num_blocks:
5527 Changed = Changed | foldKernelFnAttribute(A, Attr: "omp_target_num_teams");
5528 break;
5529 default:
5530 llvm_unreachable("Unhandled OpenMP runtime function!");
5531 }
5532
5533 return Changed;
5534 }
5535
5536 ChangeStatus manifest(Attributor &A) override {
5537 ChangeStatus Changed = ChangeStatus::UNCHANGED;
5538
5539 if (SimplifiedValue && *SimplifiedValue) {
5540 Instruction &I = *getCtxI();
5541 A.changeAfterManifest(IRP: IRPosition::inst(I), NV&: **SimplifiedValue);
5542 A.deleteAfterManifest(I);
5543
5544 CallBase *CB = dyn_cast<CallBase>(Val: &I);
5545 auto Remark = [&](OptimizationRemark OR) {
5546 if (auto *C = dyn_cast<ConstantInt>(Val: *SimplifiedValue))
5547 return OR << "Replacing OpenMP runtime call "
5548 << CB->getCalledFunction()->getName() << " with "
5549 << ore::NV("FoldedValue", C->getZExtValue()) << ".";
5550 return OR << "Replacing OpenMP runtime call "
5551 << CB->getCalledFunction()->getName() << ".";
5552 };
5553
5554 if (CB && EnableVerboseRemarks)
5555 A.emitRemark<OptimizationRemark>(I: CB, RemarkName: "OMP180", RemarkCB&: Remark);
5556
5557 LLVM_DEBUG(dbgs() << TAG << "Replacing runtime call: " << I << " with "
5558 << **SimplifiedValue << "\n");
5559
5560 Changed = ChangeStatus::CHANGED;
5561 }
5562
5563 return Changed;
5564 }
5565
5566 ChangeStatus indicatePessimisticFixpoint() override {
5567 SimplifiedValue = nullptr;
5568 return AAFoldRuntimeCall::indicatePessimisticFixpoint();
5569 }
5570
5571private:
5572 /// Fold __kmpc_is_spmd_exec_mode into a constant if possible.
5573 ChangeStatus foldIsSPMDExecMode(Attributor &A) {
5574 std::optional<Value *> SimplifiedValueBefore = SimplifiedValue;
5575
5576 unsigned AssumedSPMDCount = 0, KnownSPMDCount = 0;
5577 unsigned AssumedNonSPMDCount = 0, KnownNonSPMDCount = 0;
5578 auto *CallerKernelInfoAA = A.getAAFor<AAKernelInfo>(
5579 QueryingAA: *this, IRP: IRPosition::function(F: *getAnchorScope()), DepClass: DepClassTy::REQUIRED);
5580
5581 if (!CallerKernelInfoAA ||
5582 !CallerKernelInfoAA->ReachingKernelEntries.isValidState())
5583 return indicatePessimisticFixpoint();
5584
5585 for (Kernel K : CallerKernelInfoAA->ReachingKernelEntries) {
5586 auto *AA = A.getAAFor<AAKernelInfo>(QueryingAA: *this, IRP: IRPosition::function(F: *K),
5587 DepClass: DepClassTy::REQUIRED);
5588
5589 if (!AA || !AA->isValidState()) {
5590 SimplifiedValue = nullptr;
5591 return indicatePessimisticFixpoint();
5592 }
5593
5594 if (AA->SPMDCompatibilityTracker.isAssumed()) {
5595 if (AA->SPMDCompatibilityTracker.isAtFixpoint())
5596 ++KnownSPMDCount;
5597 else
5598 ++AssumedSPMDCount;
5599 } else {
5600 if (AA->SPMDCompatibilityTracker.isAtFixpoint())
5601 ++KnownNonSPMDCount;
5602 else
5603 ++AssumedNonSPMDCount;
5604 }
5605 }
5606
5607 if ((AssumedSPMDCount + KnownSPMDCount) &&
5608 (AssumedNonSPMDCount + KnownNonSPMDCount))
5609 return indicatePessimisticFixpoint();
5610
5611 auto &Ctx = getAnchorValue().getContext();
5612 if (KnownSPMDCount || AssumedSPMDCount) {
5613 assert(KnownNonSPMDCount == 0 && AssumedNonSPMDCount == 0 &&
5614 "Expected only SPMD kernels!");
5615 // All reaching kernels are in SPMD mode. Update all function calls to
5616 // __kmpc_is_spmd_exec_mode to 1.
5617 SimplifiedValue = ConstantInt::get(Ty: Type::getInt8Ty(C&: Ctx), V: true);
5618 } else if (KnownNonSPMDCount || AssumedNonSPMDCount) {
5619 assert(KnownSPMDCount == 0 && AssumedSPMDCount == 0 &&
5620 "Expected only non-SPMD kernels!");
5621 // All reaching kernels are in non-SPMD mode. Update all function
5622 // calls to __kmpc_is_spmd_exec_mode to 0.
5623 SimplifiedValue = ConstantInt::get(Ty: Type::getInt8Ty(C&: Ctx), V: false);
5624 } else {
5625 // We have empty reaching kernels, therefore we cannot tell if the
5626 // associated call site can be folded. At this moment, SimplifiedValue
5627 // must be none.
5628 assert(!SimplifiedValue && "SimplifiedValue should be none");
5629 }
5630
5631 return SimplifiedValue == SimplifiedValueBefore ? ChangeStatus::UNCHANGED
5632 : ChangeStatus::CHANGED;
5633 }
5634
5635 /// Fold __kmpc_parallel_level into a constant if possible.
5636 ChangeStatus foldParallelLevel(Attributor &A) {
5637 std::optional<Value *> SimplifiedValueBefore = SimplifiedValue;
5638
5639 auto *CallerKernelInfoAA = A.getAAFor<AAKernelInfo>(
5640 QueryingAA: *this, IRP: IRPosition::function(F: *getAnchorScope()), DepClass: DepClassTy::REQUIRED);
5641
5642 if (!CallerKernelInfoAA ||
5643 !CallerKernelInfoAA->ParallelLevels.isValidState())
5644 return indicatePessimisticFixpoint();
5645
5646 if (!CallerKernelInfoAA->ReachingKernelEntries.isValidState())
5647 return indicatePessimisticFixpoint();
5648
5649 if (CallerKernelInfoAA->ReachingKernelEntries.empty()) {
5650 assert(!SimplifiedValue &&
5651 "SimplifiedValue should keep none at this point");
5652 return ChangeStatus::UNCHANGED;
5653 }
5654
5655 unsigned AssumedSPMDCount = 0, KnownSPMDCount = 0;
5656 unsigned AssumedNonSPMDCount = 0, KnownNonSPMDCount = 0;
5657 for (Kernel K : CallerKernelInfoAA->ReachingKernelEntries) {
5658 auto *AA = A.getAAFor<AAKernelInfo>(QueryingAA: *this, IRP: IRPosition::function(F: *K),
5659 DepClass: DepClassTy::REQUIRED);
5660 if (!AA || !AA->SPMDCompatibilityTracker.isValidState())
5661 return indicatePessimisticFixpoint();
5662
5663 if (AA->SPMDCompatibilityTracker.isAssumed()) {
5664 if (AA->SPMDCompatibilityTracker.isAtFixpoint())
5665 ++KnownSPMDCount;
5666 else
5667 ++AssumedSPMDCount;
5668 } else {
5669 if (AA->SPMDCompatibilityTracker.isAtFixpoint())
5670 ++KnownNonSPMDCount;
5671 else
5672 ++AssumedNonSPMDCount;
5673 }
5674 }
5675
5676 if ((AssumedSPMDCount + KnownSPMDCount) &&
5677 (AssumedNonSPMDCount + KnownNonSPMDCount))
5678 return indicatePessimisticFixpoint();
5679
5680 auto &Ctx = getAnchorValue().getContext();
5681 // If the caller can only be reached by SPMD kernel entries, the parallel
5682 // level is 1. Similarly, if the caller can only be reached by non-SPMD
5683 // kernel entries, it is 0.
5684 if (AssumedSPMDCount || KnownSPMDCount) {
5685 assert(KnownNonSPMDCount == 0 && AssumedNonSPMDCount == 0 &&
5686 "Expected only SPMD kernels!");
5687 SimplifiedValue = ConstantInt::get(Ty: Type::getInt8Ty(C&: Ctx), V: 1);
5688 } else {
5689 assert(KnownSPMDCount == 0 && AssumedSPMDCount == 0 &&
5690 "Expected only non-SPMD kernels!");
5691 SimplifiedValue = ConstantInt::get(Ty: Type::getInt8Ty(C&: Ctx), V: 0);
5692 }
5693 return SimplifiedValue == SimplifiedValueBefore ? ChangeStatus::UNCHANGED
5694 : ChangeStatus::CHANGED;
5695 }
5696
5697 ChangeStatus foldKernelFnAttribute(Attributor &A, llvm::StringRef Attr) {
5698 // Specialize only if all the calls agree with the attribute constant value
5699 int32_t CurrentAttrValue = -1;
5700 std::optional<Value *> SimplifiedValueBefore = SimplifiedValue;
5701
5702 auto *CallerKernelInfoAA = A.getAAFor<AAKernelInfo>(
5703 QueryingAA: *this, IRP: IRPosition::function(F: *getAnchorScope()), DepClass: DepClassTy::REQUIRED);
5704
5705 if (!CallerKernelInfoAA ||
5706 !CallerKernelInfoAA->ReachingKernelEntries.isValidState())
5707 return indicatePessimisticFixpoint();
5708
5709 // Iterate over the kernels that reach this function
5710 for (Kernel K : CallerKernelInfoAA->ReachingKernelEntries) {
5711 int32_t NextAttrVal = K->getFnAttributeAsParsedInteger(Kind: Attr, Default: -1);
5712
5713 if (NextAttrVal == -1 ||
5714 (CurrentAttrValue != -1 && CurrentAttrValue != NextAttrVal))
5715 return indicatePessimisticFixpoint();
5716 CurrentAttrValue = NextAttrVal;
5717 }
5718
5719 if (CurrentAttrValue != -1) {
5720 auto &Ctx = getAnchorValue().getContext();
5721 SimplifiedValue =
5722 ConstantInt::get(Ty: Type::getInt32Ty(C&: Ctx), V: CurrentAttrValue);
5723 }
5724 return SimplifiedValue == SimplifiedValueBefore ? ChangeStatus::UNCHANGED
5725 : ChangeStatus::CHANGED;
5726 }
5727
5728 /// An optional value the associated value is assumed to fold to. That is, we
5729 /// assume the associated value (which is a call) can be replaced by this
5730 /// simplified value.
5731 std::optional<Value *> SimplifiedValue;
5732
5733 /// The runtime function kind of the callee of the associated call site.
5734 RuntimeFunction RFKind;
5735};
5736
5737} // namespace
5738
5739/// Register folding callsite
5740void OpenMPOpt::registerFoldRuntimeCall(RuntimeFunction RF) {
5741 auto &RFI = OMPInfoCache.RFIs[RF];
5742 RFI.foreachUse(SCC, CB: [&](Use &U, Function &F) {
5743 CallInst *CI = OpenMPOpt::getCallIfRegularCall(U, RFI: &RFI);
5744 if (!CI)
5745 return false;
5746 A.getOrCreateAAFor<AAFoldRuntimeCall>(
5747 IRP: IRPosition::callsite_returned(CB: *CI), /* QueryingAA */ nullptr,
5748 DepClass: DepClassTy::NONE, /* ForceUpdate */ false,
5749 /* UpdateAfterInit */ false);
5750 return false;
5751 });
5752}
5753
5754void OpenMPOpt::registerAAs(bool IsModulePass) {
5755 if (SCC.empty())
5756 return;
5757
5758 if (IsModulePass) {
5759 // Ensure we create the AAKernelInfo AAs first and without triggering an
5760 // update. This will make sure we register all value simplification
5761 // callbacks before any other AA has the chance to create an AAValueSimplify
5762 // or similar.
5763 auto CreateKernelInfoCB = [&](Use &, Function &Kernel) {
5764 A.getOrCreateAAFor<AAKernelInfo>(
5765 IRP: IRPosition::function(F: Kernel), /* QueryingAA */ nullptr,
5766 DepClass: DepClassTy::NONE, /* ForceUpdate */ false,
5767 /* UpdateAfterInit */ false);
5768 return false;
5769 };
5770 OMPInformationCache::RuntimeFunctionInfo &InitRFI =
5771 OMPInfoCache.RFIs[OMPRTL___kmpc_target_init];
5772 InitRFI.foreachUse(SCC, CB: CreateKernelInfoCB);
5773
5774 registerFoldRuntimeCall(RF: OMPRTL___kmpc_is_spmd_exec_mode);
5775 registerFoldRuntimeCall(RF: OMPRTL___kmpc_parallel_level);
5776 registerFoldRuntimeCall(RF: OMPRTL___kmpc_get_hardware_num_threads_in_block);
5777 registerFoldRuntimeCall(RF: OMPRTL___kmpc_get_hardware_num_blocks);
5778 }
5779
5780 // Create CallSite AA for all Getters.
5781 if (DeduceICVValues) {
5782 for (int Idx = 0; Idx < OMPInfoCache.ICVs.size() - 1; ++Idx) {
5783 auto ICVInfo = OMPInfoCache.ICVs[static_cast<InternalControlVar>(Idx)];
5784
5785 auto &GetterRFI = OMPInfoCache.RFIs[ICVInfo.Getter];
5786
5787 auto CreateAA = [&](Use &U, Function &Caller) {
5788 CallInst *CI = OpenMPOpt::getCallIfRegularCall(U, RFI: &GetterRFI);
5789 if (!CI)
5790 return false;
5791
5792 auto &CB = cast<CallBase>(Val&: *CI);
5793
5794 IRPosition CBPos = IRPosition::callsite_function(CB);
5795 A.getOrCreateAAFor<AAICVTracker>(IRP: CBPos);
5796 return false;
5797 };
5798
5799 GetterRFI.foreachUse(SCC, CB: CreateAA);
5800 }
5801 }
5802
5803 // Create an ExecutionDomain AA for every function and a HeapToStack AA for
5804 // every function if there is a device kernel.
5805 if (!isOpenMPDevice(M))
5806 return;
5807
5808 for (auto *F : SCC) {
5809 if (F->isDeclaration())
5810 continue;
5811
5812 // We look at internal functions only on-demand but if any use is not a
5813 // direct call or outside the current set of analyzed functions, we have
5814 // to do it eagerly.
5815 if (F->hasLocalLinkage()) {
5816 if (llvm::all_of(Range: F->uses(), P: [this](const Use &U) {
5817 const auto *CB = dyn_cast<CallBase>(Val: U.getUser());
5818 return CB && CB->isCallee(U: &U) &&
5819 A.isRunOn(Fn: const_cast<Function *>(CB->getCaller()));
5820 }))
5821 continue;
5822 }
5823 registerAAsForFunction(A, F: *F);
5824 }
5825}
5826
5827void OpenMPOpt::registerAAsForFunction(Attributor &A, const Function &F) {
5828 auto &OMPInfoCache = static_cast<OMPInformationCache &>(A.getInfoCache());
5829
5830 IRPosition FPos = IRPosition::function(F);
5831 A.getOrCreateAAFor<AAExecutionDomain>(IRP: FPos);
5832 if (F.hasFnAttribute(Kind: Attribute::Convergent))
5833 A.getOrCreateAAFor<AANonConvergent>(IRP: FPos);
5834
5835 bool FunctionUsesSharedAlloc = false;
5836 if (!DisableOpenMPOptDeglobalization) {
5837 const OMPInformationCache::RuntimeFunctionInfo::UseVector *SharedAllocUses =
5838 OMPInfoCache.RFIs[OMPRTL___kmpc_alloc_shared].getUseVector(
5839 F&: const_cast<Function &>(F));
5840 FunctionUsesSharedAlloc = SharedAllocUses && !SharedAllocUses->empty();
5841 }
5842 bool HasHeapToStackCandidate = false;
5843 const TargetLibraryInfo *TLI = nullptr;
5844
5845 for (auto &I : instructions(F)) {
5846 if (auto *LI = dyn_cast<LoadInst>(Val: &I)) {
5847 bool UsedAssumedInformation = false;
5848 A.getAssumedSimplified(V: IRPosition::value(V: *LI), /* AA */ nullptr,
5849 UsedAssumedInformation, S: AA::Interprocedural);
5850 A.getOrCreateAAFor<AAAddressSpace>(
5851 IRP: IRPosition::value(V: *LI->getPointerOperand()));
5852 continue;
5853 }
5854 if (auto *CI = dyn_cast<CallBase>(Val: &I)) {
5855 if (!DisableOpenMPOptDeglobalization && !HasHeapToStackCandidate) {
5856 if (!TLI)
5857 TLI = A.getInfoCache().getTargetLibraryInfoForFunction(F);
5858 HasHeapToStackCandidate =
5859 isRemovableAlloc(V: CI, TLI) || getFreedOperand(CB: CI, TLI);
5860 }
5861 if (CI->isIndirectCall())
5862 A.getOrCreateAAFor<AAIndirectCallInfo>(
5863 IRP: IRPosition::callsite_function(CB: *CI));
5864 }
5865 if (auto *SI = dyn_cast<StoreInst>(Val: &I)) {
5866 A.getOrCreateAAFor<AAIsDead>(IRP: IRPosition::value(V: *SI));
5867 A.getOrCreateAAFor<AAAddressSpace>(
5868 IRP: IRPosition::value(V: *SI->getPointerOperand()));
5869 continue;
5870 }
5871 if (auto *FI = dyn_cast<FenceInst>(Val: &I)) {
5872 A.getOrCreateAAFor<AAIsDead>(IRP: IRPosition::value(V: *FI));
5873 continue;
5874 }
5875 if (auto *II = dyn_cast<IntrinsicInst>(Val: &I)) {
5876 if (II->getIntrinsicID() == Intrinsic::assume) {
5877 A.getOrCreateAAFor<AAPotentialValues>(
5878 IRP: IRPosition::value(V: *II->getArgOperand(i: 0)));
5879 continue;
5880 }
5881 }
5882 }
5883
5884 if (FunctionUsesSharedAlloc)
5885 A.getOrCreateAAFor<AAHeapToShared>(IRP: FPos);
5886 if (HasHeapToStackCandidate)
5887 A.getOrCreateAAFor<AAHeapToStack>(IRP: FPos);
5888}
5889
5890const char AAICVTracker::ID = 0;
5891const char AAKernelInfo::ID = 0;
5892const char AAExecutionDomain::ID = 0;
5893const char AAHeapToShared::ID = 0;
5894const char AAFoldRuntimeCall::ID = 0;
5895
5896AAICVTracker &AAICVTracker::createForPosition(const IRPosition &IRP,
5897 Attributor &A) {
5898 AAICVTracker *AA = nullptr;
5899 switch (IRP.getPositionKind()) {
5900 case IRPosition::IRP_INVALID:
5901 case IRPosition::IRP_FLOAT:
5902 case IRPosition::IRP_ARGUMENT:
5903 case IRPosition::IRP_CALL_SITE_ARGUMENT:
5904 llvm_unreachable("ICVTracker can only be created for function position!");
5905 case IRPosition::IRP_RETURNED:
5906 AA = new (A.Allocator) AAICVTrackerFunctionReturned(IRP, A);
5907 break;
5908 case IRPosition::IRP_CALL_SITE_RETURNED:
5909 AA = new (A.Allocator) AAICVTrackerCallSiteReturned(IRP, A);
5910 break;
5911 case IRPosition::IRP_CALL_SITE:
5912 AA = new (A.Allocator) AAICVTrackerCallSite(IRP, A);
5913 break;
5914 case IRPosition::IRP_FUNCTION:
5915 AA = new (A.Allocator) AAICVTrackerFunction(IRP, A);
5916 break;
5917 }
5918
5919 return *AA;
5920}
5921
5922AAExecutionDomain &AAExecutionDomain::createForPosition(const IRPosition &IRP,
5923 Attributor &A) {
5924 AAExecutionDomainFunction *AA = nullptr;
5925 switch (IRP.getPositionKind()) {
5926 case IRPosition::IRP_INVALID:
5927 case IRPosition::IRP_FLOAT:
5928 case IRPosition::IRP_ARGUMENT:
5929 case IRPosition::IRP_CALL_SITE_ARGUMENT:
5930 case IRPosition::IRP_RETURNED:
5931 case IRPosition::IRP_CALL_SITE_RETURNED:
5932 case IRPosition::IRP_CALL_SITE:
5933 llvm_unreachable(
5934 "AAExecutionDomain can only be created for function position!");
5935 case IRPosition::IRP_FUNCTION:
5936 AA = new (A.Allocator) AAExecutionDomainFunction(IRP, A);
5937 break;
5938 }
5939
5940 return *AA;
5941}
5942
5943AAHeapToShared &AAHeapToShared::createForPosition(const IRPosition &IRP,
5944 Attributor &A) {
5945 AAHeapToSharedFunction *AA = nullptr;
5946 switch (IRP.getPositionKind()) {
5947 case IRPosition::IRP_INVALID:
5948 case IRPosition::IRP_FLOAT:
5949 case IRPosition::IRP_ARGUMENT:
5950 case IRPosition::IRP_CALL_SITE_ARGUMENT:
5951 case IRPosition::IRP_RETURNED:
5952 case IRPosition::IRP_CALL_SITE_RETURNED:
5953 case IRPosition::IRP_CALL_SITE:
5954 llvm_unreachable(
5955 "AAHeapToShared can only be created for function position!");
5956 case IRPosition::IRP_FUNCTION:
5957 AA = new (A.Allocator) AAHeapToSharedFunction(IRP, A);
5958 break;
5959 }
5960
5961 return *AA;
5962}
5963
5964AAKernelInfo &AAKernelInfo::createForPosition(const IRPosition &IRP,
5965 Attributor &A) {
5966 AAKernelInfo *AA = nullptr;
5967 switch (IRP.getPositionKind()) {
5968 case IRPosition::IRP_INVALID:
5969 case IRPosition::IRP_FLOAT:
5970 case IRPosition::IRP_ARGUMENT:
5971 case IRPosition::IRP_RETURNED:
5972 case IRPosition::IRP_CALL_SITE_RETURNED:
5973 case IRPosition::IRP_CALL_SITE_ARGUMENT:
5974 llvm_unreachable("KernelInfo can only be created for function position!");
5975 case IRPosition::IRP_CALL_SITE:
5976 AA = new (A.Allocator) AAKernelInfoCallSite(IRP, A);
5977 break;
5978 case IRPosition::IRP_FUNCTION:
5979 AA = new (A.Allocator) AAKernelInfoFunction(IRP, A);
5980 break;
5981 }
5982
5983 return *AA;
5984}
5985
5986AAFoldRuntimeCall &AAFoldRuntimeCall::createForPosition(const IRPosition &IRP,
5987 Attributor &A) {
5988 AAFoldRuntimeCall *AA = nullptr;
5989 switch (IRP.getPositionKind()) {
5990 case IRPosition::IRP_INVALID:
5991 case IRPosition::IRP_FLOAT:
5992 case IRPosition::IRP_ARGUMENT:
5993 case IRPosition::IRP_RETURNED:
5994 case IRPosition::IRP_FUNCTION:
5995 case IRPosition::IRP_CALL_SITE:
5996 case IRPosition::IRP_CALL_SITE_ARGUMENT:
5997 llvm_unreachable("KernelInfo can only be created for call site position!");
5998 case IRPosition::IRP_CALL_SITE_RETURNED:
5999 AA = new (A.Allocator) AAFoldRuntimeCallCallSiteReturned(IRP, A);
6000 break;
6001 }
6002
6003 return *AA;
6004}
6005
6006/// Bound the if-cascade AAIndirectCallInfo builds for an indirect call. Device
6007/// code reaches its callees through function-pointer tables and virtual
6008/// dispatch, so a call site can see every address-taken candidate in the
6009/// module; specializing all of them costs more in code size and compile time
6010/// than the direct calls are worth.
6011///
6012/// This is a threshold on the call site rather than a limit on how many callees
6013/// get specialized: the Attributor asks about each callee with the same total,
6014/// so a site above the threshold keeps its indirect call instead of getting
6015/// this many direct ones plus a fallback.
6016static bool shouldSpecializeIndirectCallee(Attributor &,
6017 const AbstractAttribute &,
6018 CallBase &, Function &,
6019 unsigned NumAssumedCallees) {
6020 return NumAssumedCallees <= MaxCalleesForSpecialization;
6021}
6022
6023PreservedAnalyses OpenMPOptPass::run(Module &M, ModuleAnalysisManager &AM) {
6024 if (!containsOpenMP(M))
6025 return PreservedAnalyses::all();
6026 if (DisableOpenMPOptimizations)
6027 return PreservedAnalyses::all();
6028
6029 FunctionAnalysisManager &FAM =
6030 AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
6031 KernelSet Kernels = getDeviceKernels(M);
6032
6033 if (PrintModuleBeforeOptimizations)
6034 LLVM_DEBUG(dbgs() << TAG << "Module before OpenMPOpt Module Pass:\n" << M);
6035
6036 auto IsCalled = [&](Function &F) {
6037 if (Kernels.contains(key: &F))
6038 return true;
6039 return !F.use_empty();
6040 };
6041
6042 auto EmitRemark = [&](Function &F) {
6043 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
6044 ORE.emit(RemarkBuilder: [&]() {
6045 OptimizationRemarkAnalysis ORA(DEBUG_TYPE, "OMP140", &F);
6046 return ORA << "Could not internalize function. "
6047 << "Some optimizations may not be possible. [OMP140]";
6048 });
6049 };
6050
6051 bool Changed = false;
6052
6053 // Create internal copies of each function if this is a kernel Module. This
6054 // allows iterprocedural passes to see every call edge.
6055 DenseMap<Function *, Function *> InternalizedMap;
6056 if (isOpenMPDevice(M)) {
6057 SmallPtrSet<Function *, 16> InternalizeFns;
6058 for (Function &F : M)
6059 if (!F.isDeclaration() && !Kernels.contains(key: &F) && IsCalled(F) &&
6060 !DisableInternalization) {
6061 if (Attributor::isInternalizable(F)) {
6062 InternalizeFns.insert(Ptr: &F);
6063 } else if (!F.hasLocalLinkage() && !F.hasFnAttribute(Kind: Attribute::Cold)) {
6064 EmitRemark(F);
6065 }
6066 }
6067
6068 Changed |=
6069 Attributor::internalizeFunctions(FnSet&: InternalizeFns, FnMap&: InternalizedMap);
6070 }
6071
6072 // Look at every function in the Module unless it was internalized.
6073 SetVector<Function *> Functions;
6074 SmallVector<Function *, 16> SCC;
6075 for (Function &F : M)
6076 if (!F.isDeclaration() && !InternalizedMap.lookup(Val: &F)) {
6077 SCC.push_back(Elt: &F);
6078 Functions.insert(X: &F);
6079 }
6080
6081 if (SCC.empty())
6082 return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
6083
6084 AnalysisGetter AG(FAM);
6085
6086 auto OREGetter = [&FAM](Function *F) -> OptimizationRemarkEmitter & {
6087 return FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: *F);
6088 };
6089
6090 BumpPtrAllocator Allocator;
6091 CallGraphUpdater CGUpdater;
6092
6093 bool PostLink = LTOPhase == ThinOrFullLTOPhase::FullLTOPostLink ||
6094 LTOPhase == ThinOrFullLTOPhase::ThinLTOPostLink ||
6095 LTOPhase == ThinOrFullLTOPhase::ThinLTOPreLink;
6096 OMPInformationCache InfoCache(M, AG, Allocator, /*CGSCC*/ nullptr, PostLink);
6097
6098 unsigned MaxFixpointIterations =
6099 (isOpenMPDevice(M)) ? SetFixpointIterations : 32;
6100
6101 AttributorConfig AC(CGUpdater);
6102 AC.DefaultInitializeLiveInternals = false;
6103 AC.IsModulePass = true;
6104 AC.RewriteSignatures = false;
6105 AC.MaxFixpointIterations = MaxFixpointIterations;
6106 AC.OREGetter = OREGetter;
6107 AC.PassName = DEBUG_TYPE;
6108 AC.InitializationCallback = OpenMPOpt::registerAAsForFunction;
6109 AC.IndirectCalleeSpecializationCallback = shouldSpecializeIndirectCallee;
6110 AC.IPOAmendableCB = [](const Function &F) {
6111 return F.hasFnAttribute(Kind: "kernel");
6112 };
6113
6114 Attributor A(Functions, InfoCache, AC);
6115
6116 OpenMPOpt OMPOpt(SCC, CGUpdater, OREGetter, InfoCache, A);
6117 Changed |= OMPOpt.run(IsModulePass: true);
6118
6119 // Optionally inline device functions for potentially better performance.
6120 if (AlwaysInlineDeviceFunctions && isOpenMPDevice(M))
6121 for (Function &F : M)
6122 if (!F.isDeclaration() && !Kernels.contains(key: &F) &&
6123 !F.hasFnAttribute(Kind: Attribute::NoInline))
6124 F.addFnAttr(Kind: Attribute::AlwaysInline);
6125
6126 if (PrintModuleAfterOptimizations)
6127 LLVM_DEBUG(dbgs() << TAG << "Module after OpenMPOpt Module Pass:\n" << M);
6128
6129 if (Changed)
6130 return PreservedAnalyses::none();
6131
6132 return PreservedAnalyses::all();
6133}
6134
6135PreservedAnalyses OpenMPOptCGSCCPass::run(LazyCallGraph::SCC &C,
6136 CGSCCAnalysisManager &AM,
6137 LazyCallGraph &CG,
6138 CGSCCUpdateResult &UR) {
6139 if (!containsOpenMP(M&: *C.begin()->getFunction().getParent()))
6140 return PreservedAnalyses::all();
6141 if (DisableOpenMPOptimizations)
6142 return PreservedAnalyses::all();
6143
6144 SmallVector<Function *, 16> SCC;
6145 // If there are kernels in the module, we have to run on all SCC's.
6146 for (LazyCallGraph::Node &N : C) {
6147 Function *Fn = &N.getFunction();
6148 SCC.push_back(Elt: Fn);
6149 }
6150
6151 if (SCC.empty())
6152 return PreservedAnalyses::all();
6153
6154 Module &M = *C.begin()->getFunction().getParent();
6155
6156 if (PrintModuleBeforeOptimizations)
6157 LLVM_DEBUG(dbgs() << TAG << "Module before OpenMPOpt CGSCC Pass:\n" << M);
6158
6159 FunctionAnalysisManager &FAM =
6160 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(IR&: C, ExtraArgs&: CG).getManager();
6161
6162 AnalysisGetter AG(FAM);
6163
6164 auto OREGetter = [&FAM](Function *F) -> OptimizationRemarkEmitter & {
6165 return FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: *F);
6166 };
6167
6168 BumpPtrAllocator Allocator;
6169 CallGraphUpdater CGUpdater;
6170 CGUpdater.initialize(LCG&: CG, SCC&: C, AM, UR);
6171
6172 bool PostLink = LTOPhase == ThinOrFullLTOPhase::FullLTOPostLink ||
6173 LTOPhase == ThinOrFullLTOPhase::ThinLTOPostLink ||
6174 LTOPhase == ThinOrFullLTOPhase::ThinLTOPreLink;
6175 SetVector<Function *> Functions(llvm::from_range, SCC);
6176 OMPInformationCache InfoCache(*(Functions.back()->getParent()), AG, Allocator,
6177 /*CGSCC*/ &Functions, PostLink);
6178
6179 unsigned MaxFixpointIterations =
6180 (isOpenMPDevice(M)) ? SetFixpointIterations : 32;
6181
6182 AttributorConfig AC(CGUpdater);
6183 AC.DefaultInitializeLiveInternals = false;
6184 AC.IsModulePass = false;
6185 AC.RewriteSignatures = false;
6186 AC.MaxFixpointIterations = MaxFixpointIterations;
6187 AC.OREGetter = OREGetter;
6188 AC.PassName = DEBUG_TYPE;
6189 AC.InitializationCallback = OpenMPOpt::registerAAsForFunction;
6190 AC.IndirectCalleeSpecializationCallback = shouldSpecializeIndirectCallee;
6191
6192 Attributor A(Functions, InfoCache, AC);
6193
6194 OpenMPOpt OMPOpt(SCC, CGUpdater, OREGetter, InfoCache, A);
6195 bool Changed = OMPOpt.run(IsModulePass: false);
6196
6197 if (PrintModuleAfterOptimizations)
6198 LLVM_DEBUG(dbgs() << TAG << "Module after OpenMPOpt CGSCC Pass:\n" << M);
6199
6200 if (Changed)
6201 return PreservedAnalyses::none();
6202
6203 return PreservedAnalyses::all();
6204}
6205
6206bool llvm::omp::isOpenMPKernel(Function &Fn) {
6207 return Fn.hasFnAttribute(Kind: "kernel");
6208}
6209
6210KernelSet llvm::omp::getDeviceKernels(Module &M) {
6211 KernelSet Kernels;
6212
6213 for (Function &F : M)
6214 if (F.hasKernelCallingConv()) {
6215 // We are only interested in OpenMP target regions. Others, such as
6216 // kernels generated by CUDA but linked together, are not interesting to
6217 // this pass.
6218 if (isOpenMPKernel(Fn&: F)) {
6219 ++NumOpenMPTargetRegionKernels;
6220 Kernels.insert(X: &F);
6221 } else
6222 ++NumNonOpenMPTargetRegionKernels;
6223 }
6224
6225 return Kernels;
6226}
6227
6228bool llvm::omp::containsOpenMP(Module &M) {
6229 Metadata *MD = M.getModuleFlag(Key: "openmp");
6230 if (!MD)
6231 return false;
6232
6233 return true;
6234}
6235
6236bool llvm::omp::isOpenMPDevice(Module &M) {
6237 Metadata *MD = M.getModuleFlag(Key: "openmp-device");
6238 if (!MD)
6239 return false;
6240
6241 return true;
6242}
6243