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