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