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