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