1//===-- IPO/OpenMPOpt.cpp - Collection of OpenMP specific optimizations ---===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// OpenMP specific optimizations:
10//
11// - Deduplication of runtime calls, e.g., omp_get_thread_num.
12// - Replacing globalized device memory with stack memory.
13// - Replacing globalized device memory with shared memory.
14// - Parallel region merging.
15// - Transforming generic-mode device kernels to SPMD mode.
16// - Specializing the state machine for generic-mode device kernels.
17//
18//===----------------------------------------------------------------------===//
19
20#include "llvm/Transforms/IPO/OpenMPOpt.h"
21#include "IPOOptions.h"
22
23#include "llvm/ADT/DenseSet.h"
24#include "llvm/ADT/EnumeratedArray.h"
25#include "llvm/ADT/PostOrderIterator.h"
26#include "llvm/ADT/SetVector.h"
27#include "llvm/ADT/SmallPtrSet.h"
28#include "llvm/ADT/SmallVector.h"
29#include "llvm/ADT/Statistic.h"
30#include "llvm/ADT/StringExtras.h"
31#include "llvm/ADT/StringRef.h"
32#include "llvm/Analysis/CallGraph.h"
33#include "llvm/Analysis/MemoryBuiltins.h"
34#include "llvm/Analysis/MemoryLocation.h"
35#include "llvm/Analysis/OptimizationRemarkEmitter.h"
36#include "llvm/Analysis/ValueTracking.h"
37#include "llvm/Frontend/OpenMP/OMPConstants.h"
38#include "llvm/Frontend/OpenMP/OMPDeviceConstants.h"
39#include "llvm/Frontend/OpenMP/OMPIRBuilder.h"
40#include "llvm/IR/Assumptions.h"
41#include "llvm/IR/BasicBlock.h"
42#include "llvm/IR/Constants.h"
43#include "llvm/IR/DiagnosticInfo.h"
44#include "llvm/IR/Dominators.h"
45#include "llvm/IR/Function.h"
46#include "llvm/IR/GlobalValue.h"
47#include "llvm/IR/GlobalVariable.h"
48#include "llvm/IR/InstrTypes.h"
49#include "llvm/IR/Instruction.h"
50#include "llvm/IR/Instructions.h"
51#include "llvm/IR/IntrinsicInst.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"
56#include "llvm/IR/ProfDataUtils.h"
57#include "llvm/IR/ProfileSummary.h"
58#include "llvm/Support/Casting.h"
59#include "llvm/Support/Debug.h"
60#include "llvm/TargetParser/AtomicScope.h"
61#include "llvm/TargetParser/Triple.h"
62#include "llvm/Transforms/IPO/Attributor.h"
63#include "llvm/Transforms/Utils/BasicBlockUtils.h"
64#include "llvm/Transforms/Utils/CallGraphUpdater.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");
100STATISTIC(
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)
139KERNEL_ENVIRONMENT_IDX(Ident, 1)
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)
148KERNEL_ENVIRONMENT_CONFIGURATION_IDX(ExecMode, 2)
149KERNEL_ENVIRONMENT_CONFIGURATION_IDX(MinThreads, 3)
150KERNEL_ENVIRONMENT_CONFIGURATION_IDX(MaxThreads, 4)
151KERNEL_ENVIRONMENT_CONFIGURATION_IDX(MinTeams, 5)
152KERNEL_ENVIRONMENT_CONFIGURATION_IDX(MaxTeams, 6)
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
161KERNEL_ENVIRONMENT_GETTER(Ident, Constant)
162KERNEL_ENVIRONMENT_GETTER(Configuration, ConstantStruct)
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)
176KERNEL_ENVIRONMENT_CONFIGURATION_GETTER(ExecMode)
177KERNEL_ENVIRONMENT_CONFIGURATION_GETTER(MinThreads)
178KERNEL_ENVIRONMENT_CONFIGURATION_GETTER(MaxThreads)
179KERNEL_ENVIRONMENT_CONFIGURATION_GETTER(MinTeams)
180KERNEL_ENVIRONMENT_CONFIGURATION_GETTER(MaxTeams)
181
182#undef KERNEL_ENVIRONMENT_CONFIGURATION_GETTER
183
184GlobalVariable *
185getKernelEnvironementGVFromKernelInitCB(CallBase *KernelInitCB) {
186 constexpr int InitKernelEnvironmentArgNo = 0;
187 return cast<GlobalVariable>(
188 Val: KernelInitCB->getArgOperand(i: InitKernelEnvironmentArgNo)
189 ->stripPointerCasts());
190}
191
192ConstantStruct *getKernelEnvironementFromKernelInitCB(CallBase *KernelInitCB) {
193 GlobalVariable *KernelEnvGV =
194 getKernelEnvironementGVFromKernelInitCB(KernelInitCB);
195 return cast<ConstantStruct>(Val: KernelEnvGV->getInitializer());
196}
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(M&: OMPBuilder.M);
215 const Triple T(OMPBuilder.M.getTargetTriple());
216 switch (T.getArch()) {
217 case llvm::Triple::nvptx:
218 case llvm::Triple::nvptx64:
219 case llvm::Triple::amdgpu:
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.
236 InternalControlVar Kind;
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(Val: &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(Elt: 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(FnID: RFI.Kind, Fn&: *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>(Val: U.getUser())) {
453 if (!CGSCC || CGSCC->empty() || CGSCC->contains(key: UserI->getFunction())) {
454 RFI.getOrCreateUseVector(F: UserI->getFunction()).push_back(Elt: &U);
455 ++NumUses;
456 }
457 } else {
458 RFI.getOrCreateUseVector(F: nullptr).push_back(Elt: &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(KindID: LLVMContext::MD_callback))
480 return;
481
482 LLVMContext &Ctx = F->getContext();
483 MDBuilder MDB(Ctx);
484 F->addMetadata(KindID: LLVMContext::MD_callback,
485 MD&: *MDNode::get(Context&: Ctx, MDs: {MDB.createCallbackEncoding(CalleeArgNo: ArgNo, Arguments: Indices,
486 VarArgsArePassed: 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) {
494 Function *Callee = CB.getCalledFunction();
495 if (!Callee)
496 return nullptr;
497 MDNode *CallbackMD = Callee->getMetadata(KindID: 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>(Val: CallbackMD->getOperand(I: 0));
503 if (!Encoding || Encoding->getNumOperands() == 0)
504 return nullptr;
505 auto *ArgNoMD = dyn_cast<ConstantAsMetadata>(Val: Encoding->getOperand(I: 0));
506 if (!ArgNoMD)
507 return nullptr;
508 uint64_t ArgNo =
509 cast<ConstantInt>(Val: ArgNoMD->getValue())->getLimitedValue(UINT64_MAX);
510 if (ArgNo >= CB.arg_size())
511 return nullptr;
512 auto *Callback =
513 dyn_cast<Function>(Val: CB.getArgOperand(i: ArgNo)->stripPointerCasts());
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(RTF: 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>(Val: 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(Kind: Attribute::NoInline) &&
614 F.getName().starts_with(Prefix) &&
615 !F.hasFnAttribute(Kind: Attribute::OptimizeNone))
616 F.removeFnAttr(Kind: 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==(R: 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^=(R: 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(NumElts: NumValues, Elt: nullptr);
869 LastAccesses.assign(NumElts: NumValues, Elt: 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>(Val: &I))
882 continue;
883
884 auto *S = cast<StoreInst>(Val: &I);
885 int64_t Offset = -1;
886 auto *Dst =
887 GetPointerBaseWithConstantOffset(Ptr: 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(V: 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) {
922 auto *Callback = dyn_cast<Function>(
923 Val: CI->getArgOperand(i: 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(a: *EntryCount, b: *EC) : *EC;
930 }
931 return EntryCount;
932}
933
934static bool moduleHasSampleProfile(const Module &M) {
935 std::unique_ptr<ProfileSummary> Summary(
936 ProfileSummary::getFromMD(MD: 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();
954 return Ctx.getDiagHandlerPtr()->isAnyRemarkEnabled(DEBUG_TYPE);
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(I: ICVInfo.InitValue->getValue(), Radix: 10, Signed: true)
1028 : "IMPLEMENTATION_DEFINED");
1029 };
1030
1031 emitRemark<OptimizationRemarkAnalysis>(F, RemarkName: "OpenMPICVTracker", RemarkCB&: 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(Fn&: *F))
1040 continue;
1041
1042 auto Remark = [&](OptimizationRemarkAnalysis ORA) {
1043 return ORA << "OpenMP GPU kernel "
1044 << ore::NV("OpenMPGPUKernel", F->getName()) << "\n";
1045 };
1046
1047 emitRemark<OptimizationRemarkAnalysis>(F, RemarkName: "OpenMPGPU", RemarkCB&: Remark);
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>(Val: U.getUser());
1056 if (CI && CI->isCallee(U: &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>(Val: &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(Old: CGStartBB, SplitPt: &*CodeGenIP, DT, LI);
1106 assert(StartBB != nullptr && "StartBB should not be null");
1107 CGStartBB->getTerminator()->setSuccessor(Idx: 0, BB: StartBB);
1108 assert(EndBB != nullptr && "EndBB should not be null");
1109 EndBB->getTerminator()->setSuccessor(Idx: 0, BB: 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(Old: ParentBB, SplitPt: SeqEndI->getNextNode(), DT, LI);
1132 BasicBlock *SeqAfterBB =
1133 SplitBlock(Old: SeqEndBB, SplitPt: &*SeqEndBB->getFirstInsertionPt(), DT, LI);
1134 BasicBlock *SeqStartBB =
1135 SplitBlock(Old: ParentBB, SplitPt: SeqStartI, DT, LI, MSSAU: nullptr, BBName: "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(Old: CGStartBB, SplitPt: &*CodeGenIP, DT, LI);
1146 assert(SeqStartBB != nullptr && "SeqStartBB should not be null");
1147 CGStartBB->getTerminator()->setSuccessor(Idx: 0, BB: SeqStartBB);
1148 assert(SeqEndBB != nullptr && "SeqEndBB should not be null");
1149 SeqEndBB->getTerminator()->setSuccessor(Idx: 0, BB: 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>(Val: 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(Ptr: &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(From: &I, To: LoadI);
1190 }
1191 }
1192
1193 OpenMPIRBuilder::LocationDescription Loc(ParentBB->end(), DL);
1194 OpenMPIRBuilder::InsertPointTy SeqAfterIP = cantFail(
1195 ValOrErr: OMPInfoCache.OMPBuilder.createMaster(Loc, BodyGenCB, FiniCB));
1196 cantFail(ValOrErr: OMPInfoCache.OMPBuilder.createBarrier(Loc: {SeqAfterIP, DL},
1197 Kind: OMPD_parallel));
1198
1199 UncondBrInst::Create(Target: SeqAfterBB, InsertBefore: 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(RangeOrContainer: MergableCIs)) {
1222 OR << ore::NV("OpenMPParallelMerge", CI->getDebugLoc());
1223 if (CI != MergableCIs.back())
1224 OR << ", ";
1225 }
1226 return OR << ".";
1227 };
1228
1229 emitRemark<OptimizationRemark>(I: MergableCIs.front(), RemarkName: "OMP150", RemarkCB&: 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(Old: BB, SplitPt: MergableCIs.back()->getNextNode(), DT, LI);
1238 BasicBlock *AfterBB =
1239 SplitBlock(Old: EndBB, SplitPt: &*EndBB->getFirstInsertionPt(), DT, LI);
1240 StartBB = SplitBlock(Old: BB, SplitPt: MergableCIs.front(), DT, LI, MSSAU: nullptr,
1241 BBName: "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.
1267 OpenMPIRBuilder::InsertPointTy AfterIP =
1268 cantFail(ValOrErr: OMPInfoCache.OMPBuilder.createParallel(
1269 Loc, AllocaIP, /* DeallocBlocks */ {}, BodyGenCB, PrivCB, FiniCB,
1270 IfCondition: nullptr, NumThreads: nullptr, ProcBind: OMP_PROC_BIND_default,
1271 /* IsCancellable */ false));
1272 UncondBrInst::Create(Target: AfterBB, InsertBefore: AfterIP.getNodeParent());
1273
1274 // Perform the actual outlining.
1275 OMPInfoCache.OMPBuilder.finalize(Fn: OriginalFn);
1276
1277 Function *OutlinedFn = MergableCIs.front()->getCaller();
1278 std::optional<uint64_t> WrapperCount =
1279 getMergedWrapperEntryCount(ForkCalls: MergableCIs, CallbackOpNo: CallbackCalleeOperand);
1280 // Leave the wrapper unprofiled when no callback has an entry count.
1281 if (WrapperCount)
1282 OutlinedFn->setEntryCount(Count: *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(M: *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(i: CallbackCalleeOperand);
1293 FunctionType *FT = OMPInfoCache.OMPBuilder.ParallelTask;
1294 Args.clear();
1295 Args.push_back(Elt: OutlinedFn->getArg(i: 0));
1296 Args.push_back(Elt: OutlinedFn->getArg(i: 1));
1297 for (unsigned U = CallbackFirstArgOperand, E = CI->arg_size(); U < E;
1298 ++U)
1299 Args.push_back(Elt: CI->getArgOperand(i: U));
1300
1301 CallInst *NewCI =
1302 CallInst::Create(Ty: FT, Func: Callee, Args, NameStr: "", InsertBefore: 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(I&: *NewCI, Weights: {*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(ArgNo: U))
1316 NewCI->addParamAttr(
1317 ArgNo: U - (CallbackFirstArgOperand - CallbackCalleeOperand), Attr: 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(ValOrErr: OMPInfoCache.OMPBuilder.createBarrier(
1324 Loc: {NewCI->getNextNode()->getIterator(), NewCI->getDebugLoc()},
1325 Kind: OMPD_parallel));
1326 }
1327
1328 CI->eraseFromParent();
1329 }
1330
1331 assert(OutlinedFn != OriginalFn && "Outlining failed");
1332 CGUpdater.registerOutlinedFunction(OriginalFn&: *OriginalFn, NewFn&: *OutlinedFn);
1333 CGUpdater.reanalyzeFunction(Fn&: *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: &RFI);
1344 BB2PRMap[CI->getParent()].insert(Ptr: CI);
1345
1346 return false;
1347 };
1348
1349 BB2PRMap.clear();
1350 RFI.foreachUse(SCC, CB: 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>(Val: &I))
1379 return true;
1380
1381 CallInst *CI = cast<CallInst>(Val: &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>(Val: 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(Ptr: &I)) {
1412 MergableCIs.push_back(Elt: cast<CallInst>(Val: &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(Ptr: &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(Elt: 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(RTF: OMPRTL___kmpc_fork_call);
1457 OMPInfoCache.recollectUsesForFunction(RTF: OMPRTL___kmpc_barrier);
1458 OMPInfoCache.recollectUsesForFunction(RTF: OMPRTL___kmpc_master);
1459 OMPInfoCache.recollectUsesForFunction(RTF: 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 Val: CI->getArgOperand(i: CallbackCalleeOperand)->stripPointerCasts());
1482 if (!Fn)
1483 return false;
1484 if (!Fn->onlyReadsMemory())
1485 return false;
1486 if (!Fn->hasFnAttribute(Kind: 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 };
1495 emitRemark<OptimizationRemark>(I: CI, RemarkName: "OMP160", RemarkCB&: Remark);
1496
1497 CI->eraseFromParent();
1498 Changed = true;
1499 ++NumOpenMPParallelRegionsDeleted;
1500 return true;
1501 };
1502
1503 RFI.foreachUse(SCC, CB: 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&: *F, RFI&: 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(key: &Arg)) {
1545 GTIdArg = &Arg;
1546 break;
1547 }
1548 Changed |= deduplicateRuntimeCalls(
1549 F&: *F, RFI&: OMPInfoCache.RFIs[OMPRTL___kmpc_global_thread_num], ReplVal: 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(Name: "__llvm_rpc_client")) {
1562 if (GV->hasNUsesOrMore(N: 1))
1563 return false;
1564
1565 GV->replaceAllUsesWith(V: PoisonValue::get(T: 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: &RFI);
1583 if (!RTCall)
1584 return false;
1585
1586 OffloadArray OffloadArrays[3];
1587 if (!getValuesInOffloadArrays(RuntimeCall&: *RTCall, OAs: 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(RuntimeCall&: *RTCall);
1595 if (WaitMovementPoint)
1596 WasSplit = splitTargetDataBeginRTC(RuntimeCall&: *RTCall, WaitMovementPoint&: *WaitMovementPoint);
1597
1598 Changed |= WasSplit;
1599 return WasSplit;
1600 };
1601 if (OMPInfoCache.runtimeFnsAvailable(
1602 Fns: {OMPRTL___tgt_target_data_begin_mapper_issue,
1603 OMPRTL___tgt_target_data_begin_mapper_wait}))
1604 RFI.foreachUse(SCC, CB: 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: &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 };
1619 emitRemark<OptimizationRemarkMissed>(I: CI, RemarkName: "OMP112", RemarkCB&: Remark);
1620 }
1621
1622 return false;
1623 };
1624
1625 RFI.foreachUse(SCC, CB: 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,
1631 MutableArrayRef<OffloadArray> OAs) {
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(i: OffloadArray::BasePtrsArgNum);
1644 // i8** %offload_ptrs.
1645 Value *PtrsArg = RuntimeCall.getArgOperand(i: OffloadArray::PtrsArgNum);
1646 // i8** %offload_sizes.
1647 Value *SizesArg = RuntimeCall.getArgOperand(i: OffloadArray::SizesArgNum);
1648
1649 // Get values stored in **offload_baseptrs.
1650 auto *V = getUnderlyingObject(V: BasePtrsArg);
1651 if (!isa<AllocaInst>(Val: V))
1652 return false;
1653 auto *BasePtrsArray = cast<AllocaInst>(Val: V);
1654 if (!OAs[0].initialize(Array&: *BasePtrsArray, Before&: RuntimeCall))
1655 return false;
1656
1657 // Get values stored in **offload_baseptrs.
1658 V = getUnderlyingObject(V: PtrsArg);
1659 if (!isa<AllocaInst>(Val: V))
1660 return false;
1661 auto *PtrsArray = cast<AllocaInst>(Val: V);
1662 if (!OAs[1].initialize(Array&: *PtrsArray, Before&: RuntimeCall))
1663 return false;
1664
1665 // Get values stored in **offload_sizes.
1666 V = getUnderlyingObject(V: SizesArg);
1667 // If it's a [constant] global array don't analyze it.
1668 if (isa<GlobalValue>(Val: V))
1669 return isa<Constant>(Val: V);
1670 if (!isa<AllocaInst>(Val: V))
1671 return false;
1672
1673 auto *SizesArray = cast<AllocaInst>(Val: V);
1674 if (!OAs[2].initialize(Array&: *SizesArray, Before&: 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(O&: 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(O&: 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(O&: 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 Ty: IRBuilder.AsyncInfo, /*ArraySize=*/nullptr, Name: "handle");
1754 Handle =
1755 IRBuilder.Builder.CreateAddrSpaceCast(V: Handle, DestTy: 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, FnID: 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(Elt: Arg.get());
1767 Args.push_back(Elt: Handle);
1768
1769 CallInst *IssueCallsite = CallInst::Create(Func: IssueDecl, Args, /*NameStr=*/"",
1770 InsertBefore: RuntimeCall.getIterator());
1771 OMPInfoCache.setCallingConvention(Callee: IssueDecl, CI: 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, FnID: OMPRTL___tgt_target_data_begin_mapper_wait);
1778
1779 Value *WaitParams[2] = {
1780 IssueCallsite->getArgOperand(
1781 i: OffloadArray::DeviceIDArgNum), // device_id.
1782 Handle // handle to wait on.
1783 };
1784 CallInst *WaitCallsite = CallInst::Create(
1785 Func: WaitDecl, Args: WaitParams, /*NameStr=*/"", InsertBefore: WaitMovementPoint.getIterator());
1786 OMPInfoCache.setCallingConvention(Callee: WaitDecl, CI: 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>(Val: 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: &RFI);
1817 if (!CI || &F != &Caller)
1818 return false;
1819 Ident = combinedIdentStruct(CurrentIdent: Ident, NextIdent: CI->getArgOperand(i: 0),
1820 /* GlobalOnly */ true, SingleChoice);
1821 return false;
1822 };
1823 RFI.foreachUse(SCC, CB: 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 Loc: {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(SrcLocStr: 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(i: 0)->getType() != OMPInfoCache.OMPBuilder.IdentPtr)
1865 return false;
1866 for (unsigned U = 1; U < NumArgs; ++U)
1867 if (isa<Instruction>(Val: CB.getArgOperand(i: 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&: *U, RFI: &RFI)) {
1880 if (IP)
1881 IP = DT->findNearestCommonDominator(I1: IP, I2: 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>(Val: ReplVal)->moveBefore(InsertPos: 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>(Val: ReplVal)) {
1900 if (!CI->arg_empty() &&
1901 CI->getArgOperand(i: 0)->getType() == OMPInfoCache.OMPBuilder.IdentPtr) {
1902 Value *Ident = getCombinedIdentFromCallUsesIn(RFI, F,
1903 /* GlobalOnly */ true);
1904 CI->setArgOperand(i: 0, v: Ident);
1905 }
1906 }
1907
1908 bool Changed = false;
1909 auto ReplaceAndDeleteCB = [&](Use &U, Function &Caller) {
1910 CallInst *CI = getCallIfRegularCall(U, RFI: &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())
1920 emitRemark<OptimizationRemark>(I: CI, RemarkName: "OMP170", RemarkCB&: Remark);
1921 else
1922 emitRemark<OptimizationRemark>(F: &F, RemarkName: "OMP170", RemarkCB&: Remark);
1923
1924 CI->replaceAllUsesWith(V: ReplVal);
1925 CI->eraseFromParent();
1926 ++NumOpenMPRuntimeCallsDeduplicated;
1927 Changed = true;
1928 return true;
1929 };
1930 RFI.foreachUse(SCC, CB: 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(i: ArgNo);
1949 if (CI == &RefCI || GTIdArgs.count(key: ArgOp) ||
1950 getCallIfRegularCall(
1951 V&: *ArgOp, RFI: &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>(Val: U.getUser()))
1963 if (CI->isArgOperand(U: &U))
1964 if (Function *Callee = CI->getCalledFunction())
1965 if (CallArgOpIsGTId(*Callee, U.getOperandNo(), *CI))
1966 GTIdArgs.insert(X: Callee->getArg(i: 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, CB: [&](Use &U, Function &F) {
1974 if (CallInst *CI = getCallIfRegularCall(U, RFI: &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(F&: *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(Prefix: "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(Prefix: "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(key: &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(Fn&: 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 };
2131 emitRemark<OptimizationRemarkAnalysis>(F: &F, RemarkName: "OMP100", RemarkCB&: Remark);
2132
2133 return nullptr;
2134 }
2135 }
2136
2137 auto GetUniqueKernelForUse = [&](const Use &U) -> Kernel {
2138 if (auto *Cmp = dyn_cast<ICmpInst>(Val: U.getUser())) {
2139 // Allow use in equality comparisons.
2140 if (Cmp->isEquality())
2141 return getUniqueKernelFor(I&: *Cmp);
2142 return nullptr;
2143 }
2144 if (auto *CB = dyn_cast<CallBase>(Val: U.getUser())) {
2145 // Allow direct calls.
2146 if (CB->isCallee(U: &U))
2147 return getUniqueKernelFor(I&: *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(V&: *U.getUser(), RFI: &KernelParallelRFI))
2153 return getUniqueKernelFor(I&: *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, CB: [&](const Use &U) {
2163 PotentialKernels.insert(Ptr: 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&: *F, CB: [&](Use &U) {
2198 if (auto *CB = dyn_cast<CallBase>(Val: U.getUser()))
2199 if (CB->isCallee(U: &U)) {
2200 ++NumDirectCalls;
2201 return;
2202 }
2203
2204 if (isa<ICmpInst>(Val: U.getUser())) {
2205 ToBeReplacedStateMachineUses.push_back(Elt: &U);
2206 return;
2207 }
2208
2209 // Find wrapper functions that represent parallel kernels.
2210 CallInst *CI =
2211 OpenMPOpt::getCallIfRegularCall(V&: *U.getUser(), RFI: &KernelParallelRFI);
2212 const unsigned int WrapperFunctionArgNo = 6;
2213 if (!KernelParallelUse && CI &&
2214 CI->getArgOperandNo(U: &U) == WrapperFunctionArgNo) {
2215 KernelParallelUse = true;
2216 ToBeReplacedStateMachineUses.push_back(Elt: &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 };
2237 emitRemark<OptimizationRemarkAnalysis>(F, RemarkName: "OMP101", RemarkCB&: Remark);
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&: *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 };
2249 emitRemark<OptimizationRemarkAnalysis>(F, RemarkName: "OMP102", RemarkCB&: Remark);
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(C&: M.getContext());
2260
2261 auto *ID = new GlobalVariable(
2262 M, Int8Ty, /* isConstant */ true, GlobalValue::PrivateLinkage,
2263 UndefValue::get(T: Int8Ty), F->getName() + ".ID");
2264
2265 for (Use *U : ToBeReplacedStateMachineUses)
2266 U->set(ConstantExpr::getPointerBitCastOrAddrSpaceCast(
2267 C: ID, Ty: 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>(Val: U);
2291 if (!CI || CI->getCalledOperand() != KernelParallelRFI.Declaration ||
2292 CI->arg_size() <= WrapperFunctionArgNo)
2293 continue;
2294
2295 Value *Wrapper = CI->getArgOperand(i: WrapperFunctionArgNo);
2296 if (isa<ConstantPointerNull>(Val: Wrapper))
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(F&: *CI->getFunction());
2306 if (!K || !OMPInfoCache.SPMDizedKernels.contains(Ptr: K))
2307 continue;
2308
2309 CI->setArgOperand(
2310 i: WrapperFunctionArgNo,
2311 v: ConstantPointerNull::get(T: cast<PointerType>(Val: Wrapper->getType())));
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(KV: std::make_pair(x&: CI, y: CI->getArgOperand(i: 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(KV: std::make_pair(x: &I, y&: *ReplVal)).second)
2410 HasChanged = ChangeStatus::CHANGED;
2411
2412 return true;
2413 };
2414
2415 // Track all changes of an ICV.
2416 SetterRFI.foreachUse(CB: TrackValues, F);
2417
2418 bool UsedAssumedInformation = false;
2419 A.checkForAllInstructions(Pred: CallCheck, QueryingAA: *this, Opcodes: {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(Key: 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>(Val: &I);
2439 if (!CB || CB->hasFnAttr(Kind: "no_openmp") ||
2440 CB->hasFnAttr(Kind: "no_openmp_routines") ||
2441 CB->hasFnAttr(Kind: "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(Val: &I))
2456 return ICVReplacementValuesMap[ICV].lookup(Val: &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 QueryingAA: *this, IRP: IRPosition::callsite_returned(CB: *CB), DepClass: DepClassTy::REQUIRED);
2467
2468 if (ICVTrackingAA->isAssumedTracked()) {
2469 std::optional<Value *> URV =
2470 ICVTrackingAA->getUniqueReplacementValue(ICV);
2471 if (!URV || (*URV && AA::isValidAtPosition(VAC: AA::ValueAndContext(**URV, I),
2472 InfoCache&: 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(Val: I))
2492 return ValuesMap.lookup(Val: I);
2493
2494 SmallVector<const Instruction *, 16> Worklist;
2495 SmallPtrSet<const Instruction *, 16> Visited;
2496 Worklist.push_back(Elt: I);
2497
2498 std::optional<Value *> ReplVal;
2499
2500 while (!Worklist.empty()) {
2501 const Instruction *CurrInst = Worklist.pop_back_val();
2502 if (!Visited.insert(Ptr: 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(Val: CurrInst)) {
2511 std::optional<Value *> NewReplVal = ValuesMap.lookup(Val: 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, I: *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(BB: CurrBB))
2548 Worklist.push_back(Elt: 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 QueryingAA: *this, IRP: IRPosition::function(F: *getAnchorScope()), DepClass: 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: &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(Pred: CheckReturnInst, QueryingAA: *this, Opcodes: {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(IRP: IRPosition::inst(I: *getCtxI()), NV&: **ReplVal);
2653 A.deleteAfterManifest(I&: *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 QueryingAA: *this, IRP: IRPosition::function(F: *getAnchorScope()), DepClass: 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(ICV: AssociatedICV, I: 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 QueryingAA: *this, IRP: IRPosition::returned(F: *getAssociatedFunction()),
2728 DepClass: 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(BB: 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(val: InitialThreadBlocks) + "/" +
2783 std::to_string(val: AlignedBlocks) + " of " +
2784 std::to_string(val: 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(Ptr: CB);
2823 A.deleteAfterManifest(I&: *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(X: LastCB))
2834 continue;
2835 if (LastCB->getFunction() != getAnchorScope())
2836 continue;
2837 if (!hasFunctionEndAsUniqueSuccessor(BB: LastCB->getParent()))
2838 continue;
2839 if (!DeletedBarriers.count(Ptr: LastCB)) {
2840 ++NumBarriersEliminated;
2841 A.deleteAfterManifest(I&: *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(in_start: LastED.AlignedBarriers.begin(),
2849 in_end: 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(I&: *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(Fn&: *getAnchorScope()))
2865 HandleAlignedBarrier(nullptr);
2866
2867 return Changed;
2868 }
2869
2870 bool isNoOpFence(const FenceInst &FI) const override {
2871 return getState().isValidState() && !NonNoOpFences.count(Ptr: &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(Val: &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>(Val: CurI);
2915 if (!CB)
2916 continue;
2917 if (CB != &I && AlignedBarriers.contains(key: const_cast<CallBase *>(CB)))
2918 return true;
2919 const auto &It = CEDMap.find(Val: {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(Val: 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>(Val: CurI);
2934 if (!CB)
2935 continue;
2936 if (CB != &I && AlignedBarriers.contains(key: const_cast<CallBase *>(CB)))
2937 return true;
2938 const auto &It = CEDMap.find(Val: {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(Val: nullptr).IsReachedFromAlignedBarrierOnly;
2955 if (!llvm::all_of(Range: predecessors(BB), P: [&](const BasicBlock *PredBB) {
2956 return BEDMap.lookup(Val: 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(Val: &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(Val: {&CB, PRE}), CEDMap.lookup(Val: {&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(i: 0) != &SuccessorBB)
2991 return false;
2992
2993 auto *Cmp = dyn_cast<CmpInst>(Val: Edge->getCondition());
2994 if (!Cmp || !Cmp->isTrueWhenEqual() || !Cmp->isEquality())
2995 return false;
2996
2997 ConstantInt *C = dyn_cast<ConstantInt>(Val: Cmp->getOperand(i_nocapture: 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>(Val: Cmp->getOperand(i_nocapture: 0));
3004 auto &OMPInfoCache = static_cast<OMPInformationCache &>(A.getInfoCache());
3005 auto &RFI = OMPInfoCache.RFIs[OMPRTL___kmpc_target_init];
3006 CB = CB ? OpenMPOpt::getCallIfRegularCall(V&: *CB, RFI: &RFI) : nullptr;
3007 if (!CB)
3008 return false;
3009 ConstantStruct *KernelEnvC =
3010 KernelInfo::getKernelEnvironementFromKernelInitCB(KernelInitCB: CB);
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>(Val: Cmp->getOperand(i_nocapture: 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>(Val: Cmp->getOperand(i_nocapture: 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, AI&: *EA);
3059
3060 for (auto *AB : PredED.AlignedBarriers)
3061 ED.addAlignedBarrier(A, CB&: *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(R&: ED.IsExecutedByInitialThreadOnly,
3071 V: InitialEdgeOnly || (PredED.IsExecutedByInitialThreadOnly &&
3072 ED.IsExecutedByInitialThreadOnly));
3073
3074 Changed |= setAndRecord(R&: ED.IsReachedFromAlignedBarrierOnly,
3075 V: ED.IsReachedFromAlignedBarrierOnly &&
3076 PredED.IsReachedFromAlignedBarrierOnly);
3077 Changed |= setAndRecord(R&: ED.EncounteredNonLocalSideEffect,
3078 V: 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) {
3090 SmallVector<std::pair<ExecutionDomainTy, ExecutionDomainTy>, 4> CallSiteEDs;
3091 auto PredForCallSite = [&](AbstractCallSite ACS) {
3092 const auto *EDAA = A.getAAFor<AAExecutionDomain>(
3093 QueryingAA: *this, IRP: IRPosition::function(F: *ACS.getInstruction()->getFunction()),
3094 DepClass: DepClassTy::OPTIONAL);
3095 if (!EDAA || !EDAA->getState().isValidState())
3096 return false;
3097 CallSiteEDs.emplace_back(
3098 Args: EDAA->getExecutionDomain(CB: *cast<CallBase>(Val: ACS.getInstruction())));
3099 return true;
3100 };
3101
3102 ExecutionDomainTy ExitED;
3103 bool AllCallSitesKnown;
3104 if (A.checkForAllCallSites(Pred: PredForCallSite, QueryingAA: *this,
3105 /* RequiresAllCallSites */ RequireAllCallSites: true,
3106 UsedAssumedInformation&: AllCallSitesKnown)) {
3107 for (const auto &[CSInED, CSOutED] : CallSiteEDs) {
3108 mergeInPredecessor(A, ED&: EntryBBED, PredED: 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(Fn&: *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(R&: FnED.IsReachedFromAlignedBarrierOnly,
3132 V: FnED.IsReachedFromAlignedBarrierOnly &
3133 EntryBBED.IsReachedFromAlignedBarrierOnly);
3134 Changed |= setAndRecord(R&: FnED.IsReachingAlignedBarrierOnly,
3135 V: FnED.IsReachingAlignedBarrierOnly &
3136 ExitED.IsReachingAlignedBarrierOnly);
3137 Changed |= setAndRecord(R&: FnED.IsExecutedByInitialThreadOnly,
3138 V: 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(X: &CB);
3151 // First, update the barrier ED kept in the separate CEDMap.
3152 auto &CallInED = CEDMap[{&CB, PRE}];
3153 Changed |= mergeInPredecessor(A, ED&: CallInED, PredED: 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, ED&: CallOutED, PredED: ED);
3163 };
3164
3165 auto *LivenessAA =
3166 A.getAAFor<AAIsDead>(QueryingAA: *this, IRP: getIRPosition(), DepClass: DepClassTy::OPTIONAL);
3167
3168 Function *F = getAnchorScope();
3169 BasicBlock &EntryBB = F->getEntryBlock();
3170 bool IsKernel = omp::isOpenMPKernel(Fn&: *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, EntryBBED&: ED);
3185 } else {
3186 // For live non-entry blocks we only propagate
3187 // information via live edges.
3188 if (LivenessAA && LivenessAA->isAssumedDead(BB: &BB))
3189 continue;
3190
3191 for (auto *PredBB : predecessors(BB: &BB)) {
3192 if (LivenessAA && LivenessAA->isEdgeDead(From: PredBB, To: &BB))
3193 continue;
3194 bool InitialEdgeOnly = isInitialThreadOnlyEdge(
3195 A, Edge: dyn_cast<CondBrInst>(Val: PredBB->getTerminator()), SuccessorBB&: BB);
3196 mergeInPredecessor(A, ED, PredED: 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, QueryingAA: *this, LivenessAA, UsedAssumedInformation,
3205 /* CheckBBLivenessOnly */ false, DepClass: 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>(Val: &I)) {
3212 if (auto *AI = dyn_cast_or_null<AssumeInst>(Val: II)) {
3213 ED.addAssumeInst(A, AI&: *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>(Val: &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(Ptr: FI);
3246 }
3247
3248 auto *CB = dyn_cast<CallBase>(Val: &I);
3249 bool IsNoSync = AA::isNoSyncInst(A, I, QueryingAA: *this);
3250 bool IsAlignedBarrier =
3251 !IsNoSync && CB &&
3252 AANoSync::isAlignedBarrier(CB: *CB, ExecutedAligned: 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>(Val: &I)) {
3270 if (!ED.EncounteredNonLocalSideEffect &&
3271 AA::isPotentiallyAffectedByBarrier(A, I, QueryingAA: *this))
3272 ED.EncounteredNonLocalSideEffect = true;
3273 if (!IsNoSync) {
3274 ED.IsReachedFromAlignedBarrierOnly = false;
3275 SyncInstWorklist.push_back(Elt: &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, ED&: CallInED, PredED: 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.
3288 Function *Callee = CB->getCalledFunction();
3289 if (!IsNoSync && Callee && !Callee->isDeclaration()) {
3290 const auto *EDAA = A.getAAFor<AAExecutionDomain>(
3291 QueryingAA: *this, IRP: IRPosition::function(F: *Callee), DepClass: 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(R&: CallInED.IsReachingAlignedBarrierOnly, V: false);
3306 SyncInstWorklist.push_back(Elt: &I);
3307 }
3308 if (CalleeED.IsReachedFromAlignedBarrierOnly)
3309 mergeInPredecessorBarriersAndAssumptions(A, ED, PredED: CalleeED);
3310 auto &CallOutED = CEDMap[{CB, POST}];
3311 Changed |= mergeInPredecessor(A, ED&: CallOutED, PredED: ED);
3312 continue;
3313 }
3314 }
3315 if (!IsNoSync) {
3316 ED.IsReachedFromAlignedBarrierOnly = false;
3317 Changed |= setAndRecord(R&: CallInED.IsReachingAlignedBarrierOnly, V: false);
3318 SyncInstWorklist.push_back(Elt: &I);
3319 }
3320 AlignedBarrierLastInBlock &= ED.IsReachedFromAlignedBarrierOnly;
3321 ED.EncounteredNonLocalSideEffect |= !CB->doesNotAccessMemory();
3322 auto &CallOutED = CEDMap[{CB, POST}];
3323 Changed |= mergeInPredecessor(A, ED&: CallOutED, PredED: 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 QueryingAA: *this, IRP: IRPosition::callsite_function(CB: *CB), DepClass: DepClassTy::OPTIONAL);
3334
3335 auto AccessPred = [&](const Instruction *I, const Value *Ptr,
3336 AAMemoryLocation::AccessKind,
3337 AAMemoryLocation::MemoryLocationsKind) {
3338 return !AA::isPotentiallyAffectedByBarrier(A, Ptrs: {Ptr}, QueryingAA: *this, CtxI: I);
3339 };
3340 if (MemAA && MemAA->getState().isValidState() &&
3341 MemAA->checkForAllAccessesToMemoryKind(
3342 Pred: AccessPred, MLK: AAMemoryLocation::ALL_LOCATIONS))
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>(Val: &I))
3351 if (LI->hasMetadata(KindID: LLVMContext::MD_invariant_load))
3352 continue;
3353
3354 if (!ED.EncounteredNonLocalSideEffect &&
3355 AA::isPotentiallyAffectedByBarrier(A, I, QueryingAA: *this))
3356 ED.EncounteredNonLocalSideEffect = true;
3357 }
3358
3359 bool IsEndAndNotReachingAlignedBarriersOnly = false;
3360 if (!isa<UnreachableInst>(Val: BB.getTerminator()) &&
3361 !BB.getTerminator()->getNumSuccessors()) {
3362
3363 Changed |= mergeInPredecessor(A, ED&: InterProceduralED, PredED: ED);
3364
3365 auto &FnED = BEDMap[nullptr];
3366 if (IsKernel && !IsExplicitlyAligned)
3367 FnED.IsReachingAlignedBarrierOnly = false;
3368 Changed |= mergeInPredecessor(A, ED&: FnED, PredED: ED);
3369
3370 if (!FnED.IsReachingAlignedBarrierOnly) {
3371 IsEndAndNotReachingAlignedBarriersOnly = true;
3372 SyncInstWorklist.push_back(Elt: BB.getTerminator());
3373 auto &BBED = BEDMap[&BB];
3374 Changed |= setAndRecord(R&: BBED.IsReachingAlignedBarrierOnly, V: 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>(Val: CurInst);
3407 if (!CB)
3408 continue;
3409 auto &CallOutED = CEDMap[{CB, POST}];
3410 Changed |= setAndRecord(R&: CallOutED.IsReachingAlignedBarrierOnly, V: false);
3411 auto &CallInED = CEDMap[{CB, PRE}];
3412 HitAlignedBarrierOrKnownEnd =
3413 AlignedBarriers.count(key: CB) || !CallInED.IsReachingAlignedBarrierOnly;
3414 if (HitAlignedBarrierOrKnownEnd)
3415 break;
3416 Changed |= setAndRecord(R&: CallInED.IsReachingAlignedBarrierOnly, V: false);
3417 }
3418 if (HitAlignedBarrierOrKnownEnd)
3419 continue;
3420 BasicBlock *SyncBB = SyncInst->getParent();
3421 for (auto *PredBB : predecessors(BB: SyncBB)) {
3422 if (LivenessAA && LivenessAA->isEdgeDead(From: PredBB, To: SyncBB))
3423 continue;
3424 if (!Visited.insert(X: PredBB))
3425 continue;
3426 auto &PredED = BEDMap[PredBB];
3427 if (setAndRecord(R&: PredED.IsReachingAlignedBarrierOnly, V: false)) {
3428 Changed = true;
3429 SyncInstWorklist.push_back(Elt: PredBB->getTerminator());
3430 }
3431 }
3432 if (SyncBB != &EntryBB)
3433 continue;
3434 Changed |=
3435 setAndRecord(R&: InterProceduralED.IsReachingAlignedBarrierOnly, V: 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(val: 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) {
3492 SmallVector<CallBase *, 4> FreeCalls;
3493 for (auto *U : CB->users()) {
3494 CallBase *C = dyn_cast<CallBase>(Val: U);
3495 if (C && C->getCalledFunction() == FreeRFI.Declaration)
3496 FreeCalls.push_back(Elt: C);
3497 }
3498
3499 if (FreeCalls.size() != 1)
3500 continue;
3501
3502 PotentialRemovedFreeCalls.insert(Ptr: 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
3517 Attributor::SimplifictionCallbackTy SCB =
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&: *F);
3524 if (!Uses)
3525 return;
3526
3527 for (Use *U : *Uses)
3528 if (CallBase *CB = dyn_cast<CallBase>(Val: U->getUser())) {
3529 MallocCalls.insert(X: CB);
3530 A.registerSimplificationCallback(IRP: IRPosition::callsite_returned(CB: *CB),
3531 CB: SCB);
3532 }
3533
3534 findPotentialRemovedFreeCalls(A);
3535 }
3536
3537 bool isAssumedHeapToShared(CallBase &CB) const override {
3538 return isValidState() && MallocCalls.count(key: &CB);
3539 }
3540
3541 bool isAssumedHeapToSharedRemovedFree(CallBase &CB) const override {
3542 return isValidState() && PotentialRemovedFreeCalls.count(Ptr: &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>(IRP: IRPosition::function(F: *F), QueryingAA: this,
3554 DepClass: 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: *CB))
3560 continue;
3561
3562 // Find the unique free call to remove it.
3563 SmallVector<CallBase *, 4> FreeCalls;
3564 for (auto *U : CB->users()) {
3565 CallBase *C = dyn_cast<CallBase>(Val: U);
3566 if (C && C->getCalledFunction() == FreeCall.Declaration)
3567 FreeCalls.push_back(Elt: C);
3568 }
3569 if (FreeCalls.size() != 1)
3570 continue;
3571
3572 auto *AllocSize = cast<ConstantInt>(Val: CB->getArgOperand(i: 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(C&: M->getContext());
3591 Type *Int8ArrTy = ArrayType::get(ElementType: Int8Ty, NumElements: AllocSize->getZExtValue());
3592 auto *SharedMem = new GlobalVariable(
3593 *M, Int8ArrTy, /* IsConstant */ false, GlobalValue::InternalLinkage,
3594 PoisonValue::get(T: Int8ArrTy), CB->getName() + "_shared", nullptr,
3595 GlobalValue::NotThreadLocal,
3596 static_cast<unsigned>(AddressSpace::Shared));
3597 auto *NewBuffer = ConstantExpr::getPointerCast(
3598 C: SharedMem, Ty: PointerType::getUnqual(C&: 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>(I: CB, RemarkName: "OMP111", RemarkCB&: 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(IRP: IRPosition::callsite_returned(CB: *CB), NV&: *NewBuffer);
3614 A.deleteAfterManifest(I&: *CB);
3615 A.deleteAfterManifest(I&: *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>(Val: U)) {
3640 if (CB->getCaller() != F)
3641 continue;
3642 if (!MallocCalls.count(key: CB))
3643 continue;
3644 if (!isa<ConstantInt>(Val: CB->getArgOperand(i: 0))) {
3645 MallocCalls.remove(X: CB);
3646 continue;
3647 }
3648 const auto *ED = A.getAAFor<AAExecutionDomain>(
3649 QueryingAA: *this, IRP: IRPosition::function(F: *F), DepClass: DepClassTy::REQUIRED);
3650 if (!ED || !ED->isExecutedByInitialThreadOnly(I: *CB))
3651 MallocCalls.remove(X: 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(val: ReachedKnownParallelRegions.size())
3692 : "<invalid>") +
3693 ", #Unknown PRs: " +
3694 (ReachedUnknownParallelRegions.isValidState()
3695 ? std::to_string(val: ReachedUnknownParallelRegions.size())
3696 : "<invalid>") +
3697 ", #Reaching Kernels: " +
3698 (ReachingKernelEntries.isValidState()
3699 ? std::to_string(val: ReachingKernelEntries.size())
3700 : "<invalid>") +
3701 ", #ParLevels: " +
3702 (ParallelLevels.isValidState()
3703 ? std::to_string(val: 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>(Val: &I);
3726 if (!FI)
3727 return false;
3728 SyncScope::ID SS = FI->getSyncScopeID();
3729 if (SS == SyncScope::SingleThread)
3730 return false;
3731 if (SS == SyncScope::System)
3732 return true;
3733 std::optional<StringRef> Name = FI->getContext().getSyncScopeName(Id: SS);
3734 if (!Name)
3735 return true;
3736 auto Parsed =
3737 parseAtomicScopeIRString(T: FI->getModule()->getTargetTriple(), Name: *Name);
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) {
3766 Constant *NewKernelEnvC = ConstantFoldInsertValueInstruction(
3767 Agg: KernelEnvC, Val: ConfigC, Idxs: {KernelInfo::ConfigurationIdx});
3768 assert(NewKernelEnvC && "Failed to create new kernel environment");
3769 KernelEnvC = cast<ConstantStruct>(Val: 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)
3784 KERNEL_ENVIRONMENT_CONFIGURATION_SETTER(ExecMode)
3785 KERNEL_ENVIRONMENT_CONFIGURATION_SETTER(MinThreads)
3786 KERNEL_ENVIRONMENT_CONFIGURATION_SETTER(MaxThreads)
3787 KERNEL_ENVIRONMENT_CONFIGURATION_SETTER(MinTeams)
3788 KERNEL_ENVIRONMENT_CONFIGURATION_SETTER(MaxTeams)
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: &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 CB: [&](Use &U, Function &) {
3820 StoreCallBase(U, InitRFI, KernelInitCB);
3821 return false;
3822 },
3823 F: Fn);
3824 DeinitRFI.foreachUse(
3825 CB: [&](Use &U, Function &) {
3826 StoreCallBase(U, DeinitRFI, KernelDeinitCB);
3827 return false;
3828 },
3829 F: 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(Elem: Fn);
3837 IsKernelEntry = true;
3838
3839 KernelEnvC =
3840 KernelInfo::getKernelEnvironementFromKernelInitCB(KernelInitCB);
3841 GlobalVariable *KernelEnvGV =
3842 KernelInfo::getKernelEnvironementGVFromKernelInitCB(KernelInitCB);
3843
3844 Attributor::GlobalVariableSimplifictionCallbackTy
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(FromAA: *this, ToAA: *AA, DepClass: DepClassTy::OPTIONAL);
3853 }
3854 return KernelEnvC;
3855 };
3856
3857 A.registerGlobalVariableSimplificationCallback(
3858 GV: *KernelEnvGV, CB: KernelConfigurationSimplifyCB);
3859
3860 // We cannot change to SPMD mode if the runtime functions aren't availible.
3861 bool CanChangeToSPMD = OMPInfoCache.runtimeFnsAvailable(
3862 Fns: {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 Ty: ExecModeC->getIntegerType(),
3870 V: ExecModeC->getSExtValue() | OMP_TGT_EXEC_MODE_GENERIC_SPMD);
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(C&: Fn->getContext());
3882 auto [MinThreads, MaxThreads] =
3883 OpenMPIRBuilder::readThreadBoundsForKernel(T, Kernel&: *Fn);
3884 if (MinThreads)
3885 setMinThreadsOfKernelEnvironment(ConstantInt::get(Ty: Int32Ty, V: MinThreads));
3886 if (MaxThreads)
3887 setMaxThreadsOfKernelEnvironment(ConstantInt::get(Ty: Int32Ty, V: MaxThreads));
3888 auto [MinTeams, MaxTeams] =
3889 OpenMPIRBuilder::readTeamBoundsForKernel(T, Kernel&: *Fn);
3890 if (MinTeams)
3891 setMinTeamsOfKernelEnvironment(ConstantInt::get(Ty: Int32Ty, V: MinTeams));
3892 if (MaxTeams)
3893 setMaxTeamsOfKernelEnvironment(ConstantInt::get(Ty: Int32Ty, V: MaxTeams));
3894
3895 ConstantInt *MayUseNestedParallelismC =
3896 KernelInfo::getMayUseNestedParallelismFromKernelEnvironment(KernelEnvC);
3897 ConstantInt *AssumedMayUseNestedParallelismC = ConstantInt::get(
3898 Ty: MayUseNestedParallelismC->getIntegerType(), V: 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(Ty: UseGenericStateMachineC->getIntegerType(), V: false);
3908 setUseGenericStateMachineOfKernelEnvironment(
3909 AssumedUseGenericStateMachineC);
3910 }
3911
3912 // Register virtual uses of functions we might need to preserve.
3913 auto RegisterVirtualUse = [&](RuntimeFunction RFKind,
3914 Attributor::VirtualUseCallbackTy &CB) {
3915 if (!OMPInfoCache.RFIs[RFKind].Declaration)
3916 return;
3917 A.registerVirtualUseCallback(V: *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(FromAA: *KI, ToAA: *QueryingAA, DepClass: 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 first: S.begin(), last: S.end(),
3993 pred: [](const char C) {
3994 return !((C >= 'a' && C <= 'z') || (C >= 'A' && C <= 'Z') ||
3995 (C >= '0' && C <= '9') || C == '_');
3996 },
3997 new_value: '.');
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 =
4021 KernelInfo::getKernelEnvironementFromKernelInitCB(KernelInitCB);
4022 ConstantInt *OldUseGenericStateMachineVal =
4023 KernelInfo::getUseGenericStateMachineFromKernelEnvironment(
4024 KernelEnvC: ExistingKernelEnvC);
4025 if (!HasBuiltStateMachine)
4026 setUseGenericStateMachineOfKernelEnvironment(
4027 OldUseGenericStateMachineVal);
4028
4029 // At last, update the KernelEnvc
4030 GlobalVariable *KernelEnvGV =
4031 KernelInfo::getKernelEnvironementGVFromKernelInitCB(KernelInitCB);
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(Old: ParentBB, SplitPt: RegionEndI->getNextNode(),
4076 DT, LI, MSSAU: MSU, BBName: "region.guarded.end");
4077 BasicBlock *RegionBarrierBB =
4078 SplitBlock(Old: RegionEndBB, SplitPt: &*RegionEndBB->getFirstInsertionPt(), DT, LI,
4079 MSSAU: MSU, BBName: "region.barrier");
4080 BasicBlock *RegionExitBB =
4081 SplitBlock(Old: RegionBarrierBB, SplitPt: &*RegionBarrierBB->getFirstInsertionPt(),
4082 DT, LI, MSSAU: MSU, BBName: "region.exit");
4083 BasicBlock *RegionStartBB =
4084 SplitBlock(Old: ParentBB, SplitPt: RegionStartI, DT, LI, MSSAU: MSU, BBName: "region.guarded");
4085
4086 assert(ParentBB->getUniqueSuccessor() == RegionStartBB &&
4087 "Expected a different CFG");
4088
4089 BasicBlock *RegionCheckTidBB = SplitBlock(
4090 Old: ParentBB, SplitPt: ParentBB->getTerminator(), DT, LI, MSSAU: MSU, BBName: "region.check.tid");
4091
4092 // Register basic blocks with the Attributor.
4093 A.registerManifestAddedBasicBlock(BB&: *RegionEndBB);
4094 A.registerManifestAddedBasicBlock(BB&: *RegionBarrierBB);
4095 A.registerManifestAddedBasicBlock(BB&: *RegionExitBB);
4096 A.registerManifestAddedBasicBlock(BB&: *RegionStartBB);
4097 A.registerManifestAddedBasicBlock(BB&: *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>(Val: U.getUser());
4106 if (UsrI.getParent() != RegionStartBB)
4107 OutsideUses.push_back(Elt: &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,
4119 GlobalValue::InternalLinkage, UndefValue::get(T: I.getType()),
4120 sanitizeForGlobalName(
4121 S: (I.getName() + ".guarded.output.alloc").str()),
4122 nullptr, GlobalValue::NotThreadLocal,
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&: *U, NV&: *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(Target: RegionCheckTidBB, InsertBefore: 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(Loc: LocRegionCheckTid);
4157 FunctionCallee HardwareTidFn =
4158 OMPInfoCache.OMPBuilder.getOrCreateRuntimeFunction(
4159 M, FnID: OMPRTL___kmpc_get_hardware_thread_id_in_block);
4160 CallInst *Tid =
4161 OMPInfoCache.OMPBuilder.Builder.CreateCall(Callee: HardwareTidFn, Args: {});
4162 Tid->setDebugLoc(DL);
4163 OMPInfoCache.setCallingConvention(Callee: HardwareTidFn, CI: Tid);
4164 Value *TidCheck = OMPInfoCache.OMPBuilder.Builder.CreateIsNull(Arg: Tid);
4165 OMPInfoCache.OMPBuilder.Builder
4166 .CreateCondBr(Cond: TidCheck, True: RegionStartBB, False: 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, FnID: OMPRTL___kmpc_barrier_simple_spmd);
4174 OMPInfoCache.OMPBuilder.updateToLocation(
4175 Loc: {RegionBarrierBB->getFirstInsertionPt(), DL});
4176 CallInst *Barrier =
4177 OMPInfoCache.OMPBuilder.Builder.CreateCall(Callee: BarrierFn, Args: {Ident, Tid});
4178 OMPInfoCache.setCallingConvention(Callee: BarrierFn, CI: Barrier);
4179
4180 // Second barrier ensures workers have read broadcast values.
4181 if (HasBroadcastValues) {
4182 CallInst *Barrier =
4183 CallInst::Create(Func: BarrierFn, Args: {Ident, Tid}, NameStr: "",
4184 InsertBefore: RegionBarrierBB->getTerminator()->getIterator());
4185 Barrier->setDebugLoc(DL);
4186 OMPInfoCache.setCallingConvention(Callee: BarrierFn, CI: 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(Ptr: BB).second)
4195 continue;
4196
4197 SmallVector<std::pair<Instruction *, Instruction *>> Reorders;
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(V&: *I, RFI: &AllocSharedRFI))
4205 continue;
4206 // Nothing tracked is sunk across a strict fence.
4207 if (isStrictFence(I: *I) || !I->user_empty() ||
4208 !SPMDCompatibilityTracker.contains(Elem: I)) {
4209 LastEffect = nullptr;
4210 continue;
4211 }
4212 if (LastEffect)
4213 Reorders.push_back(Elt: {I, LastEffect});
4214 LastEffect = &*IP;
4215 }
4216 for (auto &Reorder : Reorders)
4217 Reorder.first->moveBefore(InsertPos: Reorder.second->getIterator());
4218 }
4219
4220 SmallVector<std::pair<Instruction *, Instruction *>, 4> GuardedRegions;
4221
4222 for (Instruction *GuardedI : SPMDCompatibilityTracker) {
4223 BasicBlock *BB = GuardedI->getParent();
4224 auto *CalleeAA = A.lookupAAFor<AAKernelInfo>(
4225 IRP: IRPosition::function(F: *GuardedI->getFunction()), QueryingAA: nullptr,
4226 DepClass: DepClassTy::NONE);
4227 assert(CalleeAA != nullptr && "Expected Callee AAKernelInfo");
4228 auto &CalleeAAFunction = *cast<AAKernelInfoFunction>(Val: CalleeAA);
4229 // Continue if instruction is already guarded.
4230 if (CalleeAAFunction.getGuardedInstructions().contains(Ptr: 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(Elem: &I))
4238 CalleeAAFunction.getGuardedInstructions().insert(Ptr: &I);
4239 if (GuardedRegionStart) {
4240 GuardedRegions.push_back(
4241 Elt: std::make_pair(x&: GuardedRegionStart, y&: 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(Elem: &I)) {
4251 CalleeAAFunction.getGuardedInstructions().insert(Ptr: &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 Elt: std::make_pair(x&: GuardedRegionStart, y&: 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 I: KernelInitCB->getNextNode(), BBName: "main.thread.user_code");
4292 BasicBlock *ReturnBB =
4293 BasicBlock::Create(Context&: Ctx, Name: "exit.threads", Parent: Kernel, InsertBefore: UserCodeBB);
4294
4295 // Register blocks with attributor:
4296 A.registerManifestAddedBasicBlock(BB&: *InitBB);
4297 A.registerManifestAddedBasicBlock(BB&: *UserCodeBB);
4298 A.registerManifestAddedBasicBlock(BB&: *ReturnBB);
4299
4300 // Debug location:
4301 const DebugLoc &DLoc = KernelInitCB->getDebugLoc();
4302 ReturnInst::Create(C&: Ctx, InsertAtEnd: 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, FnID: OMPRTL___kmpc_get_hardware_thread_id_in_block);
4311
4312 // Get thread ID in block.
4313 CallInst *ThreadIdInBlock =
4314 CallInst::Create(Func: ThreadIdInBlockFn, NameStr: "thread_id.in.block", InsertBefore: InitBB);
4315 OMPInfoCache.setCallingConvention(Callee: ThreadIdInBlockFn, CI: 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(Op: ICmpInst::ICmp, Pred: CmpInst::ICMP_NE, S1: ThreadIdInBlock,
4321 S2: ConstantInt::get(Ty: ThreadIdInBlock->getType(), V: 0),
4322 Name: "thread.is_main", InsertBefore: InitBB);
4323 IsMainThread->setDebugLoc(DLoc);
4324 CondBrInst::Create(Cond: IsMainThread, IfTrue: ReturnBB, IfFalse: UserCodeBB, InsertBefore: 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>(Val: NonCompatibleI))
4337 if (OMPInfoCache.RTLFunctions.contains(V: 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>(Val: 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>(I: NonCompatibleI, RemarkName: "OMP121",
4350 RemarkCB&: 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>(Val: 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 =
4371 KernelInfo::getKernelEnvironementFromKernelInitCB(KernelInitCB);
4372 auto *ExecModeC =
4373 KernelInfo::getExecModeFromKernelEnvironment(KernelEnvC: 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(Ty: Type::getInt32Ty(C&: Kernel->getContext()), V: 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(Ty: ExecModeC->getIntegerType(),
4398 V: 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(Ptr: Kernel);
4405
4406 auto Remark = [&](OptimizationRemark OR) {
4407 return OR << "Transformed generic-mode kernel to SPMD-mode.";
4408 };
4409 A.emitRemark<OptimizationRemark>(I: KernelInitCB, RemarkName: "OMP120", RemarkCB&: 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(Fns: {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 =
4430 KernelInfo::getKernelEnvironementFromKernelInitCB(KernelInitCB);
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 KernelEnvC: ExistingKernelEnvC);
4439 ConstantInt *ModeC =
4440 KernelInfo::getExecModeFromKernelEnvironment(KernelEnvC: 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() ||
4446 (ModeC->getSExtValue() & OMP_TGT_EXEC_MODE_SPMD))
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(Ty: UseStateMachineC->getIntegerType(), V: 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>(I: KernelInitCB, RemarkName: "OMP130", RemarkCB&: 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>(I: KernelInitCB, RemarkName: "OMP131", RemarkCB&: 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>(I: KernelInitCB, RemarkName: "OMP132", RemarkCB&: 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>(I: UnknownParallelRegionCB,
4498 RemarkName: "OMP133", RemarkCB&: 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 I: KernelInitCB->getNextNode(), BBName: "thread.user_code.check");
4537 BasicBlock *IsWorkerCheckBB =
4538 BasicBlock::Create(Context&: Ctx, Name: "is_worker_check", Parent: Kernel, InsertBefore: UserCodeEntryBB);
4539 BasicBlock *StateMachineBeginBB = BasicBlock::Create(
4540 Context&: Ctx, Name: "worker_state_machine.begin", Parent: Kernel, InsertBefore: UserCodeEntryBB);
4541 BasicBlock *StateMachineFinishedBB = BasicBlock::Create(
4542 Context&: Ctx, Name: "worker_state_machine.finished", Parent: Kernel, InsertBefore: UserCodeEntryBB);
4543 BasicBlock *StateMachineIsActiveCheckBB = BasicBlock::Create(
4544 Context&: Ctx, Name: "worker_state_machine.is_active.check", Parent: Kernel, InsertBefore: UserCodeEntryBB);
4545 BasicBlock *StateMachineIfCascadeCurrentBB =
4546 BasicBlock::Create(Context&: Ctx, Name: "worker_state_machine.parallel_region.check",
4547 Parent: Kernel, InsertBefore: UserCodeEntryBB);
4548 BasicBlock *StateMachineEndParallelBB =
4549 BasicBlock::Create(Context&: Ctx, Name: "worker_state_machine.parallel_region.end",
4550 Parent: Kernel, InsertBefore: UserCodeEntryBB);
4551 BasicBlock *StateMachineDoneBarrierBB = BasicBlock::Create(
4552 Context&: Ctx, Name: "worker_state_machine.done.barrier", Parent: Kernel, InsertBefore: UserCodeEntryBB);
4553 A.registerManifestAddedBasicBlock(BB&: *InitBB);
4554 A.registerManifestAddedBasicBlock(BB&: *UserCodeEntryBB);
4555 A.registerManifestAddedBasicBlock(BB&: *IsWorkerCheckBB);
4556 A.registerManifestAddedBasicBlock(BB&: *StateMachineBeginBB);
4557 A.registerManifestAddedBasicBlock(BB&: *StateMachineFinishedBB);
4558 A.registerManifestAddedBasicBlock(BB&: *StateMachineIsActiveCheckBB);
4559 A.registerManifestAddedBasicBlock(BB&: *StateMachineIfCascadeCurrentBB);
4560 A.registerManifestAddedBasicBlock(BB&: *StateMachineEndParallelBB);
4561 A.registerManifestAddedBasicBlock(BB&: *StateMachineDoneBarrierBB);
4562
4563 const DebugLoc &DLoc = KernelInitCB->getDebugLoc();
4564 ReturnInst::Create(C&: Ctx, InsertAtEnd: StateMachineFinishedBB)->setDebugLoc(DLoc);
4565 InitBB->getTerminator()->eraseFromParent();
4566
4567 Instruction *IsWorker =
4568 ICmpInst::Create(Op: ICmpInst::ICmp, Pred: llvm::CmpInst::ICMP_NE, S1: KernelInitCB,
4569 S2: ConstantInt::getAllOnesValue(Ty: KernelInitCB->getType()),
4570 Name: "thread.is_worker", InsertBefore: InitBB);
4571 IsWorker->setDebugLoc(DLoc);
4572 CondBrInst::Create(Cond: IsWorker, IfTrue: IsWorkerCheckBB, IfFalse: UserCodeEntryBB, InsertBefore: 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, FnID: OMPRTL___kmpc_get_max_team_threads);
4582 Constant *IsSPMDArg = ConstantInt::get(Ty: OMPInfoCache.OMPBuilder.Int32, V: 0);
4583 CallInst *MaxTeamThreads = CallInst::Create(
4584 Func: MaxTeamThreadsFn, Args: {IsSPMDArg}, NameStr: "max_team_threads", InsertBefore: IsWorkerCheckBB);
4585 OMPInfoCache.setCallingConvention(Callee: MaxTeamThreadsFn, CI: MaxTeamThreads);
4586 MaxTeamThreads->setDebugLoc(DLoc);
4587 Instruction *IsMainOrWorker = ICmpInst::Create(
4588 Op: ICmpInst::ICmp, Pred: llvm::CmpInst::ICMP_SLT, S1: KernelInitCB, S2: MaxTeamThreads,
4589 Name: "thread.is_main_or_worker", InsertBefore: IsWorkerCheckBB);
4590 IsMainOrWorker->setDebugLoc(DLoc);
4591 CondBrInst::Create(Cond: IsMainOrWorker, IfTrue: StateMachineBeginBB,
4592 IfFalse: StateMachineFinishedBB, InsertBefore: IsWorkerCheckBB);
4593
4594 // Create local storage for the work function pointer.
4595 const DataLayout &DL = M.getDataLayout();
4596 Type *VoidPtrTy = PointerType::getUnqual(C&: 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 Loc: 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, FnID: OMPRTL___kmpc_barrier_simple_generic);
4611 CallInst *Barrier =
4612 CallInst::Create(Func: BarrierFn, Args: {Ident, GTid}, NameStr: "", InsertBefore: StateMachineBeginBB);
4613 OMPInfoCache.setCallingConvention(Callee: BarrierFn, CI: Barrier);
4614 Barrier->setDebugLoc(DLoc);
4615
4616 if (WorkFnAI->getType()->getPointerAddressSpace() !=
4617 (unsigned int)AddressSpace::Generic) {
4618 WorkFnAI = new AddrSpaceCastInst(
4619 WorkFnAI, PointerType::get(C&: Ctx, AddressSpace: (unsigned int)AddressSpace::Generic),
4620 WorkFnAI->getName() + ".generic", StateMachineBeginBB);
4621 WorkFnAI->setDebugLoc(DLoc);
4622 }
4623
4624 FunctionCallee KernelParallelFn =
4625 OMPInfoCache.OMPBuilder.getOrCreateRuntimeFunction(
4626 M, FnID: OMPRTL___kmpc_kernel_parallel);
4627 CallInst *IsActiveWorker = CallInst::Create(
4628 Func: KernelParallelFn, Args: {WorkFnAI}, NameStr: "worker.is_active", InsertBefore: StateMachineBeginBB);
4629 OMPInfoCache.setCallingConvention(Callee: KernelParallelFn, CI: 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 Result: Type::getVoidTy(C&: Ctx), Params: {Type::getInt16Ty(C&: Ctx), Type::getInt32Ty(C&: Ctx)},
4637 isVarArg: false);
4638
4639 Instruction *IsDone =
4640 ICmpInst::Create(Op: ICmpInst::ICmp, Pred: llvm::CmpInst::ICMP_EQ, S1: WorkFn,
4641 S2: Constant::getNullValue(Ty: VoidPtrTy), Name: "worker.is_done",
4642 InsertBefore: StateMachineBeginBB);
4643 IsDone->setDebugLoc(DLoc);
4644 CondBrInst::Create(Cond: IsDone, IfTrue: StateMachineFinishedBB,
4645 IfFalse: StateMachineIsActiveCheckBB, InsertBefore: StateMachineBeginBB)
4646 ->setDebugLoc(DLoc);
4647
4648 CondBrInst::Create(Cond: IsActiveWorker, IfTrue: StateMachineIfCascadeCurrentBB,
4649 IfFalse: StateMachineDoneBarrierBB, InsertBefore: StateMachineIsActiveCheckBB)
4650 ->setDebugLoc(DLoc);
4651
4652 Value *ZeroArg =
4653 Constant::getNullValue(Ty: ParallelRegionFnTy->getParamType(i: 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 Val: CB->getArgOperand(i: WrapperFunctionArgNo)->stripPointerCasts());
4664 BasicBlock *PRExecuteBB = BasicBlock::Create(
4665 Context&: Ctx, Name: "worker_state_machine.parallel_region.execute", Parent: Kernel,
4666 InsertBefore: StateMachineEndParallelBB);
4667 CallInst::Create(Func: ParallelRegion, Args: {ZeroArg, GTid}, NameStr: "", InsertBefore: PRExecuteBB)
4668 ->setDebugLoc(DLoc);
4669 UncondBrInst::Create(Target: StateMachineEndParallelBB, InsertBefore: PRExecuteBB)
4670 ->setDebugLoc(DLoc);
4671
4672 BasicBlock *PRNextBB =
4673 BasicBlock::Create(Context&: Ctx, Name: "worker_state_machine.parallel_region.check",
4674 Parent: Kernel, InsertBefore: StateMachineEndParallelBB);
4675 A.registerManifestAddedBasicBlock(BB&: *PRExecuteBB);
4676 A.registerManifestAddedBasicBlock(BB&: *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 Op: ICmpInst::ICmp, Pred: llvm::CmpInst::ICMP_EQ, S1: WorkFn, S2: ParallelRegion,
4684 Name: "worker.check_parallel_region", InsertBefore: StateMachineIfCascadeCurrentBB);
4685 CmpI->setDebugLoc(DLoc);
4686 IsPR = CmpI;
4687 } else {
4688 IsPR = ConstantInt::getTrue(Context&: Ctx);
4689 }
4690
4691 CondBrInst::Create(Cond: IsPR, IfTrue: PRExecuteBB, IfFalse: PRNextBB,
4692 InsertBefore: 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(Ty: ParallelRegionFnTy, Func: WorkFn, Args: {ZeroArg, GTid}, NameStr: "",
4704 InsertBefore: StateMachineIfCascadeCurrentBB)
4705 ->setDebugLoc(DLoc);
4706 }
4707 UncondBrInst::Create(Target: StateMachineEndParallelBB,
4708 InsertBefore: StateMachineIfCascadeCurrentBB)
4709 ->setDebugLoc(DLoc);
4710
4711 FunctionCallee EndParallelFn =
4712 OMPInfoCache.OMPBuilder.getOrCreateRuntimeFunction(
4713 M, FnID: OMPRTL___kmpc_kernel_end_parallel);
4714 CallInst *EndParallel =
4715 CallInst::Create(Func: EndParallelFn, Args: {}, NameStr: "", InsertBefore: StateMachineEndParallelBB);
4716 OMPInfoCache.setCallingConvention(Callee: EndParallelFn, CI: EndParallel);
4717 EndParallel->setDebugLoc(DLoc);
4718 UncondBrInst::Create(Target: StateMachineDoneBarrierBB, InsertBefore: StateMachineEndParallelBB)
4719 ->setDebugLoc(DLoc);
4720
4721 CallInst::Create(Func: BarrierFn, Args: {Ident, GTid}, NameStr: "", InsertBefore: StateMachineDoneBarrierBB)
4722 ->setDebugLoc(DLoc);
4723 UncondBrInst::Create(Target: StateMachineBeginBB, InsertBefore: 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 =
4748 KernelInfo::getKernelEnvironementFromKernelInitCB(KernelInitCB: AA.KernelInitCB);
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 KernelEnvC: ExistingKernelEnvC));
4759
4760 if (!AA.SPMDCompatibilityTracker.isValidState())
4761 AA.setExecModeOfKernelEnvironment(
4762 KernelInfo::getExecModeFromKernelEnvironment(KernelEnvC: ExistingKernelEnvC));
4763
4764 ConstantInt *MayUseNestedParallelismC =
4765 KernelInfo::getMayUseNestedParallelismFromKernelEnvironment(
4766 KernelEnvC: AA.KernelEnvC);
4767 ConstantInt *NewMayUseNestedParallelismC = ConstantInt::get(
4768 Ty: MayUseNestedParallelismC->getIntegerType(), V: 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>(Val: 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>(Val: &I)) {
4783 const auto *UnderlyingObjsAA = A.getAAFor<AAUnderlyingObjects>(
4784 QueryingAA: *this, IRP: IRPosition::value(V: *SI->getPointerOperand()),
4785 DepClass: DepClassTy::OPTIONAL);
4786 auto *HS = A.getAAFor<AAHeapToStack>(
4787 QueryingAA: *this, IRP: IRPosition::function(F: *I.getFunction()),
4788 DepClass: DepClassTy::OPTIONAL);
4789 if (UnderlyingObjsAA &&
4790 UnderlyingObjsAA->forallUnderlyingObjects(Pred: [&](Value &Obj) {
4791 if (AA::isAssumedThreadLocalObject(A, Obj, QueryingAA: *this))
4792 return true;
4793 // Check for AAHeapToStack moved objects which must not be
4794 // guarded.
4795 auto *CB = dyn_cast<CallBase>(Val: &Obj);
4796 return CB && HS && HS->isAssumedHeapToStack(CB: *CB);
4797 }))
4798 return true;
4799 }
4800
4801 // Insert instruction that needs guarding.
4802 SPMDCompatibilityTracker.insert(Elem: &I);
4803 return true;
4804 };
4805
4806 bool UsedAssumedInformationInCheckRWInst = false;
4807 if (!SPMDCompatibilityTracker.isAtFixpoint())
4808 if (!A.checkForAllReadWriteInstructions(
4809 Pred: CheckRWInst, QueryingAA&: *this, UsedAssumedInformation&: 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 QueryingAA: *this, IRP: IRPosition::function(F: *Kernel), DepClass: 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>(Val&: 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 QueryingAA: *this, IRP: IRPosition::function(F: *Callback), DepClass: 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 QueryingAA: *this, IRP: IRPosition::callsite_function(CB), DepClass: 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 Pred: CheckCallInst, QueryingAA: *this, UsedAssumedInformation&: 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 IRP: IRPosition::function(F: *Caller), QueryingAA: this, DepClass: 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(Pred: PredCallSite, QueryingAA: *this,
4934 RequireAllCallSites: true /* RequireAllCallSites */,
4935 UsedAssumedInformation&: 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>(IRP: IRPosition::function(F: *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(Pred: PredCallSite, QueryingAA: *this,
4977 RequireAllCallSites: true /* RequireAllCallSites */,
4978 UsedAssumedInformation&: 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>(Val&: getAssociatedValue());
4994 auto *AssumptionAA = A.getAAFor<AAAssumptionInfo>(
4995 QueryingAA: *this, IRP: IRPosition::callsite_function(CB), DepClass: DepClassTy::OPTIONAL);
4996
4997 // Check for SPMD-mode assumptions.
4998 if (AssumptionAA && AssumptionAA->hasAssumption(Assumption: "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>(Val: 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(Val: Callee);
5018 if (It == OMPInfoCache.RuntimeFunctionIDMap.end()) {
5019 // Unknown caller or declarations are not analyzable, we give up.
5020 if (!Callee || !A.isFunctionIPOAmendable(F: *Callee)) {
5021
5022 // Unknown callees might contain parallel regions, except if they have
5023 // an appropriate assumption attached.
5024 if (!AssumptionAA ||
5025 !(AssumptionAA->hasAssumption(Assumption: "omp_no_openmp") ||
5026 AssumptionAA->hasAssumption(Assumption: "omp_no_parallelism")))
5027 ReachedUnknownParallelRegions.insert(Elem: &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(Elem: &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(KindID: 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>(Val: CB.getArgOperand(i: 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(Elem: &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(Elem: &CB);
5137 ReachedUnknownParallelRegions.insert(Elem: &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(Elem: &CB);
5161 SPMDCompatibilityTracker.indicatePessimisticFixpoint();
5162 SPMDCompatibilityTracker.insert(Elem: &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(Elem: &CB);
5182 SPMDCompatibilityTracker.indicatePessimisticFixpoint();
5183 SPMDCompatibilityTracker.insert(Elem: &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(Elem: &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>(QueryingAA: *this, IRP: getIRPosition(), DepClass: 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(Val: 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: *F);
5227 auto *FnAA =
5228 A.getAAFor<AAKernelInfo>(QueryingAA: *this, IRP: FnPos, DepClass: 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(KindID: LLVMContext::MD_callback))
5239 return indicatePessimisticFixpoint();
5240
5241 CallBase &CB = cast<CallBase>(Val&: 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 QueryingAA: *this, IRP: IRPosition::function(F: *CB.getCaller()), DepClass: DepClassTy::OPTIONAL);
5258 auto *HeapToSharedAA = A.getAAFor<AAHeapToShared>(
5259 QueryingAA: *this, IRP: IRPosition::function(F: *CB.getCaller()), DepClass: 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(Elem: &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(Elem: &CB);
5277 break;
5278 default:
5279 SPMDCompatibilityTracker.indicatePessimisticFixpoint();
5280 SPMDCompatibilityTracker.insert(Elem: &CB);
5281 }
5282 return ChangeStatus::CHANGED;
5283 };
5284
5285 const auto *AACE =
5286 A.getAAFor<AACallEdges>(QueryingAA: *this, IRP: getIRPosition(), DepClass: 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 Val: CB.getArgOperand(i: ParallelRegionOpArgNo)->stripPointerCasts());
5314 if (!ParallelRegion)
5315 return false;
5316
5317 ReachedKnownParallelRegions.insert(Elem: &CB);
5318 /// Check nested parallelism
5319 auto *FnAA = A.getAAFor<AAKernelInfo>(
5320 QueryingAA: *this, IRP: IRPosition::function(F: *ParallelRegion), DepClass: 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>(Val: *SimplifiedValue))
5373 return Str + std::to_string(val: 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(Val: 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>(Val&: getAssociatedValue());
5392 A.registerSimplificationCallback(
5393 IRP: IRPosition::callsite_returned(CB),
5394 CB: [&](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(FromAA: *this, ToAA: *AA, DepClass: 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, Attr: "omp_target_thread_limit");
5419 break;
5420 case OMPRTL___kmpc_get_hardware_num_blocks:
5421 Changed = Changed | foldKernelFnAttribute(A, Attr: "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(IRP: IRPosition::inst(I), NV&: **SimplifiedValue);
5436 A.deleteAfterManifest(I);
5437
5438 CallBase *CB = dyn_cast<CallBase>(Val: &I);
5439 auto Remark = [&](OptimizationRemark OR) {
5440 if (auto *C = dyn_cast<ConstantInt>(Val: *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>(I: CB, RemarkName: "OMP180", RemarkCB&: 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 QueryingAA: *this, IRP: IRPosition::function(F: *getAnchorScope()), DepClass: 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>(QueryingAA: *this, IRP: IRPosition::function(F: *K),
5481 DepClass: 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(Ty: Type::getInt8Ty(C&: Ctx), V: 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(Ty: Type::getInt8Ty(C&: Ctx), V: 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 QueryingAA: *this, IRP: IRPosition::function(F: *getAnchorScope()), DepClass: 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>(QueryingAA: *this, IRP: IRPosition::function(F: *K),
5553 DepClass: 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(Ty: Type::getInt8Ty(C&: Ctx), V: 1);
5582 } else {
5583 assert(KnownSPMDCount == 0 && AssumedSPMDCount == 0 &&
5584 "Expected only non-SPMD kernels!");
5585 SimplifiedValue = ConstantInt::get(Ty: Type::getInt8Ty(C&: Ctx), V: 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 QueryingAA: *this, IRP: IRPosition::function(F: *getAnchorScope()), DepClass: 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(Kind: Attr, Default: -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(Ty: Type::getInt32Ty(C&: Ctx), V: 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, CB: [&](Use &U, Function &F) {
5637 CallInst *CI = OpenMPOpt::getCallIfRegularCall(U, RFI: &RFI);
5638 if (!CI)
5639 return false;
5640 A.getOrCreateAAFor<AAFoldRuntimeCall>(
5641 IRP: IRPosition::callsite_returned(CB: *CI), /* QueryingAA */ nullptr,
5642 DepClass: 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 IRP: IRPosition::function(F: Kernel), /* QueryingAA */ nullptr,
5660 DepClass: 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, CB: CreateKernelInfoCB);
5667
5668 registerFoldRuntimeCall(RF: OMPRTL___kmpc_is_spmd_exec_mode);
5669 registerFoldRuntimeCall(RF: OMPRTL___kmpc_parallel_level);
5670 registerFoldRuntimeCall(RF: OMPRTL___kmpc_get_hardware_num_threads_in_block);
5671 registerFoldRuntimeCall(RF: 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, RFI: &GetterRFI);
5683 if (!CI)
5684 return false;
5685
5686 auto &CB = cast<CallBase>(Val&: *CI);
5687
5688 IRPosition CBPos = IRPosition::callsite_function(CB);
5689 A.getOrCreateAAFor<AAICVTracker>(IRP: CBPos);
5690 return false;
5691 };
5692
5693 GetterRFI.foreachUse(SCC, CB: 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(Range: F->uses(), P: [this](const Use &U) {
5711 const auto *CB = dyn_cast<CallBase>(Val: U.getUser());
5712 return CB && CB->isCallee(U: &U) &&
5713 A.isRunOn(Fn: const_cast<Function *>(CB->getCaller()));
5714 }))
5715 continue;
5716 }
5717 registerAAsForFunction(A, F: *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>(IRP: FPos);
5726 if (F.hasFnAttribute(Kind: Attribute::Convergent))
5727 A.getOrCreateAAFor<AANonConvergent>(IRP: 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 F&: 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>(Val: &I)) {
5741 bool UsedAssumedInformation = false;
5742 A.getAssumedSimplified(V: IRPosition::value(V: *LI), /* AA */ nullptr,
5743 UsedAssumedInformation, S: AA::Interprocedural);
5744 A.getOrCreateAAFor<AAAddressSpace>(
5745 IRP: IRPosition::value(V: *LI->getPointerOperand()));
5746 continue;
5747 }
5748 if (auto *CI = dyn_cast<CallBase>(Val: &I)) {
5749 if (A.Opts.openmp_opt_deglobalization && !HasHeapToStackCandidate) {
5750 if (!TLI)
5751 TLI = A.getInfoCache().getTargetLibraryInfoForFunction(F);
5752 HasHeapToStackCandidate =
5753 isRemovableAlloc(V: CI, TLI) || getFreedOperand(CB: CI, TLI);
5754 }
5755 if (CI->isIndirectCall())
5756 A.getOrCreateAAFor<AAIndirectCallInfo>(
5757 IRP: IRPosition::callsite_function(CB: *CI));
5758 }
5759 if (auto *SI = dyn_cast<StoreInst>(Val: &I)) {
5760 A.getOrCreateAAFor<AAIsDead>(IRP: IRPosition::value(V: *SI));
5761 A.getOrCreateAAFor<AAAddressSpace>(
5762 IRP: IRPosition::value(V: *SI->getPointerOperand()));
5763 continue;
5764 }
5765 if (auto *FI = dyn_cast<FenceInst>(Val: &I)) {
5766 A.getOrCreateAAFor<AAIsDead>(IRP: IRPosition::value(V: *FI));
5767 continue;
5768 }
5769 if (auto *II = dyn_cast<IntrinsicInst>(Val: &I)) {
5770 if (II->getIntrinsicID() == Intrinsic::assume) {
5771 A.getOrCreateAAFor<AAPotentialValues>(
5772 IRP: IRPosition::value(V: *II->getArgOperand(i: 0)));
5773 continue;
5774 }
5775 }
5776 }
5777
5778 if (FunctionUsesSharedAlloc)
5779 A.getOrCreateAAFor<AAHeapToShared>(IRP: FPos);
5780 if (HasHeapToStackCandidate)
5781 A.getOrCreateAAFor<AAHeapToStack>(IRP: 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()) {
5794 case IRPosition::IRP_INVALID:
5795 case IRPosition::IRP_FLOAT:
5796 case IRPosition::IRP_ARGUMENT:
5797 case IRPosition::IRP_CALL_SITE_ARGUMENT:
5798 llvm_unreachable("ICVTracker can only be created for function position!");
5799 case IRPosition::IRP_RETURNED:
5800 AA = new (A.Allocator) AAICVTrackerFunctionReturned(IRP, A);
5801 break;
5802 case IRPosition::IRP_CALL_SITE_RETURNED:
5803 AA = new (A.Allocator) AAICVTrackerCallSiteReturned(IRP, A);
5804 break;
5805 case IRPosition::IRP_CALL_SITE:
5806 AA = new (A.Allocator) AAICVTrackerCallSite(IRP, A);
5807 break;
5808 case IRPosition::IRP_FUNCTION:
5809 AA = new (A.Allocator) AAICVTrackerFunction(IRP, A);
5810 break;
5811 }
5812
5813 return *AA;
5814}
5815
5816AAExecutionDomain &AAExecutionDomain::createForPosition(const IRPosition &IRP,
5817 Attributor &A) {
5818 AAExecutionDomainFunction *AA = nullptr;
5819 switch (IRP.getPositionKind()) {
5820 case IRPosition::IRP_INVALID:
5821 case IRPosition::IRP_FLOAT:
5822 case IRPosition::IRP_ARGUMENT:
5823 case IRPosition::IRP_CALL_SITE_ARGUMENT:
5824 case IRPosition::IRP_RETURNED:
5825 case IRPosition::IRP_CALL_SITE_RETURNED:
5826 case IRPosition::IRP_CALL_SITE:
5827 llvm_unreachable(
5828 "AAExecutionDomain can only be created for function position!");
5829 case IRPosition::IRP_FUNCTION:
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()) {
5841 case IRPosition::IRP_INVALID:
5842 case IRPosition::IRP_FLOAT:
5843 case IRPosition::IRP_ARGUMENT:
5844 case IRPosition::IRP_CALL_SITE_ARGUMENT:
5845 case IRPosition::IRP_RETURNED:
5846 case IRPosition::IRP_CALL_SITE_RETURNED:
5847 case IRPosition::IRP_CALL_SITE:
5848 llvm_unreachable(
5849 "AAHeapToShared can only be created for function position!");
5850 case IRPosition::IRP_FUNCTION:
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()) {
5862 case IRPosition::IRP_INVALID:
5863 case IRPosition::IRP_FLOAT:
5864 case IRPosition::IRP_ARGUMENT:
5865 case IRPosition::IRP_RETURNED:
5866 case IRPosition::IRP_CALL_SITE_RETURNED:
5867 case IRPosition::IRP_CALL_SITE_ARGUMENT:
5868 llvm_unreachable("KernelInfo can only be created for function position!");
5869 case IRPosition::IRP_CALL_SITE:
5870 AA = new (A.Allocator) AAKernelInfoCallSite(IRP, A);
5871 break;
5872 case IRPosition::IRP_FUNCTION:
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()) {
5884 case IRPosition::IRP_INVALID:
5885 case IRPosition::IRP_FLOAT:
5886 case IRPosition::IRP_ARGUMENT:
5887 case IRPosition::IRP_RETURNED:
5888 case IRPosition::IRP_FUNCTION:
5889 case IRPosition::IRP_CALL_SITE:
5890 case IRPosition::IRP_CALL_SITE_ARGUMENT:
5891 llvm_unreachable("KernelInfo can only be created for call site position!");
5892 case IRPosition::IRP_CALL_SITE_RETURNED:
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.
5910static bool shouldSpecializeIndirectCallee(Attributor &A,
5911 const AbstractAttribute &,
5912 CallBase &, Function &,
5913 unsigned NumAssumedCallees) {
5914 return NumAssumedCallees <= A.Opts.openmp_opt_max_callees_for_specialization;
5915}
5916
5917PreservedAnalyses OpenMPOptPass::run(Module &M, ModuleAnalysisManager &AM) {
5918 if (!containsOpenMP(M))
5919 return PreservedAnalyses::all();
5920 const IPOOptions &Opts = getIPOOptions(M);
5921 if (!Opts.openmp_opt)
5922 return PreservedAnalyses::all();
5923
5924 FunctionAnalysisManager &FAM =
5925 AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager();
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(key: &F))
5933 return true;
5934 return !F.use_empty();
5935 };
5936
5937 auto EmitRemark = [&](Function &F) {
5938 auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
5939 ORE.emit(RemarkBuilder: [&]() {
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(key: &F) && IsCalled(F) &&
5955 Opts.openmp_opt_internalization) {
5956 if (Attributor::isInternalizable(F)) {
5957 InternalizeFns.insert(Ptr: &F);
5958 } else if (!F.hasLocalLinkage() && !F.hasFnAttribute(Kind: Attribute::Cold)) {
5959 EmitRemark(F);
5960 }
5961 }
5962
5963 Changed |=
5964 Attributor::internalizeFunctions(FnSet&: InternalizeFns, FnMap&: InternalizedMap);
5965 }
5966
5967 // Look at every function in the Module unless it was internalized.
5968 SetVector<Function *> Functions;
5969 SmallVector<Function *, 16> SCC;
5970 for (Function &F : M)
5971 if (!F.isDeclaration() && !InternalizedMap.lookup(Val: &F)) {
5972 SCC.push_back(Elt: &F);
5973 Functions.insert(X: &F);
5974 }
5975
5976 if (SCC.empty())
5977 return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all();
5978
5979 AnalysisGetter AG(FAM);
5980
5981 auto OREGetter = [&FAM](Function *F) -> OptimizationRemarkEmitter & {
5982 return FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: *F);
5983 };
5984
5985 BumpPtrAllocator Allocator;
5986 CallGraphUpdater CGUpdater;
5987
5988 bool PostLink = LTOPhase == ThinOrFullLTOPhase::FullLTOPostLink ||
5989 LTOPhase == ThinOrFullLTOPhase::ThinLTOPostLink ||
5990 LTOPhase == ThinOrFullLTOPhase::ThinLTOPreLink;
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);
5997 AC.DefaultInitializeLiveInternals = false;
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;
6004 AC.IndirectCalleeSpecializationCallback = shouldSpecializeIndirectCallee;
6005 AC.IPOAmendableCB = [](const Function &F) {
6006 return F.hasFnAttribute(Kind: "kernel");
6007 };
6008
6009 Attributor A(Functions, InfoCache, AC);
6010
6011 OpenMPOpt OMPOpt(SCC, CGUpdater, OREGetter, InfoCache, A);
6012 Changed |= OMPOpt.run(IsModulePass: 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(key: &F) && !F.isNoInline())
6018 F.addFnAttr(Kind: 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
6029PreservedAnalyses OpenMPOptCGSCCPass::run(LazyCallGraph::SCC &C,
6030 CGSCCAnalysisManager &AM,
6031 LazyCallGraph &CG,
6032 CGSCCUpdateResult &UR) {
6033 if (!containsOpenMP(M&: *C.begin()->getFunction().getParent()))
6034 return PreservedAnalyses::all();
6035 const IPOOptions &Opts = getIPOOptions(F: C.begin()->getFunction());
6036 if (!Opts.openmp_opt)
6037 return PreservedAnalyses::all();
6038
6039 SmallVector<Function *, 16> SCC;
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(Elt: 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
6054 FunctionAnalysisManager &FAM =
6055 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(IR&: C, ExtraArgs&: CG).getManager();
6056
6057 AnalysisGetter AG(FAM);
6058
6059 auto OREGetter = [&FAM](Function *F) -> OptimizationRemarkEmitter & {
6060 return FAM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: *F);
6061 };
6062
6063 BumpPtrAllocator Allocator;
6064 CallGraphUpdater CGUpdater;
6065 CGUpdater.initialize(LCG&: CG, SCC&: C, AM, UR);
6066
6067 bool PostLink = LTOPhase == ThinOrFullLTOPhase::FullLTOPostLink ||
6068 LTOPhase == ThinOrFullLTOPhase::ThinLTOPostLink ||
6069 LTOPhase == ThinOrFullLTOPhase::ThinLTOPreLink;
6070 SetVector<Function *> Functions(llvm::from_range, SCC);
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);
6078 AC.DefaultInitializeLiveInternals = false;
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;
6085 AC.IndirectCalleeSpecializationCallback = shouldSpecializeIndirectCallee;
6086
6087 Attributor A(Functions, InfoCache, AC);
6088
6089 OpenMPOpt OMPOpt(SCC, CGUpdater, OREGetter, InfoCache, A);
6090 bool Changed = OMPOpt.run(IsModulePass: 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
6101bool llvm::omp::isOpenMPKernel(Function &Fn) {
6102 return Fn.hasFnAttribute(Kind: "kernel");
6103}
6104
6105KernelSet llvm::omp::getDeviceKernels(Module &M) {
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(Fn&: F)) {
6114 ++NumOpenMPTargetRegionKernels;
6115 Kernels.insert(X: &F);
6116 } else
6117 ++NumNonOpenMPTargetRegionKernels;
6118 }
6119
6120 return Kernels;
6121}
6122
6123bool llvm::omp::containsOpenMP(Module &M) {
6124 Metadata *MD = M.getModuleFlag(Key: "openmp");
6125 if (!MD)
6126 return false;
6127
6128 return true;
6129}
6130
6131bool llvm::omp::isOpenMPDevice(Module &M) {
6132 Metadata *MD = M.getModuleFlag(Key: "openmp-device");
6133 if (!MD)
6134 return false;
6135
6136 return true;
6137}
6138