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