LLVM  16.0.0git
OMPIRBuilder.cpp
Go to the documentation of this file.
1 //===- OpenMPIRBuilder.cpp - Builder for LLVM-IR for OpenMP directives ----===//
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 /// \file
9 ///
10 /// This file implements the OpenMPIRBuilder class, which is used as a
11 /// convenient way to create LLVM instructions for OpenMP directives.
12 ///
13 //===----------------------------------------------------------------------===//
14 
16 #include "llvm/ADT/SmallSet.h"
17 #include "llvm/ADT/StringRef.h"
20 #include "llvm/Analysis/LoopInfo.h"
24 #include "llvm/IR/CFG.h"
25 #include "llvm/IR/Constants.h"
27 #include "llvm/IR/DerivedTypes.h"
28 #include "llvm/IR/GlobalVariable.h"
29 #include "llvm/IR/IRBuilder.h"
30 #include "llvm/IR/MDBuilder.h"
31 #include "llvm/IR/PassManager.h"
32 #include "llvm/IR/Value.h"
33 #include "llvm/MC/TargetRegistry.h"
42 
43 #include <cstdint>
44 
45 #define DEBUG_TYPE "openmp-ir-builder"
46 
47 using namespace llvm;
48 using namespace omp;
49 
50 static cl::opt<bool>
51  OptimisticAttributes("openmp-ir-builder-optimistic-attributes", cl::Hidden,
52  cl::desc("Use optimistic attributes describing "
53  "'as-if' properties of runtime calls."),
54  cl::init(false));
55 
57  "openmp-ir-builder-unroll-threshold-factor", cl::Hidden,
58  cl::desc("Factor for the unroll threshold to account for code "
59  "simplifications still taking place"),
60  cl::init(1.5));
61 
62 #ifndef NDEBUG
63 /// Return whether IP1 and IP2 are ambiguous, i.e. that inserting instructions
64 /// at position IP1 may change the meaning of IP2 or vice-versa. This is because
65 /// an InsertPoint stores the instruction before something is inserted. For
66 /// instance, if both point to the same instruction, two IRBuilders alternating
67 /// creating instruction will cause the instructions to be interleaved.
70  if (!IP1.isSet() || !IP2.isSet())
71  return false;
72  return IP1.getBlock() == IP2.getBlock() && IP1.getPoint() == IP2.getPoint();
73 }
74 
76  // Valid ordered/unordered and base algorithm combinations.
77  switch (SchedType & ~OMPScheduleType::MonotonicityMask) {
119  break;
120  default:
121  return false;
122  }
123 
124  // Must not set both monotonicity modifiers at the same time.
125  OMPScheduleType MonotonicityFlags =
127  if (MonotonicityFlags == OMPScheduleType::MonotonicityMask)
128  return false;
129 
130  return true;
131 }
132 #endif
133 
134 /// Determine which scheduling algorithm to use, determined from schedule clause
135 /// arguments.
136 static OMPScheduleType
137 getOpenMPBaseScheduleType(llvm::omp::ScheduleKind ClauseKind, bool HasChunks,
138  bool HasSimdModifier) {
139  // Currently, the default schedule it static.
140  switch (ClauseKind) {
141  case OMP_SCHEDULE_Default:
142  case OMP_SCHEDULE_Static:
143  return HasChunks ? OMPScheduleType::BaseStaticChunked
145  case OMP_SCHEDULE_Dynamic:
147  case OMP_SCHEDULE_Guided:
148  return HasSimdModifier ? OMPScheduleType::BaseGuidedSimd
150  case OMP_SCHEDULE_Auto:
152  case OMP_SCHEDULE_Runtime:
153  return HasSimdModifier ? OMPScheduleType::BaseRuntimeSimd
155  }
156  llvm_unreachable("unhandled schedule clause argument");
157 }
158 
159 /// Adds ordering modifier flags to schedule type.
160 static OMPScheduleType
162  bool HasOrderedClause) {
163  assert((BaseScheduleType & OMPScheduleType::ModifierMask) ==
165  "Must not have ordering nor monotonicity flags already set");
166 
167  OMPScheduleType OrderingModifier = HasOrderedClause
170  OMPScheduleType OrderingScheduleType = BaseScheduleType | OrderingModifier;
171 
172  // Unsupported combinations
173  if (OrderingScheduleType ==
176  else if (OrderingScheduleType == (OMPScheduleType::BaseRuntimeSimd |
179 
180  return OrderingScheduleType;
181 }
182 
183 /// Adds monotonicity modifier flags to schedule type.
184 static OMPScheduleType
186  bool HasSimdModifier, bool HasMonotonic,
187  bool HasNonmonotonic, bool HasOrderedClause) {
188  assert((ScheduleType & OMPScheduleType::MonotonicityMask) ==
190  "Must not have monotonicity flags already set");
191  assert((!HasMonotonic || !HasNonmonotonic) &&
192  "Monotonic and Nonmonotonic are contradicting each other");
193 
194  if (HasMonotonic) {
195  return ScheduleType | OMPScheduleType::ModifierMonotonic;
196  } else if (HasNonmonotonic) {
197  return ScheduleType | OMPScheduleType::ModifierNonmonotonic;
198  } else {
199  // OpenMP 5.1, 2.11.4 Worksharing-Loop Construct, Description.
200  // If the static schedule kind is specified or if the ordered clause is
201  // specified, and if the nonmonotonic modifier is not specified, the
202  // effect is as if the monotonic modifier is specified. Otherwise, unless
203  // the monotonic modifier is specified, the effect is as if the
204  // nonmonotonic modifier is specified.
205  OMPScheduleType BaseScheduleType =
206  ScheduleType & ~OMPScheduleType::ModifierMask;
207  if ((BaseScheduleType == OMPScheduleType::BaseStatic) ||
208  (BaseScheduleType == OMPScheduleType::BaseStaticChunked) ||
209  HasOrderedClause) {
210  // The monotonic is used by default in openmp runtime library, so no need
211  // to set it.
212  return ScheduleType;
213  } else {
214  return ScheduleType | OMPScheduleType::ModifierNonmonotonic;
215  }
216  }
217 }
218 
219 /// Determine the schedule type using schedule and ordering clause arguments.
220 static OMPScheduleType
221 computeOpenMPScheduleType(ScheduleKind ClauseKind, bool HasChunks,
222  bool HasSimdModifier, bool HasMonotonicModifier,
223  bool HasNonmonotonicModifier, bool HasOrderedClause) {
224  OMPScheduleType BaseSchedule =
225  getOpenMPBaseScheduleType(ClauseKind, HasChunks, HasSimdModifier);
226  OMPScheduleType OrderedSchedule =
227  getOpenMPOrderingScheduleType(BaseSchedule, HasOrderedClause);
229  OrderedSchedule, HasSimdModifier, HasMonotonicModifier,
230  HasNonmonotonicModifier, HasOrderedClause);
231 
233  return Result;
234 }
235 
236 /// Make \p Source branch to \p Target.
237 ///
238 /// Handles two situations:
239 /// * \p Source already has an unconditional branch.
240 /// * \p Source is a degenerate block (no terminator because the BB is
241 /// the current head of the IR construction).
243  if (Instruction *Term = Source->getTerminator()) {
244  auto *Br = cast<BranchInst>(Term);
245  assert(!Br->isConditional() &&
246  "BB's terminator must be an unconditional branch (or degenerate)");
247  BasicBlock *Succ = Br->getSuccessor(0);
248  Succ->removePredecessor(Source, /*KeepOneInputPHIs=*/true);
249  Br->setSuccessor(0, Target);
250  return;
251  }
252 
253  auto *NewBr = BranchInst::Create(Target, Source);
254  NewBr->setDebugLoc(DL);
255 }
256 
258  bool CreateBranch) {
259  assert(New->getFirstInsertionPt() == New->begin() &&
260  "Target BB must not have PHI nodes");
261 
262  // Move instructions to new block.
263  BasicBlock *Old = IP.getBlock();
264  New->getInstList().splice(New->begin(), Old->getInstList(), IP.getPoint(),
265  Old->end());
266 
267  if (CreateBranch)
268  BranchInst::Create(New, Old);
269 }
270 
271 void llvm::spliceBB(IRBuilder<> &Builder, BasicBlock *New, bool CreateBranch) {
272  DebugLoc DebugLoc = Builder.getCurrentDebugLocation();
273  BasicBlock *Old = Builder.GetInsertBlock();
274 
275  spliceBB(Builder.saveIP(), New, CreateBranch);
276  if (CreateBranch)
277  Builder.SetInsertPoint(Old->getTerminator());
278  else
279  Builder.SetInsertPoint(Old);
280 
281  // SetInsertPoint also updates the Builder's debug location, but we want to
282  // keep the one the Builder was configured to use.
283  Builder.SetCurrentDebugLocation(DebugLoc);
284 }
285 
287  llvm::Twine Name) {
288  BasicBlock *Old = IP.getBlock();
290  Old->getContext(), Name.isTriviallyEmpty() ? Old->getName() : Name,
291  Old->getParent(), Old->getNextNode());
292  spliceBB(IP, New, CreateBranch);
293  New->replaceSuccessorsPhiUsesWith(Old, New);
294  return New;
295 }
296 
298  llvm::Twine Name) {
299  DebugLoc DebugLoc = Builder.getCurrentDebugLocation();
300  BasicBlock *New = splitBB(Builder.saveIP(), CreateBranch, Name);
301  if (CreateBranch)
302  Builder.SetInsertPoint(Builder.GetInsertBlock()->getTerminator());
303  else
304  Builder.SetInsertPoint(Builder.GetInsertBlock());
305  // SetInsertPoint also updates the Builder's debug location, but we want to
306  // keep the one the Builder was configured to use.
307  Builder.SetCurrentDebugLocation(DebugLoc);
308  return New;
309 }
310 
312  llvm::Twine Name) {
313  DebugLoc DebugLoc = Builder.getCurrentDebugLocation();
314  BasicBlock *New = splitBB(Builder.saveIP(), CreateBranch, Name);
315  if (CreateBranch)
316  Builder.SetInsertPoint(Builder.GetInsertBlock()->getTerminator());
317  else
318  Builder.SetInsertPoint(Builder.GetInsertBlock());
319  // SetInsertPoint also updates the Builder's debug location, but we want to
320  // keep the one the Builder was configured to use.
321  Builder.SetCurrentDebugLocation(DebugLoc);
322  return New;
323 }
324 
326  llvm::Twine Suffix) {
327  BasicBlock *Old = Builder.GetInsertBlock();
328  return splitBB(Builder, CreateBranch, Old->getName() + Suffix);
329 }
330 
332  LLVMContext &Ctx = Fn.getContext();
333 
334  // Get the function's current attributes.
335  auto Attrs = Fn.getAttributes();
336  auto FnAttrs = Attrs.getFnAttrs();
337  auto RetAttrs = Attrs.getRetAttrs();
339  for (size_t ArgNo = 0; ArgNo < Fn.arg_size(); ++ArgNo)
340  ArgAttrs.emplace_back(Attrs.getParamAttrs(ArgNo));
341 
342 #define OMP_ATTRS_SET(VarName, AttrSet) AttributeSet VarName = AttrSet;
343 #include "llvm/Frontend/OpenMP/OMPKinds.def"
344 
345  // Add attributes to the function declaration.
346  switch (FnID) {
347 #define OMP_RTL_ATTRS(Enum, FnAttrSet, RetAttrSet, ArgAttrSets) \
348  case Enum: \
349  FnAttrs = FnAttrs.addAttributes(Ctx, FnAttrSet); \
350  RetAttrs = RetAttrs.addAttributes(Ctx, RetAttrSet); \
351  for (size_t ArgNo = 0; ArgNo < ArgAttrSets.size(); ++ArgNo) \
352  ArgAttrs[ArgNo] = \
353  ArgAttrs[ArgNo].addAttributes(Ctx, ArgAttrSets[ArgNo]); \
354  Fn.setAttributes(AttributeList::get(Ctx, FnAttrs, RetAttrs, ArgAttrs)); \
355  break;
356 #include "llvm/Frontend/OpenMP/OMPKinds.def"
357  default:
358  // Attributes are optional.
359  break;
360  }
361 }
362 
365  FunctionType *FnTy = nullptr;
366  Function *Fn = nullptr;
367 
368  // Try to find the declation in the module first.
369  switch (FnID) {
370 #define OMP_RTL(Enum, Str, IsVarArg, ReturnType, ...) \
371  case Enum: \
372  FnTy = FunctionType::get(ReturnType, ArrayRef<Type *>{__VA_ARGS__}, \
373  IsVarArg); \
374  Fn = M.getFunction(Str); \
375  break;
376 #include "llvm/Frontend/OpenMP/OMPKinds.def"
377  }
378 
379  if (!Fn) {
380  // Create a new declaration if we need one.
381  switch (FnID) {
382 #define OMP_RTL(Enum, Str, ...) \
383  case Enum: \
384  Fn = Function::Create(FnTy, GlobalValue::ExternalLinkage, Str, M); \
385  break;
386 #include "llvm/Frontend/OpenMP/OMPKinds.def"
387  }
388 
389  // Add information if the runtime function takes a callback function
390  if (FnID == OMPRTL___kmpc_fork_call || FnID == OMPRTL___kmpc_fork_teams) {
391  if (!Fn->hasMetadata(LLVMContext::MD_callback)) {
392  LLVMContext &Ctx = Fn->getContext();
393  MDBuilder MDB(Ctx);
394  // Annotate the callback behavior of the runtime function:
395  // - The callback callee is argument number 2 (microtask).
396  // - The first two arguments of the callback callee are unknown (-1).
397  // - All variadic arguments to the runtime function are passed to the
398  // callback callee.
399  Fn->addMetadata(
400  LLVMContext::MD_callback,
402  2, {-1, -1}, /* VarArgsArePassed */ true)}));
403  }
404  }
405 
406  LLVM_DEBUG(dbgs() << "Created OpenMP runtime function " << Fn->getName()
407  << " with type " << *Fn->getFunctionType() << "\n");
408  addAttributes(FnID, *Fn);
409 
410  } else {
411  LLVM_DEBUG(dbgs() << "Found OpenMP runtime function " << Fn->getName()
412  << " with type " << *Fn->getFunctionType() << "\n");
413  }
414 
415  assert(Fn && "Failed to create OpenMP runtime function");
416 
417  // Cast the function to the expected type if necessary
419  return {FnTy, C};
420 }
421 
423  FunctionCallee RTLFn = getOrCreateRuntimeFunction(M, FnID);
424  auto *Fn = dyn_cast<llvm::Function>(RTLFn.getCallee());
425  assert(Fn && "Failed to create OpenMP runtime function pointer");
426  return Fn;
427 }
428 
429 void OpenMPIRBuilder::initialize() { initializeTypes(M); }
430 
432  SmallPtrSet<BasicBlock *, 32> ParallelRegionBlockSet;
434  SmallVector<OutlineInfo, 16> DeferredOutlines;
435  for (OutlineInfo &OI : OutlineInfos) {
436  // Skip functions that have not finalized yet; may happen with nested
437  // function generation.
438  if (Fn && OI.getFunction() != Fn) {
439  DeferredOutlines.push_back(OI);
440  continue;
441  }
442 
443  ParallelRegionBlockSet.clear();
444  Blocks.clear();
445  OI.collectBlocks(ParallelRegionBlockSet, Blocks);
446 
447  Function *OuterFn = OI.getFunction();
448  CodeExtractorAnalysisCache CEAC(*OuterFn);
449  CodeExtractor Extractor(Blocks, /* DominatorTree */ nullptr,
450  /* AggregateArgs */ true,
451  /* BlockFrequencyInfo */ nullptr,
452  /* BranchProbabilityInfo */ nullptr,
453  /* AssumptionCache */ nullptr,
454  /* AllowVarArgs */ true,
455  /* AllowAlloca */ true,
456  /* AllocaBlock*/ OI.OuterAllocaBB,
457  /* Suffix */ ".omp_par");
458 
459  LLVM_DEBUG(dbgs() << "Before outlining: " << *OuterFn << "\n");
460  LLVM_DEBUG(dbgs() << "Entry " << OI.EntryBB->getName()
461  << " Exit: " << OI.ExitBB->getName() << "\n");
462  assert(Extractor.isEligible() &&
463  "Expected OpenMP outlining to be possible!");
464 
465  for (auto *V : OI.ExcludeArgsFromAggregate)
466  Extractor.excludeArgFromAggregate(V);
467 
468  Function *OutlinedFn = Extractor.extractCodeRegion(CEAC);
469 
470  LLVM_DEBUG(dbgs() << "After outlining: " << *OuterFn << "\n");
471  LLVM_DEBUG(dbgs() << " Outlined function: " << *OutlinedFn << "\n");
472  assert(OutlinedFn->getReturnType()->isVoidTy() &&
473  "OpenMP outlined functions should not return a value!");
474 
475  // For compability with the clang CG we move the outlined function after the
476  // one with the parallel region.
477  OutlinedFn->removeFromParent();
478  M.getFunctionList().insertAfter(OuterFn->getIterator(), OutlinedFn);
479 
480  // Remove the artificial entry introduced by the extractor right away, we
481  // made our own entry block after all.
482  {
483  BasicBlock &ArtificialEntry = OutlinedFn->getEntryBlock();
484  assert(ArtificialEntry.getUniqueSuccessor() == OI.EntryBB);
485  assert(OI.EntryBB->getUniquePredecessor() == &ArtificialEntry);
486  // Move instructions from the to-be-deleted ArtificialEntry to the entry
487  // basic block of the parallel region. CodeExtractor generates
488  // instructions to unwrap the aggregate argument and may sink
489  // allocas/bitcasts for values that are solely used in the outlined region
490  // and do not escape.
491  assert(!ArtificialEntry.empty() &&
492  "Expected instructions to add in the outlined region entry");
493  for (BasicBlock::reverse_iterator It = ArtificialEntry.rbegin(),
494  End = ArtificialEntry.rend();
495  It != End;) {
496  Instruction &I = *It;
497  It++;
498 
499  if (I.isTerminator())
500  continue;
501 
502  I.moveBefore(*OI.EntryBB, OI.EntryBB->getFirstInsertionPt());
503  }
504 
505  OI.EntryBB->moveBefore(&ArtificialEntry);
506  ArtificialEntry.eraseFromParent();
507  }
508  assert(&OutlinedFn->getEntryBlock() == OI.EntryBB);
509  assert(OutlinedFn && OutlinedFn->getNumUses() == 1);
510 
511  // Run a user callback, e.g. to add attributes.
512  if (OI.PostOutlineCB)
513  OI.PostOutlineCB(*OutlinedFn);
514  }
515 
516  // Remove work items that have been completed.
517  OutlineInfos = std::move(DeferredOutlines);
518 }
519 
521  assert(OutlineInfos.empty() && "There must be no outstanding outlinings");
522 }
523 
525  IntegerType *I32Ty = Type::getInt32Ty(M.getContext());
526  auto *GV =
527  new GlobalVariable(M, I32Ty,
528  /* isConstant = */ true, GlobalValue::WeakODRLinkage,
529  ConstantInt::get(I32Ty, Value), Name);
530  GV->setVisibility(GlobalValue::HiddenVisibility);
531 
532  return GV;
533 }
534 
536  uint32_t SrcLocStrSize,
537  IdentFlag LocFlags,
538  unsigned Reserve2Flags) {
539  // Enable "C-mode".
540  LocFlags |= OMP_IDENT_FLAG_KMPC;
541 
542  Constant *&Ident =
543  IdentMap[{SrcLocStr, uint64_t(LocFlags) << 31 | Reserve2Flags}];
544  if (!Ident) {
545  Constant *I32Null = ConstantInt::getNullValue(Int32);
546  Constant *IdentData[] = {I32Null,
547  ConstantInt::get(Int32, uint32_t(LocFlags)),
548  ConstantInt::get(Int32, Reserve2Flags),
549  ConstantInt::get(Int32, SrcLocStrSize), SrcLocStr};
550  Constant *Initializer =
551  ConstantStruct::get(OpenMPIRBuilder::Ident, IdentData);
552 
553  // Look for existing encoding of the location + flags, not needed but
554  // minimizes the difference to the existing solution while we transition.
555  for (GlobalVariable &GV : M.getGlobalList())
556  if (GV.getValueType() == OpenMPIRBuilder::Ident && GV.hasInitializer())
557  if (GV.getInitializer() == Initializer)
558  Ident = &GV;
559 
560  if (!Ident) {
561  auto *GV = new GlobalVariable(
562  M, OpenMPIRBuilder::Ident,
563  /* isConstant = */ true, GlobalValue::PrivateLinkage, Initializer, "",
565  M.getDataLayout().getDefaultGlobalsAddressSpace());
566  GV->setUnnamedAddr(GlobalValue::UnnamedAddr::Global);
567  GV->setAlignment(Align(8));
568  Ident = GV;
569  }
570  }
571 
572  return ConstantExpr::getPointerBitCastOrAddrSpaceCast(Ident, IdentPtr);
573 }
574 
576  uint32_t &SrcLocStrSize) {
577  SrcLocStrSize = LocStr.size();
578  Constant *&SrcLocStr = SrcLocStrMap[LocStr];
579  if (!SrcLocStr) {
580  Constant *Initializer =
581  ConstantDataArray::getString(M.getContext(), LocStr);
582 
583  // Look for existing encoding of the location, not needed but minimizes the
584  // difference to the existing solution while we transition.
585  for (GlobalVariable &GV : M.getGlobalList())
586  if (GV.isConstant() && GV.hasInitializer() &&
587  GV.getInitializer() == Initializer)
588  return SrcLocStr = ConstantExpr::getPointerCast(&GV, Int8Ptr);
589 
590  SrcLocStr = Builder.CreateGlobalStringPtr(LocStr, /* Name */ "",
591  /* AddressSpace */ 0, &M);
592  }
593  return SrcLocStr;
594 }
595 
597  StringRef FileName,
598  unsigned Line, unsigned Column,
599  uint32_t &SrcLocStrSize) {
600  SmallString<128> Buffer;
601  Buffer.push_back(';');
602  Buffer.append(FileName);
603  Buffer.push_back(';');
604  Buffer.append(FunctionName);
605  Buffer.push_back(';');
606  Buffer.append(std::to_string(Line));
607  Buffer.push_back(';');
608  Buffer.append(std::to_string(Column));
609  Buffer.push_back(';');
610  Buffer.push_back(';');
611  return getOrCreateSrcLocStr(Buffer.str(), SrcLocStrSize);
612 }
613 
614 Constant *
616  StringRef UnknownLoc = ";unknown;unknown;0;0;;";
617  return getOrCreateSrcLocStr(UnknownLoc, SrcLocStrSize);
618 }
619 
621  uint32_t &SrcLocStrSize,
622  Function *F) {
623  DILocation *DIL = DL.get();
624  if (!DIL)
625  return getOrCreateDefaultSrcLocStr(SrcLocStrSize);
626  StringRef FileName = M.getName();
627  if (DIFile *DIF = DIL->getFile())
628  if (Optional<StringRef> Source = DIF->getSource())
629  FileName = *Source;
630  StringRef Function = DIL->getScope()->getSubprogram()->getName();
631  if (Function.empty() && F)
632  Function = F->getName();
633  return getOrCreateSrcLocStr(Function, FileName, DIL->getLine(),
634  DIL->getColumn(), SrcLocStrSize);
635 }
636 
638  uint32_t &SrcLocStrSize) {
639  return getOrCreateSrcLocStr(Loc.DL, SrcLocStrSize,
640  Loc.IP.getBlock()->getParent());
641 }
642 
644  return Builder.CreateCall(
645  getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_global_thread_num), Ident,
646  "omp_global_thread_num");
647 }
648 
651  bool ForceSimpleCall, bool CheckCancelFlag) {
652  if (!updateToLocation(Loc))
653  return Loc.IP;
654  return emitBarrierImpl(Loc, DK, ForceSimpleCall, CheckCancelFlag);
655 }
656 
659  bool ForceSimpleCall, bool CheckCancelFlag) {
660  // Build call __kmpc_cancel_barrier(loc, thread_id) or
661  // __kmpc_barrier(loc, thread_id);
662 
663  IdentFlag BarrierLocFlags;
664  switch (Kind) {
665  case OMPD_for:
666  BarrierLocFlags = OMP_IDENT_FLAG_BARRIER_IMPL_FOR;
667  break;
668  case OMPD_sections:
669  BarrierLocFlags = OMP_IDENT_FLAG_BARRIER_IMPL_SECTIONS;
670  break;
671  case OMPD_single:
672  BarrierLocFlags = OMP_IDENT_FLAG_BARRIER_IMPL_SINGLE;
673  break;
674  case OMPD_barrier:
675  BarrierLocFlags = OMP_IDENT_FLAG_BARRIER_EXPL;
676  break;
677  default:
678  BarrierLocFlags = OMP_IDENT_FLAG_BARRIER_IMPL;
679  break;
680  }
681 
682  uint32_t SrcLocStrSize;
683  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
684  Value *Args[] = {
685  getOrCreateIdent(SrcLocStr, SrcLocStrSize, BarrierLocFlags),
686  getOrCreateThreadID(getOrCreateIdent(SrcLocStr, SrcLocStrSize))};
687 
688  // If we are in a cancellable parallel region, barriers are cancellation
689  // points.
690  // TODO: Check why we would force simple calls or to ignore the cancel flag.
691  bool UseCancelBarrier =
692  !ForceSimpleCall && isLastFinalizationInfoCancellable(OMPD_parallel);
693 
694  Value *Result =
695  Builder.CreateCall(getOrCreateRuntimeFunctionPtr(
696  UseCancelBarrier ? OMPRTL___kmpc_cancel_barrier
697  : OMPRTL___kmpc_barrier),
698  Args);
699 
700  if (UseCancelBarrier && CheckCancelFlag)
701  emitCancelationCheckImpl(Result, OMPD_parallel);
702 
703  return Builder.saveIP();
704 }
705 
708  Value *IfCondition,
709  omp::Directive CanceledDirective) {
710  if (!updateToLocation(Loc))
711  return Loc.IP;
712 
713  // LLVM utilities like blocks with terminators.
714  auto *UI = Builder.CreateUnreachable();
715 
716  Instruction *ThenTI = UI, *ElseTI = nullptr;
717  if (IfCondition)
718  SplitBlockAndInsertIfThenElse(IfCondition, UI, &ThenTI, &ElseTI);
719  Builder.SetInsertPoint(ThenTI);
720 
721  Value *CancelKind = nullptr;
722  switch (CanceledDirective) {
723 #define OMP_CANCEL_KIND(Enum, Str, DirectiveEnum, Value) \
724  case DirectiveEnum: \
725  CancelKind = Builder.getInt32(Value); \
726  break;
727 #include "llvm/Frontend/OpenMP/OMPKinds.def"
728  default:
729  llvm_unreachable("Unknown cancel kind!");
730  }
731 
732  uint32_t SrcLocStrSize;
733  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
734  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
735  Value *Args[] = {Ident, getOrCreateThreadID(Ident), CancelKind};
736  Value *Result = Builder.CreateCall(
737  getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_cancel), Args);
738  auto ExitCB = [this, CanceledDirective, Loc](InsertPointTy IP) {
739  if (CanceledDirective == OMPD_parallel) {
741  Builder.restoreIP(IP);
742  createBarrier(LocationDescription(Builder.saveIP(), Loc.DL),
743  omp::Directive::OMPD_unknown, /* ForceSimpleCall */ false,
744  /* CheckCancelFlag */ false);
745  }
746  };
747 
748  // The actual cancel logic is shared with others, e.g., cancel_barriers.
749  emitCancelationCheckImpl(Result, CanceledDirective, ExitCB);
750 
751  // Update the insertion point and remove the terminator we introduced.
752  Builder.SetInsertPoint(UI->getParent());
753  UI->eraseFromParent();
754 
755  return Builder.saveIP();
756 }
757 
759  uint64_t Size, int32_t Flags,
761  Type *Int8PtrTy = Type::getInt8PtrTy(M.getContext());
762  Type *Int32Ty = Type::getInt32Ty(M.getContext());
763  Type *SizeTy = M.getDataLayout().getIntPtrType(M.getContext());
764 
765  Constant *AddrName = ConstantDataArray::getString(M.getContext(), Name);
766 
767  // Create the constant string used to look up the symbol in the device.
768  auto *Str =
769  new llvm::GlobalVariable(M, AddrName->getType(), /*isConstant=*/true,
771  ".omp_offloading.entry_name");
772  Str->setUnnamedAddr(llvm::GlobalValue::UnnamedAddr::Global);
773 
774  // Construct the offloading entry.
775  Constant *EntryData[] = {
778  ConstantInt::get(SizeTy, Size),
781  };
782  Constant *EntryInitializer =
783  ConstantStruct::get(OpenMPIRBuilder::OffloadEntry, EntryData);
784 
785  auto *Entry = new GlobalVariable(
786  M, OpenMPIRBuilder::OffloadEntry,
787  /* isConstant = */ true, GlobalValue::WeakAnyLinkage, EntryInitializer,
788  ".omp_offloading.entry." + Name, nullptr, GlobalValue::NotThreadLocal,
789  M.getDataLayout().getDefaultGlobalsAddressSpace());
790 
791  // The entry has to be created in the section the linker expects it to be.
792  Entry->setSection(SectionName);
793  Entry->setAlignment(Align(1));
794 }
795 
797  const LocationDescription &Loc, Value *&Return, Value *Ident,
798  Value *DeviceID, Value *NumTeams, Value *NumThreads, Value *HostPtr,
799  ArrayRef<Value *> KernelArgs, ArrayRef<Value *> NoWaitArgs) {
800  if (!updateToLocation(Loc))
801  return Loc.IP;
802 
803  auto *KernelArgsPtr =
804  Builder.CreateAlloca(OpenMPIRBuilder::KernelArgs, nullptr, "kernel_args");
805  for (unsigned I = 0, Size = KernelArgs.size(); I != Size; ++I) {
806  llvm::Value *Arg =
807  Builder.CreateStructGEP(OpenMPIRBuilder::KernelArgs, KernelArgsPtr, I);
808  Builder.CreateAlignedStore(
809  KernelArgs[I], Arg,
810  M.getDataLayout().getPrefTypeAlign(KernelArgs[I]->getType()));
811  }
812 
813  bool HasNoWait = !NoWaitArgs.empty();
814  SmallVector<Value *> OffloadingArgs{Ident, DeviceID, NumTeams,
815  NumThreads, HostPtr, KernelArgsPtr};
816  if (HasNoWait)
817  OffloadingArgs.append(NoWaitArgs.begin(), NoWaitArgs.end());
818 
819  Return = Builder.CreateCall(
820  HasNoWait
821  ? getOrCreateRuntimeFunction(M, OMPRTL___tgt_target_kernel_nowait)
822  : getOrCreateRuntimeFunction(M, OMPRTL___tgt_target_kernel),
823  OffloadingArgs);
824 
825  return Builder.saveIP();
826 }
827 
829  omp::Directive CanceledDirective,
830  FinalizeCallbackTy ExitCB) {
831  assert(isLastFinalizationInfoCancellable(CanceledDirective) &&
832  "Unexpected cancellation!");
833 
834  // For a cancel barrier we create two new blocks.
835  BasicBlock *BB = Builder.GetInsertBlock();
836  BasicBlock *NonCancellationBlock;
837  if (Builder.GetInsertPoint() == BB->end()) {
838  // TODO: This branch will not be needed once we moved to the
839  // OpenMPIRBuilder codegen completely.
840  NonCancellationBlock = BasicBlock::Create(
841  BB->getContext(), BB->getName() + ".cont", BB->getParent());
842  } else {
843  NonCancellationBlock = SplitBlock(BB, &*Builder.GetInsertPoint());
844  BB->getTerminator()->eraseFromParent();
845  Builder.SetInsertPoint(BB);
846  }
847  BasicBlock *CancellationBlock = BasicBlock::Create(
848  BB->getContext(), BB->getName() + ".cncl", BB->getParent());
849 
850  // Jump to them based on the return value.
851  Value *Cmp = Builder.CreateIsNull(CancelFlag);
852  Builder.CreateCondBr(Cmp, NonCancellationBlock, CancellationBlock,
853  /* TODO weight */ nullptr, nullptr);
854 
855  // From the cancellation block we finalize all variables and go to the
856  // post finalization block that is known to the FiniCB callback.
857  Builder.SetInsertPoint(CancellationBlock);
858  if (ExitCB)
859  ExitCB(Builder.saveIP());
860  auto &FI = FinalizationStack.back();
861  FI.FiniCB(Builder.saveIP());
862 
863  // The continuation block is where code generation continues.
864  Builder.SetInsertPoint(NonCancellationBlock, NonCancellationBlock->begin());
865 }
866 
868  const LocationDescription &Loc, InsertPointTy OuterAllocaIP,
869  BodyGenCallbackTy BodyGenCB, PrivatizeCallbackTy PrivCB,
870  FinalizeCallbackTy FiniCB, Value *IfCondition, Value *NumThreads,
871  omp::ProcBindKind ProcBind, bool IsCancellable) {
872  assert(!isConflictIP(Loc.IP, OuterAllocaIP) && "IPs must not be ambiguous");
873 
874  if (!updateToLocation(Loc))
875  return Loc.IP;
876 
877  uint32_t SrcLocStrSize;
878  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
879  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
880  Value *ThreadID = getOrCreateThreadID(Ident);
881 
882  if (NumThreads) {
883  // Build call __kmpc_push_num_threads(&Ident, global_tid, num_threads)
884  Value *Args[] = {
885  Ident, ThreadID,
886  Builder.CreateIntCast(NumThreads, Int32, /*isSigned*/ false)};
887  Builder.CreateCall(
888  getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_push_num_threads), Args);
889  }
890 
891  if (ProcBind != OMP_PROC_BIND_default) {
892  // Build call __kmpc_push_proc_bind(&Ident, global_tid, proc_bind)
893  Value *Args[] = {
894  Ident, ThreadID,
895  ConstantInt::get(Int32, unsigned(ProcBind), /*isSigned=*/true)};
896  Builder.CreateCall(
897  getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_push_proc_bind), Args);
898  }
899 
900  BasicBlock *InsertBB = Builder.GetInsertBlock();
901  Function *OuterFn = InsertBB->getParent();
902 
903  // Save the outer alloca block because the insertion iterator may get
904  // invalidated and we still need this later.
905  BasicBlock *OuterAllocaBlock = OuterAllocaIP.getBlock();
906 
907  // Vector to remember instructions we used only during the modeling but which
908  // we want to delete at the end.
909  SmallVector<Instruction *, 4> ToBeDeleted;
910 
911  // Change the location to the outer alloca insertion point to create and
912  // initialize the allocas we pass into the parallel region.
913  Builder.restoreIP(OuterAllocaIP);
914  AllocaInst *TIDAddr = Builder.CreateAlloca(Int32, nullptr, "tid.addr");
915  AllocaInst *ZeroAddr = Builder.CreateAlloca(Int32, nullptr, "zero.addr");
916 
917  // If there is an if condition we actually use the TIDAddr and ZeroAddr in the
918  // program, otherwise we only need them for modeling purposes to get the
919  // associated arguments in the outlined function. In the former case,
920  // initialize the allocas properly, in the latter case, delete them later.
921  if (IfCondition) {
922  Builder.CreateStore(Constant::getNullValue(Int32), TIDAddr);
923  Builder.CreateStore(Constant::getNullValue(Int32), ZeroAddr);
924  } else {
925  ToBeDeleted.push_back(TIDAddr);
926  ToBeDeleted.push_back(ZeroAddr);
927  }
928 
929  // Create an artificial insertion point that will also ensure the blocks we
930  // are about to split are not degenerated.
931  auto *UI = new UnreachableInst(Builder.getContext(), InsertBB);
932 
933  Instruction *ThenTI = UI, *ElseTI = nullptr;
934  if (IfCondition)
935  SplitBlockAndInsertIfThenElse(IfCondition, UI, &ThenTI, &ElseTI);
936 
937  BasicBlock *ThenBB = ThenTI->getParent();
938  BasicBlock *PRegEntryBB = ThenBB->splitBasicBlock(ThenTI, "omp.par.entry");
939  BasicBlock *PRegBodyBB =
940  PRegEntryBB->splitBasicBlock(ThenTI, "omp.par.region");
941  BasicBlock *PRegPreFiniBB =
942  PRegBodyBB->splitBasicBlock(ThenTI, "omp.par.pre_finalize");
943  BasicBlock *PRegExitBB =
944  PRegPreFiniBB->splitBasicBlock(ThenTI, "omp.par.exit");
945 
946  auto FiniCBWrapper = [&](InsertPointTy IP) {
947  // Hide "open-ended" blocks from the given FiniCB by setting the right jump
948  // target to the region exit block.
949  if (IP.getBlock()->end() == IP.getPoint()) {
951  Builder.restoreIP(IP);
952  Instruction *I = Builder.CreateBr(PRegExitBB);
953  IP = InsertPointTy(I->getParent(), I->getIterator());
954  }
955  assert(IP.getBlock()->getTerminator()->getNumSuccessors() == 1 &&
956  IP.getBlock()->getTerminator()->getSuccessor(0) == PRegExitBB &&
957  "Unexpected insertion point for finalization call!");
958  return FiniCB(IP);
959  };
960 
961  FinalizationStack.push_back({FiniCBWrapper, OMPD_parallel, IsCancellable});
962 
963  // Generate the privatization allocas in the block that will become the entry
964  // of the outlined function.
965  Builder.SetInsertPoint(PRegEntryBB->getTerminator());
966  InsertPointTy InnerAllocaIP = Builder.saveIP();
967 
968  AllocaInst *PrivTIDAddr =
969  Builder.CreateAlloca(Int32, nullptr, "tid.addr.local");
970  Instruction *PrivTID = Builder.CreateLoad(Int32, PrivTIDAddr, "tid");
971 
972  // Add some fake uses for OpenMP provided arguments.
973  ToBeDeleted.push_back(Builder.CreateLoad(Int32, TIDAddr, "tid.addr.use"));
974  Instruction *ZeroAddrUse =
975  Builder.CreateLoad(Int32, ZeroAddr, "zero.addr.use");
976  ToBeDeleted.push_back(ZeroAddrUse);
977 
978  // ThenBB
979  // |
980  // V
981  // PRegionEntryBB <- Privatization allocas are placed here.
982  // |
983  // V
984  // PRegionBodyBB <- BodeGen is invoked here.
985  // |
986  // V
987  // PRegPreFiniBB <- The block we will start finalization from.
988  // |
989  // V
990  // PRegionExitBB <- A common exit to simplify block collection.
991  //
992 
993  LLVM_DEBUG(dbgs() << "Before body codegen: " << *OuterFn << "\n");
994 
995  // Let the caller create the body.
996  assert(BodyGenCB && "Expected body generation callback!");
997  InsertPointTy CodeGenIP(PRegBodyBB, PRegBodyBB->begin());
998  BodyGenCB(InnerAllocaIP, CodeGenIP);
999 
1000  LLVM_DEBUG(dbgs() << "After body codegen: " << *OuterFn << "\n");
1001 
1002  FunctionCallee RTLFn = getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_fork_call);
1003  if (auto *F = dyn_cast<llvm::Function>(RTLFn.getCallee())) {
1004  if (!F->hasMetadata(llvm::LLVMContext::MD_callback)) {
1005  llvm::LLVMContext &Ctx = F->getContext();
1006  MDBuilder MDB(Ctx);
1007  // Annotate the callback behavior of the __kmpc_fork_call:
1008  // - The callback callee is argument number 2 (microtask).
1009  // - The first two arguments of the callback callee are unknown (-1).
1010  // - All variadic arguments to the __kmpc_fork_call are passed to the
1011  // callback callee.
1012  F->addMetadata(
1013  llvm::LLVMContext::MD_callback,
1015  Ctx, {MDB.createCallbackEncoding(2, {-1, -1},
1016  /* VarArgsArePassed */ true)}));
1017  }
1018  }
1019 
1020  OutlineInfo OI;
1021  OI.PostOutlineCB = [=](Function &OutlinedFn) {
1022  // Add some known attributes.
1023  OutlinedFn.addParamAttr(0, Attribute::NoAlias);
1024  OutlinedFn.addParamAttr(1, Attribute::NoAlias);
1025  OutlinedFn.addFnAttr(Attribute::NoUnwind);
1026  OutlinedFn.addFnAttr(Attribute::NoRecurse);
1027 
1028  assert(OutlinedFn.arg_size() >= 2 &&
1029  "Expected at least tid and bounded tid as arguments");
1030  unsigned NumCapturedVars =
1031  OutlinedFn.arg_size() - /* tid & bounded tid */ 2;
1032 
1033  CallInst *CI = cast<CallInst>(OutlinedFn.user_back());
1034  CI->getParent()->setName("omp_parallel");
1035  Builder.SetInsertPoint(CI);
1036 
1037  // Build call __kmpc_fork_call(Ident, n, microtask, var1, .., varn);
1038  Value *ForkCallArgs[] = {
1039  Ident, Builder.getInt32(NumCapturedVars),
1040  Builder.CreateBitCast(&OutlinedFn, ParallelTaskPtr)};
1041 
1042  SmallVector<Value *, 16> RealArgs;
1043  RealArgs.append(std::begin(ForkCallArgs), std::end(ForkCallArgs));
1044  RealArgs.append(CI->arg_begin() + /* tid & bound tid */ 2, CI->arg_end());
1045 
1046  Builder.CreateCall(RTLFn, RealArgs);
1047 
1048  LLVM_DEBUG(dbgs() << "With fork_call placed: "
1049  << *Builder.GetInsertBlock()->getParent() << "\n");
1050 
1051  InsertPointTy ExitIP(PRegExitBB, PRegExitBB->end());
1052 
1053  // Initialize the local TID stack location with the argument value.
1054  Builder.SetInsertPoint(PrivTID);
1055  Function::arg_iterator OutlinedAI = OutlinedFn.arg_begin();
1056  Builder.CreateStore(Builder.CreateLoad(Int32, OutlinedAI), PrivTIDAddr);
1057 
1058  // If no "if" clause was present we do not need the call created during
1059  // outlining, otherwise we reuse it in the serialized parallel region.
1060  if (!ElseTI) {
1061  CI->eraseFromParent();
1062  } else {
1063 
1064  // If an "if" clause was present we are now generating the serialized
1065  // version into the "else" branch.
1066  Builder.SetInsertPoint(ElseTI);
1067 
1068  // Build calls __kmpc_serialized_parallel(&Ident, GTid);
1069  Value *SerializedParallelCallArgs[] = {Ident, ThreadID};
1070  Builder.CreateCall(
1071  getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_serialized_parallel),
1072  SerializedParallelCallArgs);
1073 
1074  // OutlinedFn(&GTid, &zero, CapturedStruct);
1075  CI->removeFromParent();
1076  Builder.Insert(CI);
1077 
1078  // __kmpc_end_serialized_parallel(&Ident, GTid);
1079  Value *EndArgs[] = {Ident, ThreadID};
1080  Builder.CreateCall(
1081  getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_end_serialized_parallel),
1082  EndArgs);
1083 
1084  LLVM_DEBUG(dbgs() << "With serialized parallel region: "
1085  << *Builder.GetInsertBlock()->getParent() << "\n");
1086  }
1087 
1088  for (Instruction *I : ToBeDeleted)
1089  I->eraseFromParent();
1090  };
1091 
1092  // Adjust the finalization stack, verify the adjustment, and call the
1093  // finalize function a last time to finalize values between the pre-fini
1094  // block and the exit block if we left the parallel "the normal way".
1095  auto FiniInfo = FinalizationStack.pop_back_val();
1096  (void)FiniInfo;
1097  assert(FiniInfo.DK == OMPD_parallel &&
1098  "Unexpected finalization stack state!");
1099 
1100  Instruction *PRegPreFiniTI = PRegPreFiniBB->getTerminator();
1101 
1102  InsertPointTy PreFiniIP(PRegPreFiniBB, PRegPreFiniTI->getIterator());
1103  FiniCB(PreFiniIP);
1104 
1105  OI.OuterAllocaBB = OuterAllocaBlock;
1106  OI.EntryBB = PRegEntryBB;
1107  OI.ExitBB = PRegExitBB;
1108 
1109  SmallPtrSet<BasicBlock *, 32> ParallelRegionBlockSet;
1111  OI.collectBlocks(ParallelRegionBlockSet, Blocks);
1112 
1113  // Ensure a single exit node for the outlined region by creating one.
1114  // We might have multiple incoming edges to the exit now due to finalizations,
1115  // e.g., cancel calls that cause the control flow to leave the region.
1116  BasicBlock *PRegOutlinedExitBB = PRegExitBB;
1117  PRegExitBB = SplitBlock(PRegExitBB, &*PRegExitBB->getFirstInsertionPt());
1118  PRegOutlinedExitBB->setName("omp.par.outlined.exit");
1119  Blocks.push_back(PRegOutlinedExitBB);
1120 
1121  CodeExtractorAnalysisCache CEAC(*OuterFn);
1122  CodeExtractor Extractor(Blocks, /* DominatorTree */ nullptr,
1123  /* AggregateArgs */ false,
1124  /* BlockFrequencyInfo */ nullptr,
1125  /* BranchProbabilityInfo */ nullptr,
1126  /* AssumptionCache */ nullptr,
1127  /* AllowVarArgs */ true,
1128  /* AllowAlloca */ true,
1129  /* AllocationBlock */ OuterAllocaBlock,
1130  /* Suffix */ ".omp_par");
1131 
1132  // Find inputs to, outputs from the code region.
1133  BasicBlock *CommonExit = nullptr;
1134  SetVector<Value *> Inputs, Outputs, SinkingCands, HoistingCands;
1135  Extractor.findAllocas(CEAC, SinkingCands, HoistingCands, CommonExit);
1136  Extractor.findInputsOutputs(Inputs, Outputs, SinkingCands);
1137 
1138  LLVM_DEBUG(dbgs() << "Before privatization: " << *OuterFn << "\n");
1139 
1140  FunctionCallee TIDRTLFn =
1141  getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_global_thread_num);
1142 
1143  auto PrivHelper = [&](Value &V) {
1144  if (&V == TIDAddr || &V == ZeroAddr) {
1145  OI.ExcludeArgsFromAggregate.push_back(&V);
1146  return;
1147  }
1148 
1150  for (Use &U : V.uses())
1151  if (auto *UserI = dyn_cast<Instruction>(U.getUser()))
1152  if (ParallelRegionBlockSet.count(UserI->getParent()))
1153  Uses.insert(&U);
1154 
1155  // __kmpc_fork_call expects extra arguments as pointers. If the input
1156  // already has a pointer type, everything is fine. Otherwise, store the
1157  // value onto stack and load it back inside the to-be-outlined region. This
1158  // will ensure only the pointer will be passed to the function.
1159  // FIXME: if there are more than 15 trailing arguments, they must be
1160  // additionally packed in a struct.
1161  Value *Inner = &V;
1162  if (!V.getType()->isPointerTy()) {
1164  LLVM_DEBUG(llvm::dbgs() << "Forwarding input as pointer: " << V << "\n");
1165 
1166  Builder.restoreIP(OuterAllocaIP);
1167  Value *Ptr =
1168  Builder.CreateAlloca(V.getType(), nullptr, V.getName() + ".reloaded");
1169 
1170  // Store to stack at end of the block that currently branches to the entry
1171  // block of the to-be-outlined region.
1172  Builder.SetInsertPoint(InsertBB,
1173  InsertBB->getTerminator()->getIterator());
1174  Builder.CreateStore(&V, Ptr);
1175 
1176  // Load back next to allocations in the to-be-outlined region.
1177  Builder.restoreIP(InnerAllocaIP);
1178  Inner = Builder.CreateLoad(V.getType(), Ptr);
1179  }
1180 
1181  Value *ReplacementValue = nullptr;
1182  CallInst *CI = dyn_cast<CallInst>(&V);
1183  if (CI && CI->getCalledFunction() == TIDRTLFn.getCallee()) {
1184  ReplacementValue = PrivTID;
1185  } else {
1186  Builder.restoreIP(
1187  PrivCB(InnerAllocaIP, Builder.saveIP(), V, *Inner, ReplacementValue));
1188  assert(ReplacementValue &&
1189  "Expected copy/create callback to set replacement value!");
1190  if (ReplacementValue == &V)
1191  return;
1192  }
1193 
1194  for (Use *UPtr : Uses)
1195  UPtr->set(ReplacementValue);
1196  };
1197 
1198  // Reset the inner alloca insertion as it will be used for loading the values
1199  // wrapped into pointers before passing them into the to-be-outlined region.
1200  // Configure it to insert immediately after the fake use of zero address so
1201  // that they are available in the generated body and so that the
1202  // OpenMP-related values (thread ID and zero address pointers) remain leading
1203  // in the argument list.
1204  InnerAllocaIP = IRBuilder<>::InsertPoint(
1205  ZeroAddrUse->getParent(), ZeroAddrUse->getNextNode()->getIterator());
1206 
1207  // Reset the outer alloca insertion point to the entry of the relevant block
1208  // in case it was invalidated.
1209  OuterAllocaIP = IRBuilder<>::InsertPoint(
1210  OuterAllocaBlock, OuterAllocaBlock->getFirstInsertionPt());
1211 
1212  for (Value *Input : Inputs) {
1213  LLVM_DEBUG(dbgs() << "Captured input: " << *Input << "\n");
1214  PrivHelper(*Input);
1215  }
1216  LLVM_DEBUG({
1217  for (Value *Output : Outputs)
1218  LLVM_DEBUG(dbgs() << "Captured output: " << *Output << "\n");
1219  });
1220  assert(Outputs.empty() &&
1221  "OpenMP outlining should not produce live-out values!");
1222 
1223  LLVM_DEBUG(dbgs() << "After privatization: " << *OuterFn << "\n");
1224  LLVM_DEBUG({
1225  for (auto *BB : Blocks)
1226  dbgs() << " PBR: " << BB->getName() << "\n";
1227  });
1228 
1229  // Register the outlined info.
1230  addOutlineInfo(std::move(OI));
1231 
1232  InsertPointTy AfterIP(UI->getParent(), UI->getParent()->end());
1233  UI->eraseFromParent();
1234 
1235  return AfterIP;
1236 }
1237 
1239  // Build call void __kmpc_flush(ident_t *loc)
1240  uint32_t SrcLocStrSize;
1241  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
1242  Value *Args[] = {getOrCreateIdent(SrcLocStr, SrcLocStrSize)};
1243 
1244  Builder.CreateCall(getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_flush), Args);
1245 }
1246 
1248  if (!updateToLocation(Loc))
1249  return;
1250  emitFlush(Loc);
1251 }
1252 
1254  // Build call kmp_int32 __kmpc_omp_taskwait(ident_t *loc, kmp_int32
1255  // global_tid);
1256  uint32_t SrcLocStrSize;
1257  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
1258  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
1259  Value *Args[] = {Ident, getOrCreateThreadID(Ident)};
1260 
1261  // Ignore return result until untied tasks are supported.
1262  Builder.CreateCall(getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_omp_taskwait),
1263  Args);
1264 }
1265 
1267  if (!updateToLocation(Loc))
1268  return;
1269  emitTaskwaitImpl(Loc);
1270 }
1271 
1273  // Build call __kmpc_omp_taskyield(loc, thread_id, 0);
1274  uint32_t SrcLocStrSize;
1275  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
1276  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
1277  Constant *I32Null = ConstantInt::getNullValue(Int32);
1278  Value *Args[] = {Ident, getOrCreateThreadID(Ident), I32Null};
1279 
1280  Builder.CreateCall(getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_omp_taskyield),
1281  Args);
1282 }
1283 
1285  if (!updateToLocation(Loc))
1286  return;
1287  emitTaskyieldImpl(Loc);
1288 }
1289 
1292  InsertPointTy AllocaIP, BodyGenCallbackTy BodyGenCB,
1293  bool Tied, Value *Final, Value *IfCondition,
1294  ArrayRef<DependData *> Dependencies) {
1295  if (!updateToLocation(Loc))
1296  return InsertPointTy();
1297 
1298  uint32_t SrcLocStrSize;
1299  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
1300  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
1301  // The current basic block is split into four basic blocks. After outlining,
1302  // they will be mapped as follows:
1303  // ```
1304  // def current_fn() {
1305  // current_basic_block:
1306  // br label %task.exit
1307  // task.exit:
1308  // ; instructions after task
1309  // }
1310  // def outlined_fn() {
1311  // task.alloca:
1312  // br label %task.body
1313  // task.body:
1314  // ret void
1315  // }
1316  // ```
1317  BasicBlock *TaskExitBB = splitBB(Builder, /*CreateBranch=*/true, "task.exit");
1318  BasicBlock *TaskBodyBB = splitBB(Builder, /*CreateBranch=*/true, "task.body");
1319  BasicBlock *TaskAllocaBB =
1320  splitBB(Builder, /*CreateBranch=*/true, "task.alloca");
1321 
1322  OutlineInfo OI;
1323  OI.EntryBB = TaskAllocaBB;
1324  OI.OuterAllocaBB = AllocaIP.getBlock();
1325  OI.ExitBB = TaskExitBB;
1326  OI.PostOutlineCB = [this, Ident, Tied, Final, IfCondition,
1327  Dependencies](Function &OutlinedFn) {
1328  // The input IR here looks like the following-
1329  // ```
1330  // func @current_fn() {
1331  // outlined_fn(%args)
1332  // }
1333  // func @outlined_fn(%args) { ... }
1334  // ```
1335  //
1336  // This is changed to the following-
1337  //
1338  // ```
1339  // func @current_fn() {
1340  // runtime_call(..., wrapper_fn, ...)
1341  // }
1342  // func @wrapper_fn(..., %args) {
1343  // outlined_fn(%args)
1344  // }
1345  // func @outlined_fn(%args) { ... }
1346  // ```
1347 
1348  // The stale call instruction will be replaced with a new call instruction
1349  // for runtime call with a wrapper function.
1350  assert(OutlinedFn.getNumUses() == 1 &&
1351  "there must be a single user for the outlined function");
1352  CallInst *StaleCI = cast<CallInst>(OutlinedFn.user_back());
1353 
1354  // HasTaskData is true if any variables are captured in the outlined region,
1355  // false otherwise.
1356  bool HasTaskData = StaleCI->arg_size() > 0;
1357  Builder.SetInsertPoint(StaleCI);
1358 
1359  // Gather the arguments for emitting the runtime call for
1360  // @__kmpc_omp_task_alloc
1361  Function *TaskAllocFn =
1362  getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_omp_task_alloc);
1363 
1364  // Arguments - `loc_ref` (Ident) and `gtid` (ThreadID)
1365  // call.
1366  Value *ThreadID = getOrCreateThreadID(Ident);
1367 
1368  // Argument - `flags`
1369  // Task is tied iff (Flags & 1) == 1.
1370  // Task is untied iff (Flags & 1) == 0.
1371  // Task is final iff (Flags & 2) == 2.
1372  // Task is not final iff (Flags & 2) == 0.
1373  // TODO: Handle the other flags.
1374  Value *Flags = Builder.getInt32(Tied);
1375  if (Final) {
1376  Value *FinalFlag =
1377  Builder.CreateSelect(Final, Builder.getInt32(2), Builder.getInt32(0));
1378  Flags = Builder.CreateOr(FinalFlag, Flags);
1379  }
1380 
1381  // Argument - `sizeof_kmp_task_t` (TaskSize)
1382  // Tasksize refers to the size in bytes of kmp_task_t data structure
1383  // including private vars accessed in task.
1384  Value *TaskSize = Builder.getInt64(0);
1385  if (HasTaskData) {
1386  AllocaInst *ArgStructAlloca =
1387  dyn_cast<AllocaInst>(StaleCI->getArgOperand(0));
1388  assert(ArgStructAlloca &&
1389  "Unable to find the alloca instruction corresponding to arguments "
1390  "for extracted function");
1391  StructType *ArgStructType =
1392  dyn_cast<StructType>(ArgStructAlloca->getAllocatedType());
1393  assert(ArgStructType && "Unable to find struct type corresponding to "
1394  "arguments for extracted function");
1395  TaskSize =
1396  Builder.getInt64(M.getDataLayout().getTypeStoreSize(ArgStructType));
1397  }
1398 
1399  // TODO: Argument - sizeof_shareds
1400 
1401  // Argument - task_entry (the wrapper function)
1402  // If the outlined function has some captured variables (i.e. HasTaskData is
1403  // true), then the wrapper function will have an additional argument (the
1404  // struct containing captured variables). Otherwise, no such argument will
1405  // be present.
1406  SmallVector<Type *> WrapperArgTys{Builder.getInt32Ty()};
1407  if (HasTaskData)
1408  WrapperArgTys.push_back(OutlinedFn.getArg(0)->getType());
1409  FunctionCallee WrapperFuncVal = M.getOrInsertFunction(
1410  (Twine(OutlinedFn.getName()) + ".wrapper").str(),
1411  FunctionType::get(Builder.getInt32Ty(), WrapperArgTys, false));
1412  Function *WrapperFunc = dyn_cast<Function>(WrapperFuncVal.getCallee());
1413  PointerType *WrapperFuncBitcastType =
1414  FunctionType::get(Builder.getInt32Ty(),
1415  {Builder.getInt32Ty(), Builder.getInt8PtrTy()}, false)
1416  ->getPointerTo();
1417  Value *WrapperFuncBitcast =
1418  ConstantExpr::getBitCast(WrapperFunc, WrapperFuncBitcastType);
1419 
1420  // Emit the @__kmpc_omp_task_alloc runtime call
1421  // The runtime call returns a pointer to an area where the task captured
1422  // variables must be copied before the task is run (NewTaskData)
1423  CallInst *NewTaskData = Builder.CreateCall(
1424  TaskAllocFn,
1425  {/*loc_ref=*/Ident, /*gtid=*/ThreadID, /*flags=*/Flags,
1426  /*sizeof_task=*/TaskSize, /*sizeof_shared=*/Builder.getInt64(0),
1427  /*task_func=*/WrapperFuncBitcast});
1428 
1429  // Copy the arguments for outlined function
1430  if (HasTaskData) {
1431  Value *TaskData = StaleCI->getArgOperand(0);
1432  Align Alignment = TaskData->getPointerAlignment(M.getDataLayout());
1433  Builder.CreateMemCpy(NewTaskData, Alignment, TaskData, Alignment,
1434  TaskSize);
1435  }
1436 
1437  Value *DepArrayPtr = nullptr;
1438  if (Dependencies.size()) {
1439  InsertPointTy OldIP = Builder.saveIP();
1440  Builder.SetInsertPoint(
1441  &OldIP.getBlock()->getParent()->getEntryBlock().back());
1442 
1443  Type *DepArrayTy = ArrayType::get(DependInfo, Dependencies.size());
1444  Value *DepArray =
1445  Builder.CreateAlloca(DepArrayTy, nullptr, ".dep.arr.addr");
1446 
1447  unsigned P = 0;
1448  for (DependData *Dep : Dependencies) {
1449  Value *Base =
1450  Builder.CreateConstInBoundsGEP2_64(DepArrayTy, DepArray, 0, P);
1451  // Store the pointer to the variable
1452  Value *Addr = Builder.CreateStructGEP(
1453  DependInfo, Base,
1454  static_cast<unsigned int>(RTLDependInfoFields::BaseAddr));
1455  Value *DepValPtr =
1456  Builder.CreatePtrToInt(Dep->DepVal, Builder.getInt64Ty());
1457  Builder.CreateStore(DepValPtr, Addr);
1458  // Store the size of the variable
1459  Value *Size = Builder.CreateStructGEP(
1460  DependInfo, Base,
1461  static_cast<unsigned int>(RTLDependInfoFields::Len));
1462  Builder.CreateStore(Builder.getInt64(M.getDataLayout().getTypeStoreSize(
1463  Dep->DepValueType)),
1464  Size);
1465  // Store the dependency kind
1466  Value *Flags = Builder.CreateStructGEP(
1467  DependInfo, Base,
1468  static_cast<unsigned int>(RTLDependInfoFields::Flags));
1469  Builder.CreateStore(
1470  ConstantInt::get(Builder.getInt8Ty(),
1471  static_cast<unsigned int>(Dep->DepKind)),
1472  Flags);
1473  ++P;
1474  }
1475 
1476  DepArrayPtr = Builder.CreateBitCast(DepArray, Builder.getInt8PtrTy());
1477  Builder.restoreIP(OldIP);
1478  }
1479 
1480  // In the presence of the `if` clause, the following IR is generated:
1481  // ...
1482  // %data = call @__kmpc_omp_task_alloc(...)
1483  // br i1 %if_condition, label %then, label %else
1484  // then:
1485  // call @__kmpc_omp_task(...)
1486  // br label %exit
1487  // else:
1488  // call @__kmpc_omp_task_begin_if0(...)
1489  // call @wrapper_fn(...)
1490  // call @__kmpc_omp_task_complete_if0(...)
1491  // br label %exit
1492  // exit:
1493  // ...
1494  if (IfCondition) {
1495  // `SplitBlockAndInsertIfThenElse` requires the block to have a
1496  // terminator.
1497  BasicBlock *NewBasicBlock =
1498  splitBB(Builder, /*CreateBranch=*/true, "if.end");
1499  Instruction *IfTerminator =
1500  NewBasicBlock->getSinglePredecessor()->getTerminator();
1501  Instruction *ThenTI = IfTerminator, *ElseTI = nullptr;
1502  Builder.SetInsertPoint(IfTerminator);
1503  SplitBlockAndInsertIfThenElse(IfCondition, IfTerminator, &ThenTI,
1504  &ElseTI);
1505  Builder.SetInsertPoint(ElseTI);
1506  Function *TaskBeginFn =
1507  getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_omp_task_begin_if0);
1508  Function *TaskCompleteFn =
1509  getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_omp_task_complete_if0);
1510  Builder.CreateCall(TaskBeginFn, {Ident, ThreadID, NewTaskData});
1511  if (HasTaskData)
1512  Builder.CreateCall(WrapperFunc, {ThreadID, NewTaskData});
1513  else
1514  Builder.CreateCall(WrapperFunc, {ThreadID});
1515  Builder.CreateCall(TaskCompleteFn, {Ident, ThreadID, NewTaskData});
1516  Builder.SetInsertPoint(ThenTI);
1517  }
1518 
1519  if (Dependencies.size()) {
1520  Function *TaskFn =
1521  getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_omp_task_with_deps);
1522  Builder.CreateCall(
1523  TaskFn,
1524  {Ident, ThreadID, NewTaskData, Builder.getInt32(Dependencies.size()),
1525  DepArrayPtr, ConstantInt::get(Builder.getInt32Ty(), 0),
1527 
1528  } else {
1529  // Emit the @__kmpc_omp_task runtime call to spawn the task
1530  Function *TaskFn = getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_omp_task);
1531  Builder.CreateCall(TaskFn, {Ident, ThreadID, NewTaskData});
1532  }
1533 
1534  StaleCI->eraseFromParent();
1535 
1536  // Emit the body for wrapper function
1537  BasicBlock *WrapperEntryBB =
1538  BasicBlock::Create(M.getContext(), "", WrapperFunc);
1539  Builder.SetInsertPoint(WrapperEntryBB);
1540  if (HasTaskData)
1541  Builder.CreateCall(&OutlinedFn, {WrapperFunc->getArg(1)});
1542  else
1543  Builder.CreateCall(&OutlinedFn);
1544  Builder.CreateRet(Builder.getInt32(0));
1545  };
1546 
1547  addOutlineInfo(std::move(OI));
1548 
1549  InsertPointTy TaskAllocaIP =
1550  InsertPointTy(TaskAllocaBB, TaskAllocaBB->begin());
1551  InsertPointTy TaskBodyIP = InsertPointTy(TaskBodyBB, TaskBodyBB->begin());
1552  BodyGenCB(TaskAllocaIP, TaskBodyIP);
1553  Builder.SetInsertPoint(TaskExitBB, TaskExitBB->begin());
1554 
1555  return Builder.saveIP();
1556 }
1557 
1560  InsertPointTy AllocaIP,
1561  BodyGenCallbackTy BodyGenCB) {
1562  if (!updateToLocation(Loc))
1563  return InsertPointTy();
1564 
1565  uint32_t SrcLocStrSize;
1566  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
1567  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
1568  Value *ThreadID = getOrCreateThreadID(Ident);
1569 
1570  // Emit the @__kmpc_taskgroup runtime call to start the taskgroup
1571  Function *TaskgroupFn =
1572  getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_taskgroup);
1573  Builder.CreateCall(TaskgroupFn, {Ident, ThreadID});
1574 
1575  BasicBlock *TaskgroupExitBB = splitBB(Builder, true, "taskgroup.exit");
1576  BodyGenCB(AllocaIP, Builder.saveIP());
1577 
1578  Builder.SetInsertPoint(TaskgroupExitBB);
1579  // Emit the @__kmpc_end_taskgroup runtime call to end the taskgroup
1580  Function *EndTaskgroupFn =
1581  getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_end_taskgroup);
1582  Builder.CreateCall(EndTaskgroupFn, {Ident, ThreadID});
1583 
1584  return Builder.saveIP();
1585 }
1586 
1588  const LocationDescription &Loc, InsertPointTy AllocaIP,
1590  FinalizeCallbackTy FiniCB, bool IsCancellable, bool IsNowait) {
1591  assert(!isConflictIP(AllocaIP, Loc.IP) && "Dedicated IP allocas required");
1592 
1593  if (!updateToLocation(Loc))
1594  return Loc.IP;
1595 
1596  auto FiniCBWrapper = [&](InsertPointTy IP) {
1597  if (IP.getBlock()->end() != IP.getPoint())
1598  return FiniCB(IP);
1599  // This must be done otherwise any nested constructs using FinalizeOMPRegion
1600  // will fail because that function requires the Finalization Basic Block to
1601  // have a terminator, which is already removed by EmitOMPRegionBody.
1602  // IP is currently at cancelation block.
1603  // We need to backtrack to the condition block to fetch
1604  // the exit block and create a branch from cancelation
1605  // to exit block.
1607  Builder.restoreIP(IP);
1608  auto *CaseBB = IP.getBlock()->getSinglePredecessor();
1609  auto *CondBB = CaseBB->getSinglePredecessor()->getSinglePredecessor();
1610  auto *ExitBB = CondBB->getTerminator()->getSuccessor(1);
1611  Instruction *I = Builder.CreateBr(ExitBB);
1612  IP = InsertPointTy(I->getParent(), I->getIterator());
1613  return FiniCB(IP);
1614  };
1615 
1616  FinalizationStack.push_back({FiniCBWrapper, OMPD_sections, IsCancellable});
1617 
1618  // Each section is emitted as a switch case
1619  // Each finalization callback is handled from clang.EmitOMPSectionDirective()
1620  // -> OMP.createSection() which generates the IR for each section
1621  // Iterate through all sections and emit a switch construct:
1622  // switch (IV) {
1623  // case 0:
1624  // <SectionStmt[0]>;
1625  // break;
1626  // ...
1627  // case <NumSection> - 1:
1628  // <SectionStmt[<NumSection> - 1]>;
1629  // break;
1630  // }
1631  // ...
1632  // section_loop.after:
1633  // <FiniCB>;
1634  auto LoopBodyGenCB = [&](InsertPointTy CodeGenIP, Value *IndVar) {
1635  Builder.restoreIP(CodeGenIP);
1636  BasicBlock *Continue =
1637  splitBBWithSuffix(Builder, /*CreateBranch=*/false, ".sections.after");
1638  Function *CurFn = Continue->getParent();
1639  SwitchInst *SwitchStmt = Builder.CreateSwitch(IndVar, Continue);
1640 
1641  unsigned CaseNumber = 0;
1642  for (auto SectionCB : SectionCBs) {
1643  BasicBlock *CaseBB = BasicBlock::Create(
1644  M.getContext(), "omp_section_loop.body.case", CurFn, Continue);
1645  SwitchStmt->addCase(Builder.getInt32(CaseNumber), CaseBB);
1646  Builder.SetInsertPoint(CaseBB);
1647  BranchInst *CaseEndBr = Builder.CreateBr(Continue);
1648  SectionCB(InsertPointTy(),
1649  {CaseEndBr->getParent(), CaseEndBr->getIterator()});
1650  CaseNumber++;
1651  }
1652  // remove the existing terminator from body BB since there can be no
1653  // terminators after switch/case
1654  };
1655  // Loop body ends here
1656  // LowerBound, UpperBound, and STride for createCanonicalLoop
1657  Type *I32Ty = Type::getInt32Ty(M.getContext());
1658  Value *LB = ConstantInt::get(I32Ty, 0);
1659  Value *UB = ConstantInt::get(I32Ty, SectionCBs.size());
1660  Value *ST = ConstantInt::get(I32Ty, 1);
1661  llvm::CanonicalLoopInfo *LoopInfo = createCanonicalLoop(
1662  Loc, LoopBodyGenCB, LB, UB, ST, true, false, AllocaIP, "section_loop");
1663  InsertPointTy AfterIP =
1664  applyStaticWorkshareLoop(Loc.DL, LoopInfo, AllocaIP, !IsNowait);
1665 
1666  // Apply the finalization callback in LoopAfterBB
1667  auto FiniInfo = FinalizationStack.pop_back_val();
1668  assert(FiniInfo.DK == OMPD_sections &&
1669  "Unexpected finalization stack state!");
1670  if (FinalizeCallbackTy &CB = FiniInfo.FiniCB) {
1671  Builder.restoreIP(AfterIP);
1672  BasicBlock *FiniBB =
1673  splitBBWithSuffix(Builder, /*CreateBranch=*/true, "sections.fini");
1674  CB(Builder.saveIP());
1675  AfterIP = {FiniBB, FiniBB->begin()};
1676  }
1677 
1678  return AfterIP;
1679 }
1680 
1683  BodyGenCallbackTy BodyGenCB,
1684  FinalizeCallbackTy FiniCB) {
1685  if (!updateToLocation(Loc))
1686  return Loc.IP;
1687 
1688  auto FiniCBWrapper = [&](InsertPointTy IP) {
1689  if (IP.getBlock()->end() != IP.getPoint())
1690  return FiniCB(IP);
1691  // This must be done otherwise any nested constructs using FinalizeOMPRegion
1692  // will fail because that function requires the Finalization Basic Block to
1693  // have a terminator, which is already removed by EmitOMPRegionBody.
1694  // IP is currently at cancelation block.
1695  // We need to backtrack to the condition block to fetch
1696  // the exit block and create a branch from cancelation
1697  // to exit block.
1699  Builder.restoreIP(IP);
1700  auto *CaseBB = Loc.IP.getBlock();
1701  auto *CondBB = CaseBB->getSinglePredecessor()->getSinglePredecessor();
1702  auto *ExitBB = CondBB->getTerminator()->getSuccessor(1);
1703  Instruction *I = Builder.CreateBr(ExitBB);
1704  IP = InsertPointTy(I->getParent(), I->getIterator());
1705  return FiniCB(IP);
1706  };
1707 
1708  Directive OMPD = Directive::OMPD_sections;
1709  // Since we are using Finalization Callback here, HasFinalize
1710  // and IsCancellable have to be true
1711  return EmitOMPInlinedRegion(OMPD, nullptr, nullptr, BodyGenCB, FiniCBWrapper,
1712  /*Conditional*/ false, /*hasFinalize*/ true,
1713  /*IsCancellable*/ true);
1714 }
1715 
1716 /// Create a function with a unique name and a "void (i8*, i8*)" signature in
1717 /// the given module and return it.
1719  Type *VoidTy = Type::getVoidTy(M.getContext());
1720  Type *Int8PtrTy = Type::getInt8PtrTy(M.getContext());
1721  auto *FuncTy =
1722  FunctionType::get(VoidTy, {Int8PtrTy, Int8PtrTy}, /* IsVarArg */ false);
1724  M.getDataLayout().getDefaultGlobalsAddressSpace(),
1725  ".omp.reduction.func", &M);
1726 }
1727 
1729  const LocationDescription &Loc, InsertPointTy AllocaIP,
1730  ArrayRef<ReductionInfo> ReductionInfos, bool IsNoWait) {
1731  for (const ReductionInfo &RI : ReductionInfos) {
1732  (void)RI;
1733  assert(RI.Variable && "expected non-null variable");
1734  assert(RI.PrivateVariable && "expected non-null private variable");
1735  assert(RI.ReductionGen && "expected non-null reduction generator callback");
1736  assert(RI.Variable->getType() == RI.PrivateVariable->getType() &&
1737  "expected variables and their private equivalents to have the same "
1738  "type");
1739  assert(RI.Variable->getType()->isPointerTy() &&
1740  "expected variables to be pointers");
1741  }
1742 
1743  if (!updateToLocation(Loc))
1744  return InsertPointTy();
1745 
1746  BasicBlock *InsertBlock = Loc.IP.getBlock();
1747  BasicBlock *ContinuationBlock =
1748  InsertBlock->splitBasicBlock(Loc.IP.getPoint(), "reduce.finalize");
1749  InsertBlock->getTerminator()->eraseFromParent();
1750 
1751  // Create and populate array of type-erased pointers to private reduction
1752  // values.
1753  unsigned NumReductions = ReductionInfos.size();
1754  Type *RedArrayTy = ArrayType::get(Builder.getInt8PtrTy(), NumReductions);
1755  Builder.restoreIP(AllocaIP);
1756  Value *RedArray = Builder.CreateAlloca(RedArrayTy, nullptr, "red.array");
1757 
1758  Builder.SetInsertPoint(InsertBlock, InsertBlock->end());
1759 
1760  for (auto En : enumerate(ReductionInfos)) {
1761  unsigned Index = En.index();
1762  const ReductionInfo &RI = En.value();
1763  Value *RedArrayElemPtr = Builder.CreateConstInBoundsGEP2_64(
1764  RedArrayTy, RedArray, 0, Index, "red.array.elem." + Twine(Index));
1765  Value *Casted =
1766  Builder.CreateBitCast(RI.PrivateVariable, Builder.getInt8PtrTy(),
1767  "private.red.var." + Twine(Index) + ".casted");
1768  Builder.CreateStore(Casted, RedArrayElemPtr);
1769  }
1770 
1771  // Emit a call to the runtime function that orchestrates the reduction.
1772  // Declare the reduction function in the process.
1773  Function *Func = Builder.GetInsertBlock()->getParent();
1774  Module *Module = Func->getParent();
1775  Value *RedArrayPtr =
1776  Builder.CreateBitCast(RedArray, Builder.getInt8PtrTy(), "red.array.ptr");
1777  uint32_t SrcLocStrSize;
1778  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
1779  bool CanGenerateAtomic =
1780  llvm::all_of(ReductionInfos, [](const ReductionInfo &RI) {
1781  return RI.AtomicReductionGen;
1782  });
1783  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize,
1784  CanGenerateAtomic
1785  ? IdentFlag::OMP_IDENT_FLAG_ATOMIC_REDUCE
1786  : IdentFlag(0));
1787  Value *ThreadId = getOrCreateThreadID(Ident);
1788  Constant *NumVariables = Builder.getInt32(NumReductions);
1789  const DataLayout &DL = Module->getDataLayout();
1790  unsigned RedArrayByteSize = DL.getTypeStoreSize(RedArrayTy);
1791  Constant *RedArraySize = Builder.getInt64(RedArrayByteSize);
1792  Function *ReductionFunc = getFreshReductionFunc(*Module);
1793  Value *Lock = getOMPCriticalRegionLock(".reduction");
1794  Function *ReduceFunc = getOrCreateRuntimeFunctionPtr(
1795  IsNoWait ? RuntimeFunction::OMPRTL___kmpc_reduce_nowait
1796  : RuntimeFunction::OMPRTL___kmpc_reduce);
1797  CallInst *ReduceCall =
1798  Builder.CreateCall(ReduceFunc,
1799  {Ident, ThreadId, NumVariables, RedArraySize,
1800  RedArrayPtr, ReductionFunc, Lock},
1801  "reduce");
1802 
1803  // Create final reduction entry blocks for the atomic and non-atomic case.
1804  // Emit IR that dispatches control flow to one of the blocks based on the
1805  // reduction supporting the atomic mode.
1806  BasicBlock *NonAtomicRedBlock =
1807  BasicBlock::Create(Module->getContext(), "reduce.switch.nonatomic", Func);
1808  BasicBlock *AtomicRedBlock =
1809  BasicBlock::Create(Module->getContext(), "reduce.switch.atomic", Func);
1810  SwitchInst *Switch =
1811  Builder.CreateSwitch(ReduceCall, ContinuationBlock, /* NumCases */ 2);
1812  Switch->addCase(Builder.getInt32(1), NonAtomicRedBlock);
1813  Switch->addCase(Builder.getInt32(2), AtomicRedBlock);
1814 
1815  // Populate the non-atomic reduction using the elementwise reduction function.
1816  // This loads the elements from the global and private variables and reduces
1817  // them before storing back the result to the global variable.
1818  Builder.SetInsertPoint(NonAtomicRedBlock);
1819  for (auto En : enumerate(ReductionInfos)) {
1820  const ReductionInfo &RI = En.value();
1821  Type *ValueType = RI.ElementType;
1822  Value *RedValue = Builder.CreateLoad(ValueType, RI.Variable,
1823  "red.value." + Twine(En.index()));
1824  Value *PrivateRedValue =
1825  Builder.CreateLoad(ValueType, RI.PrivateVariable,
1826  "red.private.value." + Twine(En.index()));
1827  Value *Reduced;
1828  Builder.restoreIP(
1829  RI.ReductionGen(Builder.saveIP(), RedValue, PrivateRedValue, Reduced));
1830  if (!Builder.GetInsertBlock())
1831  return InsertPointTy();
1832  Builder.CreateStore(Reduced, RI.Variable);
1833  }
1834  Function *EndReduceFunc = getOrCreateRuntimeFunctionPtr(
1835  IsNoWait ? RuntimeFunction::OMPRTL___kmpc_end_reduce_nowait
1836  : RuntimeFunction::OMPRTL___kmpc_end_reduce);
1837  Builder.CreateCall(EndReduceFunc, {Ident, ThreadId, Lock});
1838  Builder.CreateBr(ContinuationBlock);
1839 
1840  // Populate the atomic reduction using the atomic elementwise reduction
1841  // function. There are no loads/stores here because they will be happening
1842  // inside the atomic elementwise reduction.
1843  Builder.SetInsertPoint(AtomicRedBlock);
1844  if (CanGenerateAtomic) {
1845  for (const ReductionInfo &RI : ReductionInfos) {
1846  Builder.restoreIP(RI.AtomicReductionGen(Builder.saveIP(), RI.ElementType,
1847  RI.Variable, RI.PrivateVariable));
1848  if (!Builder.GetInsertBlock())
1849  return InsertPointTy();
1850  }
1851  Builder.CreateBr(ContinuationBlock);
1852  } else {
1853  Builder.CreateUnreachable();
1854  }
1855 
1856  // Populate the outlined reduction function using the elementwise reduction
1857  // function. Partial values are extracted from the type-erased array of
1858  // pointers to private variables.
1859  BasicBlock *ReductionFuncBlock =
1860  BasicBlock::Create(Module->getContext(), "", ReductionFunc);
1861  Builder.SetInsertPoint(ReductionFuncBlock);
1862  Value *LHSArrayPtr = Builder.CreateBitCast(ReductionFunc->getArg(0),
1863  RedArrayTy->getPointerTo());
1864  Value *RHSArrayPtr = Builder.CreateBitCast(ReductionFunc->getArg(1),
1865  RedArrayTy->getPointerTo());
1866  for (auto En : enumerate(ReductionInfos)) {
1867  const ReductionInfo &RI = En.value();
1868  Value *LHSI8PtrPtr = Builder.CreateConstInBoundsGEP2_64(
1869  RedArrayTy, LHSArrayPtr, 0, En.index());
1870  Value *LHSI8Ptr = Builder.CreateLoad(Builder.getInt8PtrTy(), LHSI8PtrPtr);
1871  Value *LHSPtr = Builder.CreateBitCast(LHSI8Ptr, RI.Variable->getType());
1872  Value *LHS = Builder.CreateLoad(RI.ElementType, LHSPtr);
1873  Value *RHSI8PtrPtr = Builder.CreateConstInBoundsGEP2_64(
1874  RedArrayTy, RHSArrayPtr, 0, En.index());
1875  Value *RHSI8Ptr = Builder.CreateLoad(Builder.getInt8PtrTy(), RHSI8PtrPtr);
1876  Value *RHSPtr =
1877  Builder.CreateBitCast(RHSI8Ptr, RI.PrivateVariable->getType());
1878  Value *RHS = Builder.CreateLoad(RI.ElementType, RHSPtr);
1879  Value *Reduced;
1880  Builder.restoreIP(RI.ReductionGen(Builder.saveIP(), LHS, RHS, Reduced));
1881  if (!Builder.GetInsertBlock())
1882  return InsertPointTy();
1883  Builder.CreateStore(Reduced, LHSPtr);
1884  }
1885  Builder.CreateRetVoid();
1886 
1887  Builder.SetInsertPoint(ContinuationBlock);
1888  return Builder.saveIP();
1889 }
1890 
1893  BodyGenCallbackTy BodyGenCB,
1894  FinalizeCallbackTy FiniCB) {
1895 
1896  if (!updateToLocation(Loc))
1897  return Loc.IP;
1898 
1899  Directive OMPD = Directive::OMPD_master;
1900  uint32_t SrcLocStrSize;
1901  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
1902  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
1903  Value *ThreadId = getOrCreateThreadID(Ident);
1904  Value *Args[] = {Ident, ThreadId};
1905 
1906  Function *EntryRTLFn = getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_master);
1907  Instruction *EntryCall = Builder.CreateCall(EntryRTLFn, Args);
1908 
1909  Function *ExitRTLFn = getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_end_master);
1910  Instruction *ExitCall = Builder.CreateCall(ExitRTLFn, Args);
1911 
1912  return EmitOMPInlinedRegion(OMPD, EntryCall, ExitCall, BodyGenCB, FiniCB,
1913  /*Conditional*/ true, /*hasFinalize*/ true);
1914 }
1915 
1918  BodyGenCallbackTy BodyGenCB,
1919  FinalizeCallbackTy FiniCB, Value *Filter) {
1920  if (!updateToLocation(Loc))
1921  return Loc.IP;
1922 
1923  Directive OMPD = Directive::OMPD_masked;
1924  uint32_t SrcLocStrSize;
1925  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
1926  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
1927  Value *ThreadId = getOrCreateThreadID(Ident);
1928  Value *Args[] = {Ident, ThreadId, Filter};
1929  Value *ArgsEnd[] = {Ident, ThreadId};
1930 
1931  Function *EntryRTLFn = getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_masked);
1932  Instruction *EntryCall = Builder.CreateCall(EntryRTLFn, Args);
1933 
1934  Function *ExitRTLFn = getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_end_masked);
1935  Instruction *ExitCall = Builder.CreateCall(ExitRTLFn, ArgsEnd);
1936 
1937  return EmitOMPInlinedRegion(OMPD, EntryCall, ExitCall, BodyGenCB, FiniCB,
1938  /*Conditional*/ true, /*hasFinalize*/ true);
1939 }
1940 
1942  DebugLoc DL, Value *TripCount, Function *F, BasicBlock *PreInsertBefore,
1943  BasicBlock *PostInsertBefore, const Twine &Name) {
1944  Module *M = F->getParent();
1945  LLVMContext &Ctx = M->getContext();
1946  Type *IndVarTy = TripCount->getType();
1947 
1948  // Create the basic block structure.
1949  BasicBlock *Preheader =
1950  BasicBlock::Create(Ctx, "omp_" + Name + ".preheader", F, PreInsertBefore);
1951  BasicBlock *Header =
1952  BasicBlock::Create(Ctx, "omp_" + Name + ".header", F, PreInsertBefore);
1953  BasicBlock *Cond =
1954  BasicBlock::Create(Ctx, "omp_" + Name + ".cond", F, PreInsertBefore);
1955  BasicBlock *Body =
1956  BasicBlock::Create(Ctx, "omp_" + Name + ".body", F, PreInsertBefore);
1957  BasicBlock *Latch =
1958  BasicBlock::Create(Ctx, "omp_" + Name + ".inc", F, PostInsertBefore);
1959  BasicBlock *Exit =
1960  BasicBlock::Create(Ctx, "omp_" + Name + ".exit", F, PostInsertBefore);
1961  BasicBlock *After =
1962  BasicBlock::Create(Ctx, "omp_" + Name + ".after", F, PostInsertBefore);
1963 
1964  // Use specified DebugLoc for new instructions.
1965  Builder.SetCurrentDebugLocation(DL);
1966 
1967  Builder.SetInsertPoint(Preheader);
1968  Builder.CreateBr(Header);
1969 
1970  Builder.SetInsertPoint(Header);
1971  PHINode *IndVarPHI = Builder.CreatePHI(IndVarTy, 2, "omp_" + Name + ".iv");
1972  IndVarPHI->addIncoming(ConstantInt::get(IndVarTy, 0), Preheader);
1973  Builder.CreateBr(Cond);
1974 
1975  Builder.SetInsertPoint(Cond);
1976  Value *Cmp =
1977  Builder.CreateICmpULT(IndVarPHI, TripCount, "omp_" + Name + ".cmp");
1978  Builder.CreateCondBr(Cmp, Body, Exit);
1979 
1980  Builder.SetInsertPoint(Body);
1981  Builder.CreateBr(Latch);
1982 
1983  Builder.SetInsertPoint(Latch);
1984  Value *Next = Builder.CreateAdd(IndVarPHI, ConstantInt::get(IndVarTy, 1),
1985  "omp_" + Name + ".next", /*HasNUW=*/true);
1986  Builder.CreateBr(Header);
1987  IndVarPHI->addIncoming(Next, Latch);
1988 
1989  Builder.SetInsertPoint(Exit);
1990  Builder.CreateBr(After);
1991 
1992  // Remember and return the canonical control flow.
1993  LoopInfos.emplace_front();
1994  CanonicalLoopInfo *CL = &LoopInfos.front();
1995 
1996  CL->Header = Header;
1997  CL->Cond = Cond;
1998  CL->Latch = Latch;
1999  CL->Exit = Exit;
2000 
2001 #ifndef NDEBUG
2002  CL->assertOK();
2003 #endif
2004  return CL;
2005 }
2006 
2009  LoopBodyGenCallbackTy BodyGenCB,
2010  Value *TripCount, const Twine &Name) {
2011  BasicBlock *BB = Loc.IP.getBlock();
2012  BasicBlock *NextBB = BB->getNextNode();
2013 
2014  CanonicalLoopInfo *CL = createLoopSkeleton(Loc.DL, TripCount, BB->getParent(),
2015  NextBB, NextBB, Name);
2016  BasicBlock *After = CL->getAfter();
2017 
2018  // If location is not set, don't connect the loop.
2019  if (updateToLocation(Loc)) {
2020  // Split the loop at the insertion point: Branch to the preheader and move
2021  // every following instruction to after the loop (the After BB). Also, the
2022  // new successor is the loop's after block.
2023  spliceBB(Builder, After, /*CreateBranch=*/false);
2024  Builder.CreateBr(CL->getPreheader());
2025  }
2026 
2027  // Emit the body content. We do it after connecting the loop to the CFG to
2028  // avoid that the callback encounters degenerate BBs.
2029  BodyGenCB(CL->getBodyIP(), CL->getIndVar());
2030 
2031 #ifndef NDEBUG
2032  CL->assertOK();
2033 #endif
2034  return CL;
2035 }
2036 
2038  const LocationDescription &Loc, LoopBodyGenCallbackTy BodyGenCB,
2039  Value *Start, Value *Stop, Value *Step, bool IsSigned, bool InclusiveStop,
2040  InsertPointTy ComputeIP, const Twine &Name) {
2041 
2042  // Consider the following difficulties (assuming 8-bit signed integers):
2043  // * Adding \p Step to the loop counter which passes \p Stop may overflow:
2044  // DO I = 1, 100, 50
2045  /// * A \p Step of INT_MIN cannot not be normalized to a positive direction:
2046  // DO I = 100, 0, -128
2047 
2048  // Start, Stop and Step must be of the same integer type.
2049  auto *IndVarTy = cast<IntegerType>(Start->getType());
2050  assert(IndVarTy == Stop->getType() && "Stop type mismatch");
2051  assert(IndVarTy == Step->getType() && "Step type mismatch");
2052 
2053  LocationDescription ComputeLoc =
2054  ComputeIP.isSet() ? LocationDescription(ComputeIP, Loc.DL) : Loc;
2055  updateToLocation(ComputeLoc);
2056 
2057  ConstantInt *Zero = ConstantInt::get(IndVarTy, 0);
2058  ConstantInt *One = ConstantInt::get(IndVarTy, 1);
2059 
2060  // Like Step, but always positive.
2061  Value *Incr = Step;
2062 
2063  // Distance between Start and Stop; always positive.
2064  Value *Span;
2065 
2066  // Condition whether there are no iterations are executed at all, e.g. because
2067  // UB < LB.
2068  Value *ZeroCmp;
2069 
2070  if (IsSigned) {
2071  // Ensure that increment is positive. If not, negate and invert LB and UB.
2072  Value *IsNeg = Builder.CreateICmpSLT(Step, Zero);
2073  Incr = Builder.CreateSelect(IsNeg, Builder.CreateNeg(Step), Step);
2074  Value *LB = Builder.CreateSelect(IsNeg, Stop, Start);
2075  Value *UB = Builder.CreateSelect(IsNeg, Start, Stop);
2076  Span = Builder.CreateSub(UB, LB, "", false, true);
2077  ZeroCmp = Builder.CreateICmp(
2078  InclusiveStop ? CmpInst::ICMP_SLT : CmpInst::ICMP_SLE, UB, LB);
2079  } else {
2080  Span = Builder.CreateSub(Stop, Start, "", true);
2081  ZeroCmp = Builder.CreateICmp(
2082  InclusiveStop ? CmpInst::ICMP_ULT : CmpInst::ICMP_ULE, Stop, Start);
2083  }
2084 
2085  Value *CountIfLooping;
2086  if (InclusiveStop) {
2087  CountIfLooping = Builder.CreateAdd(Builder.CreateUDiv(Span, Incr), One);
2088  } else {
2089  // Avoid incrementing past stop since it could overflow.
2090  Value *CountIfTwo = Builder.CreateAdd(
2091  Builder.CreateUDiv(Builder.CreateSub(Span, One), Incr), One);
2092  Value *OneCmp = Builder.CreateICmp(
2093  InclusiveStop ? CmpInst::ICMP_ULT : CmpInst::ICMP_ULE, Span, Incr);
2094  CountIfLooping = Builder.CreateSelect(OneCmp, One, CountIfTwo);
2095  }
2096  Value *TripCount = Builder.CreateSelect(ZeroCmp, Zero, CountIfLooping,
2097  "omp_" + Name + ".tripcount");
2098 
2099  auto BodyGen = [=](InsertPointTy CodeGenIP, Value *IV) {
2100  Builder.restoreIP(CodeGenIP);
2101  Value *Span = Builder.CreateMul(IV, Step);
2102  Value *IndVar = Builder.CreateAdd(Span, Start);
2103  BodyGenCB(Builder.saveIP(), IndVar);
2104  };
2105  LocationDescription LoopLoc = ComputeIP.isSet() ? Loc.IP : Builder.saveIP();
2106  return createCanonicalLoop(LoopLoc, BodyGen, TripCount, Name);
2107 }
2108 
2109 // Returns an LLVM function to call for initializing loop bounds using OpenMP
2110 // static scheduling depending on `type`. Only i32 and i64 are supported by the
2111 // runtime. Always interpret integers as unsigned similarly to
2112 // CanonicalLoopInfo.
2114  OpenMPIRBuilder &OMPBuilder) {
2115  unsigned Bitwidth = Ty->getIntegerBitWidth();
2116  if (Bitwidth == 32)
2117  return OMPBuilder.getOrCreateRuntimeFunction(
2118  M, omp::RuntimeFunction::OMPRTL___kmpc_for_static_init_4u);
2119  if (Bitwidth == 64)
2120  return OMPBuilder.getOrCreateRuntimeFunction(
2121  M, omp::RuntimeFunction::OMPRTL___kmpc_for_static_init_8u);
2122  llvm_unreachable("unknown OpenMP loop iterator bitwidth");
2123 }
2124 
2126 OpenMPIRBuilder::applyStaticWorkshareLoop(DebugLoc DL, CanonicalLoopInfo *CLI,
2127  InsertPointTy AllocaIP,
2128  bool NeedsBarrier) {
2129  assert(CLI->isValid() && "Requires a valid canonical loop");
2130  assert(!isConflictIP(AllocaIP, CLI->getPreheaderIP()) &&
2131  "Require dedicated allocate IP");
2132 
2133  // Set up the source location value for OpenMP runtime.
2134  Builder.restoreIP(CLI->getPreheaderIP());
2135  Builder.SetCurrentDebugLocation(DL);
2136 
2137  uint32_t SrcLocStrSize;
2138  Constant *SrcLocStr = getOrCreateSrcLocStr(DL, SrcLocStrSize);
2139  Value *SrcLoc = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
2140 
2141  // Declare useful OpenMP runtime functions.
2142  Value *IV = CLI->getIndVar();
2143  Type *IVTy = IV->getType();
2144  FunctionCallee StaticInit = getKmpcForStaticInitForType(IVTy, M, *this);
2145  FunctionCallee StaticFini =
2146  getOrCreateRuntimeFunction(M, omp::OMPRTL___kmpc_for_static_fini);
2147 
2148  // Allocate space for computed loop bounds as expected by the "init" function.
2149  Builder.restoreIP(AllocaIP);
2150  Type *I32Type = Type::getInt32Ty(M.getContext());
2151  Value *PLastIter = Builder.CreateAlloca(I32Type, nullptr, "p.lastiter");
2152  Value *PLowerBound = Builder.CreateAlloca(IVTy, nullptr, "p.lowerbound");
2153  Value *PUpperBound = Builder.CreateAlloca(IVTy, nullptr, "p.upperbound");
2154  Value *PStride = Builder.CreateAlloca(IVTy, nullptr, "p.stride");
2155 
2156  // At the end of the preheader, prepare for calling the "init" function by
2157  // storing the current loop bounds into the allocated space. A canonical loop
2158  // always iterates from 0 to trip-count with step 1. Note that "init" expects
2159  // and produces an inclusive upper bound.
2160  Builder.SetInsertPoint(CLI->getPreheader()->getTerminator());
2161  Constant *Zero = ConstantInt::get(IVTy, 0);
2162  Constant *One = ConstantInt::get(IVTy, 1);
2163  Builder.CreateStore(Zero, PLowerBound);
2164  Value *UpperBound = Builder.CreateSub(CLI->getTripCount(), One);
2165  Builder.CreateStore(UpperBound, PUpperBound);
2166  Builder.CreateStore(One, PStride);
2167 
2168  Value *ThreadNum = getOrCreateThreadID(SrcLoc);
2169 
2170  Constant *SchedulingType = ConstantInt::get(
2171  I32Type, static_cast<int>(OMPScheduleType::UnorderedStatic));
2172 
2173  // Call the "init" function and update the trip count of the loop with the
2174  // value it produced.
2175  Builder.CreateCall(StaticInit,
2176  {SrcLoc, ThreadNum, SchedulingType, PLastIter, PLowerBound,
2177  PUpperBound, PStride, One, Zero});
2178  Value *LowerBound = Builder.CreateLoad(IVTy, PLowerBound);
2179  Value *InclusiveUpperBound = Builder.CreateLoad(IVTy, PUpperBound);
2180  Value *TripCountMinusOne = Builder.CreateSub(InclusiveUpperBound, LowerBound);
2181  Value *TripCount = Builder.CreateAdd(TripCountMinusOne, One);
2182  CLI->setTripCount(TripCount);
2183 
2184  // Update all uses of the induction variable except the one in the condition
2185  // block that compares it with the actual upper bound, and the increment in
2186  // the latch block.
2187 
2188  CLI->mapIndVar([&](Instruction *OldIV) -> Value * {
2189  Builder.SetInsertPoint(CLI->getBody(),
2190  CLI->getBody()->getFirstInsertionPt());
2191  Builder.SetCurrentDebugLocation(DL);
2192  return Builder.CreateAdd(OldIV, LowerBound);
2193  });
2194 
2195  // In the "exit" block, call the "fini" function.
2196  Builder.SetInsertPoint(CLI->getExit(),
2197  CLI->getExit()->getTerminator()->getIterator());
2198  Builder.CreateCall(StaticFini, {SrcLoc, ThreadNum});
2199 
2200  // Add the barrier if requested.
2201  if (NeedsBarrier)
2202  createBarrier(LocationDescription(Builder.saveIP(), DL),
2203  omp::Directive::OMPD_for, /* ForceSimpleCall */ false,
2204  /* CheckCancelFlag */ false);
2205 
2206  InsertPointTy AfterIP = CLI->getAfterIP();
2207  CLI->invalidate();
2208 
2209  return AfterIP;
2210 }
2211 
2212 OpenMPIRBuilder::InsertPointTy OpenMPIRBuilder::applyStaticChunkedWorkshareLoop(
2213  DebugLoc DL, CanonicalLoopInfo *CLI, InsertPointTy AllocaIP,
2214  bool NeedsBarrier, Value *ChunkSize) {
2215  assert(CLI->isValid() && "Requires a valid canonical loop");
2216  assert(ChunkSize && "Chunk size is required");
2217 
2218  LLVMContext &Ctx = CLI->getFunction()->getContext();
2219  Value *IV = CLI->getIndVar();
2220  Value *OrigTripCount = CLI->getTripCount();
2221  Type *IVTy = IV->getType();
2222  assert(IVTy->getIntegerBitWidth() <= 64 &&
2223  "Max supported tripcount bitwidth is 64 bits");
2224  Type *InternalIVTy = IVTy->getIntegerBitWidth() <= 32 ? Type::getInt32Ty(Ctx)
2225  : Type::getInt64Ty(Ctx);
2226  Type *I32Type = Type::getInt32Ty(M.getContext());
2227  Constant *Zero = ConstantInt::get(InternalIVTy, 0);
2228  Constant *One = ConstantInt::get(InternalIVTy, 1);
2229 
2230  // Declare useful OpenMP runtime functions.
2231  FunctionCallee StaticInit =
2232  getKmpcForStaticInitForType(InternalIVTy, M, *this);
2233  FunctionCallee StaticFini =
2234  getOrCreateRuntimeFunction(M, omp::OMPRTL___kmpc_for_static_fini);
2235 
2236  // Allocate space for computed loop bounds as expected by the "init" function.
2237  Builder.restoreIP(AllocaIP);
2238  Builder.SetCurrentDebugLocation(DL);
2239  Value *PLastIter = Builder.CreateAlloca(I32Type, nullptr, "p.lastiter");
2240  Value *PLowerBound =
2241  Builder.CreateAlloca(InternalIVTy, nullptr, "p.lowerbound");
2242  Value *PUpperBound =
2243  Builder.CreateAlloca(InternalIVTy, nullptr, "p.upperbound");
2244  Value *PStride = Builder.CreateAlloca(InternalIVTy, nullptr, "p.stride");
2245 
2246  // Set up the source location value for the OpenMP runtime.
2247  Builder.restoreIP(CLI->getPreheaderIP());
2248  Builder.SetCurrentDebugLocation(DL);
2249 
2250  // TODO: Detect overflow in ubsan or max-out with current tripcount.
2251  Value *CastedChunkSize =
2252  Builder.CreateZExtOrTrunc(ChunkSize, InternalIVTy, "chunksize");
2253  Value *CastedTripCount =
2254  Builder.CreateZExt(OrigTripCount, InternalIVTy, "tripcount");
2255 
2256  Constant *SchedulingType = ConstantInt::get(
2257  I32Type, static_cast<int>(OMPScheduleType::UnorderedStaticChunked));
2258  Builder.CreateStore(Zero, PLowerBound);
2259  Value *OrigUpperBound = Builder.CreateSub(CastedTripCount, One);
2260  Builder.CreateStore(OrigUpperBound, PUpperBound);
2261  Builder.CreateStore(One, PStride);
2262 
2263  // Call the "init" function and update the trip count of the loop with the
2264  // value it produced.
2265  uint32_t SrcLocStrSize;
2266  Constant *SrcLocStr = getOrCreateSrcLocStr(DL, SrcLocStrSize);
2267  Value *SrcLoc = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
2268  Value *ThreadNum = getOrCreateThreadID(SrcLoc);
2269  Builder.CreateCall(StaticInit,
2270  {/*loc=*/SrcLoc, /*global_tid=*/ThreadNum,
2271  /*schedtype=*/SchedulingType, /*plastiter=*/PLastIter,
2272  /*plower=*/PLowerBound, /*pupper=*/PUpperBound,
2273  /*pstride=*/PStride, /*incr=*/One,
2274  /*chunk=*/CastedChunkSize});
2275 
2276  // Load values written by the "init" function.
2277  Value *FirstChunkStart =
2278  Builder.CreateLoad(InternalIVTy, PLowerBound, "omp_firstchunk.lb");
2279  Value *FirstChunkStop =
2280  Builder.CreateLoad(InternalIVTy, PUpperBound, "omp_firstchunk.ub");
2281  Value *FirstChunkEnd = Builder.CreateAdd(FirstChunkStop, One);
2282  Value *ChunkRange =
2283  Builder.CreateSub(FirstChunkEnd, FirstChunkStart, "omp_chunk.range");
2284  Value *NextChunkStride =
2285  Builder.CreateLoad(InternalIVTy, PStride, "omp_dispatch.stride");
2286 
2287  // Create outer "dispatch" loop for enumerating the chunks.
2288  BasicBlock *DispatchEnter = splitBB(Builder, true);
2289  Value *DispatchCounter;
2290  CanonicalLoopInfo *DispatchCLI = createCanonicalLoop(
2291  {Builder.saveIP(), DL},
2292  [&](InsertPointTy BodyIP, Value *Counter) { DispatchCounter = Counter; },
2293  FirstChunkStart, CastedTripCount, NextChunkStride,
2294  /*IsSigned=*/false, /*InclusiveStop=*/false, /*ComputeIP=*/{},
2295  "dispatch");
2296 
2297  // Remember the BasicBlocks of the dispatch loop we need, then invalidate to
2298  // not have to preserve the canonical invariant.
2299  BasicBlock *DispatchBody = DispatchCLI->getBody();
2300  BasicBlock *DispatchLatch = DispatchCLI->getLatch();
2301  BasicBlock *DispatchExit = DispatchCLI->getExit();
2302  BasicBlock *DispatchAfter = DispatchCLI->getAfter();
2303  DispatchCLI->invalidate();
2304 
2305  // Rewire the original loop to become the chunk loop inside the dispatch loop.
2306  redirectTo(DispatchAfter, CLI->getAfter(), DL);
2307  redirectTo(CLI->getExit(), DispatchLatch, DL);
2308  redirectTo(DispatchBody, DispatchEnter, DL);
2309 
2310  // Prepare the prolog of the chunk loop.
2311  Builder.restoreIP(CLI->getPreheaderIP());
2312  Builder.SetCurrentDebugLocation(DL);
2313 
2314  // Compute the number of iterations of the chunk loop.
2315  Builder.SetInsertPoint(CLI->getPreheader()->getTerminator());
2316  Value *ChunkEnd = Builder.CreateAdd(DispatchCounter, ChunkRange);
2317  Value *IsLastChunk =
2318  Builder.CreateICmpUGE(ChunkEnd, CastedTripCount, "omp_chunk.is_last");
2319  Value *CountUntilOrigTripCount =
2320  Builder.CreateSub(CastedTripCount, DispatchCounter);
2321  Value *ChunkTripCount = Builder.CreateSelect(
2322  IsLastChunk, CountUntilOrigTripCount, ChunkRange, "omp_chunk.tripcount");
2323  Value *BackcastedChunkTC =
2324  Builder.CreateTrunc(ChunkTripCount, IVTy, "omp_chunk.tripcount.trunc");
2325  CLI->setTripCount(BackcastedChunkTC);
2326 
2327  // Update all uses of the induction variable except the one in the condition
2328  // block that compares it with the actual upper bound, and the increment in
2329  // the latch block.
2330  Value *BackcastedDispatchCounter =
2331  Builder.CreateTrunc(DispatchCounter, IVTy, "omp_dispatch.iv.trunc");
2332  CLI->mapIndVar([&](Instruction *) -> Value * {
2333  Builder.restoreIP(CLI->getBodyIP());
2334  return Builder.CreateAdd(IV, BackcastedDispatchCounter);
2335  });
2336 
2337  // In the "exit" block, call the "fini" function.
2338  Builder.SetInsertPoint(DispatchExit, DispatchExit->getFirstInsertionPt());
2339  Builder.CreateCall(StaticFini, {SrcLoc, ThreadNum});
2340 
2341  // Add the barrier if requested.
2342  if (NeedsBarrier)
2343  createBarrier(LocationDescription(Builder.saveIP(), DL), OMPD_for,
2344  /*ForceSimpleCall=*/false, /*CheckCancelFlag=*/false);
2345 
2346 #ifndef NDEBUG
2347  // Even though we currently do not support applying additional methods to it,
2348  // the chunk loop should remain a canonical loop.
2349  CLI->assertOK();
2350 #endif
2351 
2352  return {DispatchAfter, DispatchAfter->getFirstInsertionPt()};
2353 }
2354 
2356  DebugLoc DL, CanonicalLoopInfo *CLI, InsertPointTy AllocaIP,
2357  bool NeedsBarrier, llvm::omp::ScheduleKind SchedKind,
2358  llvm::Value *ChunkSize, bool HasSimdModifier, bool HasMonotonicModifier,
2359  bool HasNonmonotonicModifier, bool HasOrderedClause) {
2360  OMPScheduleType EffectiveScheduleType = computeOpenMPScheduleType(
2361  SchedKind, ChunkSize, HasSimdModifier, HasMonotonicModifier,
2362  HasNonmonotonicModifier, HasOrderedClause);
2363 
2364  bool IsOrdered = (EffectiveScheduleType & OMPScheduleType::ModifierOrdered) ==
2366  switch (EffectiveScheduleType & ~OMPScheduleType::ModifierMask) {
2368  assert(!ChunkSize && "No chunk size with static-chunked schedule");
2369  if (IsOrdered)
2370  return applyDynamicWorkshareLoop(DL, CLI, AllocaIP, EffectiveScheduleType,
2371  NeedsBarrier, ChunkSize);
2372  // FIXME: Monotonicity ignored?
2373  return applyStaticWorkshareLoop(DL, CLI, AllocaIP, NeedsBarrier);
2374 
2376  if (IsOrdered)
2377  return applyDynamicWorkshareLoop(DL, CLI, AllocaIP, EffectiveScheduleType,
2378  NeedsBarrier, ChunkSize);
2379  // FIXME: Monotonicity ignored?
2380  return applyStaticChunkedWorkshareLoop(DL, CLI, AllocaIP, NeedsBarrier,
2381  ChunkSize);
2382 
2390  assert(!ChunkSize &&
2391  "schedule type does not support user-defined chunk sizes");
2392  [[fallthrough]];
2398  return applyDynamicWorkshareLoop(DL, CLI, AllocaIP, EffectiveScheduleType,
2399  NeedsBarrier, ChunkSize);
2400 
2401  default:
2402  llvm_unreachable("Unknown/unimplemented schedule kind");
2403  }
2404 }
2405 
2406 /// Returns an LLVM function to call for initializing loop bounds using OpenMP
2407 /// dynamic scheduling depending on `type`. Only i32 and i64 are supported by
2408 /// the runtime. Always interpret integers as unsigned similarly to
2409 /// CanonicalLoopInfo.
2410 static FunctionCallee
2412  unsigned Bitwidth = Ty->getIntegerBitWidth();
2413  if (Bitwidth == 32)
2414  return OMPBuilder.getOrCreateRuntimeFunction(
2415  M, omp::RuntimeFunction::OMPRTL___kmpc_dispatch_init_4u);
2416  if (Bitwidth == 64)
2417  return OMPBuilder.getOrCreateRuntimeFunction(
2418  M, omp::RuntimeFunction::OMPRTL___kmpc_dispatch_init_8u);
2419  llvm_unreachable("unknown OpenMP loop iterator bitwidth");
2420 }
2421 
2422 /// Returns an LLVM function to call for updating the next loop using OpenMP
2423 /// dynamic scheduling depending on `type`. Only i32 and i64 are supported by
2424 /// the runtime. Always interpret integers as unsigned similarly to
2425 /// CanonicalLoopInfo.
2426 static FunctionCallee
2428  unsigned Bitwidth = Ty->getIntegerBitWidth();
2429  if (Bitwidth == 32)
2430  return OMPBuilder.getOrCreateRuntimeFunction(
2431  M, omp::RuntimeFunction::OMPRTL___kmpc_dispatch_next_4u);
2432  if (Bitwidth == 64)
2433  return OMPBuilder.getOrCreateRuntimeFunction(
2434  M, omp::RuntimeFunction::OMPRTL___kmpc_dispatch_next_8u);
2435  llvm_unreachable("unknown OpenMP loop iterator bitwidth");
2436 }
2437 
2438 /// Returns an LLVM function to call for finalizing the dynamic loop using
2439 /// depending on `type`. Only i32 and i64 are supported by the runtime. Always
2440 /// interpret integers as unsigned similarly to CanonicalLoopInfo.
2441 static FunctionCallee
2443  unsigned Bitwidth = Ty->getIntegerBitWidth();
2444  if (Bitwidth == 32)
2445  return OMPBuilder.getOrCreateRuntimeFunction(
2446  M, omp::RuntimeFunction::OMPRTL___kmpc_dispatch_fini_4u);
2447  if (Bitwidth == 64)
2448  return OMPBuilder.getOrCreateRuntimeFunction(
2449  M, omp::RuntimeFunction::OMPRTL___kmpc_dispatch_fini_8u);
2450  llvm_unreachable("unknown OpenMP loop iterator bitwidth");
2451 }
2452 
2453 OpenMPIRBuilder::InsertPointTy OpenMPIRBuilder::applyDynamicWorkshareLoop(
2454  DebugLoc DL, CanonicalLoopInfo *CLI, InsertPointTy AllocaIP,
2455  OMPScheduleType SchedType, bool NeedsBarrier, Value *Chunk) {
2456  assert(CLI->isValid() && "Requires a valid canonical loop");
2457  assert(!isConflictIP(AllocaIP, CLI->getPreheaderIP()) &&
2458  "Require dedicated allocate IP");
2460  "Require valid schedule type");
2461 
2462  bool Ordered = (SchedType & OMPScheduleType::ModifierOrdered) ==
2464 
2465  // Set up the source location value for OpenMP runtime.
2466  Builder.SetCurrentDebugLocation(DL);
2467 
2468  uint32_t SrcLocStrSize;
2469  Constant *SrcLocStr = getOrCreateSrcLocStr(DL, SrcLocStrSize);
2470  Value *SrcLoc = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
2471 
2472  // Declare useful OpenMP runtime functions.
2473  Value *IV = CLI->getIndVar();
2474  Type *IVTy = IV->getType();
2475  FunctionCallee DynamicInit = getKmpcForDynamicInitForType(IVTy, M, *this);
2476  FunctionCallee DynamicNext = getKmpcForDynamicNextForType(IVTy, M, *this);
2477 
2478  // Allocate space for computed loop bounds as expected by the "init" function.
2479  Builder.restoreIP(AllocaIP);
2480  Type *I32Type = Type::getInt32Ty(M.getContext());
2481  Value *PLastIter = Builder.CreateAlloca(I32Type, nullptr, "p.lastiter");
2482  Value *PLowerBound = Builder.CreateAlloca(IVTy, nullptr, "p.lowerbound");
2483  Value *PUpperBound = Builder.CreateAlloca(IVTy, nullptr, "p.upperbound");
2484  Value *PStride = Builder.CreateAlloca(IVTy, nullptr, "p.stride");
2485 
2486  // At the end of the preheader, prepare for calling the "init" function by
2487  // storing the current loop bounds into the allocated space. A canonical loop
2488  // always iterates from 0 to trip-count with step 1. Note that "init" expects
2489  // and produces an inclusive upper bound.
2490  BasicBlock *PreHeader = CLI->getPreheader();
2491  Builder.SetInsertPoint(PreHeader->getTerminator());
2492  Constant *One = ConstantInt::get(IVTy, 1);
2493  Builder.CreateStore(One, PLowerBound);
2494  Value *UpperBound = CLI->getTripCount();
2495  Builder.CreateStore(UpperBound, PUpperBound);
2496  Builder.CreateStore(One, PStride);
2497 
2498  BasicBlock *Header = CLI->getHeader();
2499  BasicBlock *Exit = CLI->getExit();
2500  BasicBlock *Cond = CLI->getCond();
2501  BasicBlock *Latch = CLI->getLatch();
2502  InsertPointTy AfterIP = CLI->getAfterIP();
2503 
2504  // The CLI will be "broken" in the code below, as the loop is no longer
2505  // a valid canonical loop.
2506 
2507  if (!Chunk)
2508  Chunk = One;
2509 
2510  Value *ThreadNum = getOrCreateThreadID(SrcLoc);
2511 
2512  Constant *SchedulingType =
2513  ConstantInt::get(I32Type, static_cast<int>(SchedType));
2514 
2515  // Call the "init" function.
2516  Builder.CreateCall(DynamicInit,
2517  {SrcLoc, ThreadNum, SchedulingType, /* LowerBound */ One,
2518  UpperBound, /* step */ One, Chunk});
2519 
2520  // An outer loop around the existing one.
2521  BasicBlock *OuterCond = BasicBlock::Create(
2522  PreHeader->getContext(), Twine(PreHeader->getName()) + ".outer.cond",
2523  PreHeader->getParent());
2524  // This needs to be 32-bit always, so can't use the IVTy Zero above.
2525  Builder.SetInsertPoint(OuterCond, OuterCond->getFirstInsertionPt());
2526  Value *Res =
2527  Builder.CreateCall(DynamicNext, {SrcLoc, ThreadNum, PLastIter,
2528  PLowerBound, PUpperBound, PStride});
2529  Constant *Zero32 = ConstantInt::get(I32Type, 0);
2530  Value *MoreWork = Builder.CreateCmp(CmpInst::ICMP_NE, Res, Zero32);
2531  Value *LowerBound =
2532  Builder.CreateSub(Builder.CreateLoad(IVTy, PLowerBound), One, "lb");
2533  Builder.CreateCondBr(MoreWork, Header, Exit);
2534 
2535  // Change PHI-node in loop header to use outer cond rather than preheader,
2536  // and set IV to the LowerBound.
2537  Instruction *Phi = &Header->front();
2538  auto *PI = cast<PHINode>(Phi);
2539  PI->setIncomingBlock(0, OuterCond);
2540  PI->setIncomingValue(0, LowerBound);
2541 
2542  // Then set the pre-header to jump to the OuterCond
2543  Instruction *Term = PreHeader->getTerminator();
2544  auto *Br = cast<BranchInst>(Term);
2545  Br->setSuccessor(0, OuterCond);
2546 
2547  // Modify the inner condition:
2548  // * Use the UpperBound returned from the DynamicNext call.
2549  // * jump to the loop outer loop when done with one of the inner loops.
2550  Builder.SetInsertPoint(Cond, Cond->getFirstInsertionPt());
2551  UpperBound = Builder.CreateLoad(IVTy, PUpperBound, "ub");
2552  Instruction *Comp = &*Builder.GetInsertPoint();
2553  auto *CI = cast<CmpInst>(Comp);
2554  CI->setOperand(1, UpperBound);
2555  // Redirect the inner exit to branch to outer condition.
2556  Instruction *Branch = &Cond->back();
2557  auto *BI = cast<BranchInst>(Branch);
2558  assert(BI->getSuccessor(1) == Exit);
2559  BI->setSuccessor(1, OuterCond);
2560 
2561  // Call the "fini" function if "ordered" is present in wsloop directive.
2562  if (Ordered) {
2563  Builder.SetInsertPoint(&Latch->back());
2564  FunctionCallee DynamicFini = getKmpcForDynamicFiniForType(IVTy, M, *this);
2565  Builder.CreateCall(DynamicFini, {SrcLoc, ThreadNum});
2566  }
2567 
2568  // Add the barrier if requested.
2569  if (NeedsBarrier) {
2570  Builder.SetInsertPoint(&Exit->back());
2571  createBarrier(LocationDescription(Builder.saveIP(), DL),
2572  omp::Directive::OMPD_for, /* ForceSimpleCall */ false,
2573  /* CheckCancelFlag */ false);
2574  }
2575 
2576  CLI->invalidate();
2577  return AfterIP;
2578 }
2579 
2580 /// Redirect all edges that branch to \p OldTarget to \p NewTarget. That is,
2581 /// after this \p OldTarget will be orphaned.
2582 static void redirectAllPredecessorsTo(BasicBlock *OldTarget,
2583  BasicBlock *NewTarget, DebugLoc DL) {
2584  for (BasicBlock *Pred : make_early_inc_range(predecessors(OldTarget)))
2585  redirectTo(Pred, NewTarget, DL);
2586 }
2587 
2588 /// Determine which blocks in \p BBs are reachable from outside and remove the
2589 /// ones that are not reachable from the function.
2591  SmallPtrSet<BasicBlock *, 6> BBsToErase{BBs.begin(), BBs.end()};
2592  auto HasRemainingUses = [&BBsToErase](BasicBlock *BB) {
2593  for (Use &U : BB->uses()) {
2594  auto *UseInst = dyn_cast<Instruction>(U.getUser());
2595  if (!UseInst)
2596  continue;
2597  if (BBsToErase.count(UseInst->getParent()))
2598  continue;
2599  return true;
2600  }
2601  return false;
2602  };
2603 
2604  while (true) {
2605  bool Changed = false;
2606  for (BasicBlock *BB : make_early_inc_range(BBsToErase)) {
2607  if (HasRemainingUses(BB)) {
2608  BBsToErase.erase(BB);
2609  Changed = true;
2610  }
2611  }
2612  if (!Changed)
2613  break;
2614  }
2615 
2616  SmallVector<BasicBlock *, 7> BBVec(BBsToErase.begin(), BBsToErase.end());
2617  DeleteDeadBlocks(BBVec);
2618 }
2619 
2622  InsertPointTy ComputeIP) {
2623  assert(Loops.size() >= 1 && "At least one loop required");
2624  size_t NumLoops = Loops.size();
2625 
2626  // Nothing to do if there is already just one loop.
2627  if (NumLoops == 1)
2628  return Loops.front();
2629 
2630  CanonicalLoopInfo *Outermost = Loops.front();
2631  CanonicalLoopInfo *Innermost = Loops.back();
2632  BasicBlock *OrigPreheader = Outermost->getPreheader();
2633  BasicBlock *OrigAfter = Outermost->getAfter();
2634  Function *F = OrigPreheader->getParent();
2635 
2636  // Loop control blocks that may become orphaned later.
2637  SmallVector<BasicBlock *, 12> OldControlBBs;
2638  OldControlBBs.reserve(6 * Loops.size());
2639  for (CanonicalLoopInfo *Loop : Loops)
2640  Loop->collectControlBlocks(OldControlBBs);
2641 
2642  // Setup the IRBuilder for inserting the trip count computation.
2643  Builder.SetCurrentDebugLocation(DL);
2644  if (ComputeIP.isSet())
2645  Builder.restoreIP(ComputeIP);
2646  else
2647  Builder.restoreIP(Outermost->getPreheaderIP());
2648 
2649  // Derive the collapsed' loop trip count.
2650  // TODO: Find common/largest indvar type.
2651  Value *CollapsedTripCount = nullptr;
2652  for (CanonicalLoopInfo *L : Loops) {
2653  assert(L->isValid() &&
2654  "All loops to collapse must be valid canonical loops");
2655  Value *OrigTripCount = L->getTripCount();
2656  if (!CollapsedTripCount) {
2657  CollapsedTripCount = OrigTripCount;
2658  continue;
2659  }
2660 
2661  // TODO: Enable UndefinedSanitizer to diagnose an overflow here.
2662  CollapsedTripCount = Builder.CreateMul(CollapsedTripCount, OrigTripCount,
2663  {}, /*HasNUW=*/true);
2664  }
2665 
2666  // Create the collapsed loop control flow.
2667  CanonicalLoopInfo *Result =
2668  createLoopSkeleton(DL, CollapsedTripCount, F,
2669  OrigPreheader->getNextNode(), OrigAfter, "collapsed");
2670 
2671  // Build the collapsed loop body code.
2672  // Start with deriving the input loop induction variables from the collapsed
2673  // one, using a divmod scheme. To preserve the original loops' order, the
2674  // innermost loop use the least significant bits.
2675  Builder.restoreIP(Result->getBodyIP());
2676 
2677  Value *Leftover = Result->getIndVar();
2678  SmallVector<Value *> NewIndVars;
2679  NewIndVars.resize(NumLoops);
2680  for (int i = NumLoops - 1; i >= 1; --i) {
2681  Value *OrigTripCount = Loops[i]->getTripCount();
2682 
2683  Value *NewIndVar = Builder.CreateURem(Leftover, OrigTripCount);
2684  NewIndVars[i] = NewIndVar;
2685 
2686  Leftover = Builder.CreateUDiv(Leftover, OrigTripCount);
2687  }
2688  // Outermost loop gets all the remaining bits.
2689  NewIndVars[0] = Leftover;
2690 
2691  // Construct the loop body control flow.
2692  // We progressively construct the branch structure following in direction of
2693  // the control flow, from the leading in-between code, the loop nest body, the
2694  // trailing in-between code, and rejoining the collapsed loop's latch.
2695  // ContinueBlock and ContinuePred keep track of the source(s) of next edge. If
2696  // the ContinueBlock is set, continue with that block. If ContinuePred, use
2697  // its predecessors as sources.
2698  BasicBlock *ContinueBlock = Result->getBody();
2699  BasicBlock *ContinuePred = nullptr;
2700  auto ContinueWith = [&ContinueBlock, &ContinuePred, DL](BasicBlock *Dest,
2701  BasicBlock *NextSrc) {
2702  if (ContinueBlock)
2703  redirectTo(ContinueBlock, Dest, DL);
2704  else
2705  redirectAllPredecessorsTo(ContinuePred, Dest, DL);
2706 
2707  ContinueBlock = nullptr;
2708  ContinuePred = NextSrc;
2709  };
2710 
2711  // The code before the nested loop of each level.
2712  // Because we are sinking it into the nest, it will be executed more often
2713  // that the original loop. More sophisticated schemes could keep track of what
2714  // the in-between code is and instantiate it only once per thread.
2715  for (size_t i = 0; i < NumLoops - 1; ++i)
2716  ContinueWith(Loops[i]->getBody(), Loops[i + 1]->getHeader());
2717 
2718  // Connect the loop nest body.
2719  ContinueWith(Innermost->getBody(), Innermost->getLatch());
2720 
2721  // The code after the nested loop at each level.
2722  for (size_t i = NumLoops - 1; i > 0; --i)
2723  ContinueWith(Loops[i]->getAfter(), Loops[i - 1]->getLatch());
2724 
2725  // Connect the finished loop to the collapsed loop latch.
2726  ContinueWith(Result->getLatch(), nullptr);
2727 
2728  // Replace the input loops with the new collapsed loop.
2729  redirectTo(Outermost->getPreheader(), Result->getPreheader(), DL);
2730  redirectTo(Result->getAfter(), Outermost->getAfter(), DL);
2731 
2732  // Replace the input loop indvars with the derived ones.
2733  for (size_t i = 0; i < NumLoops; ++i)
2734  Loops[i]->getIndVar()->replaceAllUsesWith(NewIndVars[i]);
2735 
2736  // Remove unused parts of the input loops.
2737  removeUnusedBlocksFromParent(OldControlBBs);
2738 
2739  for (CanonicalLoopInfo *L : Loops)
2740  L->invalidate();
2741 
2742 #ifndef NDEBUG
2743  Result->assertOK();
2744 #endif
2745  return Result;
2746 }
2747 
2748 std::vector<CanonicalLoopInfo *>
2750  ArrayRef<Value *> TileSizes) {
2751  assert(TileSizes.size() == Loops.size() &&
2752  "Must pass as many tile sizes as there are loops");
2753  int NumLoops = Loops.size();
2754  assert(NumLoops >= 1 && "At least one loop to tile required");
2755 
2756  CanonicalLoopInfo *OutermostLoop = Loops.front();
2757  CanonicalLoopInfo *InnermostLoop = Loops.back();
2758  Function *F = OutermostLoop->getBody()->getParent();
2759  BasicBlock *InnerEnter = InnermostLoop->getBody();
2760  BasicBlock *InnerLatch = InnermostLoop->getLatch();
2761 
2762  // Loop control blocks that may become orphaned later.
2763  SmallVector<BasicBlock *, 12> OldControlBBs;
2764  OldControlBBs.reserve(6 * Loops.size());
2765  for (CanonicalLoopInfo *Loop : Loops)
2766  Loop->collectControlBlocks(OldControlBBs);
2767 
2768  // Collect original trip counts and induction variable to be accessible by
2769  // index. Also, the structure of the original loops is not preserved during
2770  // the construction of the tiled loops, so do it before we scavenge the BBs of
2771  // any original CanonicalLoopInfo.
2772  SmallVector<Value *, 4> OrigTripCounts, OrigIndVars;
2773  for (CanonicalLoopInfo *L : Loops) {
2774  assert(L->isValid() && "All input loops must be valid canonical loops");
2775  OrigTripCounts.push_back(L->getTripCount());
2776  OrigIndVars.push_back(L->getIndVar());
2777  }
2778 
2779  // Collect the code between loop headers. These may contain SSA definitions
2780  // that are used in the loop nest body. To be usable with in the innermost
2781  // body, these BasicBlocks will be sunk into the loop nest body. That is,
2782  // these instructions may be executed more often than before the tiling.
2783  // TODO: It would be sufficient to only sink them into body of the
2784  // corresponding tile loop.
2786  for (int i = 0; i < NumLoops - 1; ++i) {
2787  CanonicalLoopInfo *Surrounding = Loops[i];
2788  CanonicalLoopInfo *Nested = Loops[i + 1];
2789 
2790  BasicBlock *EnterBB = Surrounding->getBody();
2791  BasicBlock *ExitBB = Nested->getHeader();
2792  InbetweenCode.emplace_back(EnterBB, ExitBB);
2793  }
2794 
2795  // Compute the trip counts of the floor loops.
2796  Builder.SetCurrentDebugLocation(DL);
2797  Builder.restoreIP(OutermostLoop->getPreheaderIP());
2798  SmallVector<Value *, 4> FloorCount, FloorRems;
2799  for (int i = 0; i < NumLoops; ++i) {
2800  Value *TileSize = TileSizes[i];
2801  Value *OrigTripCount = OrigTripCounts[i];
2802  Type *IVType = OrigTripCount->getType();
2803 
2804  Value *FloorTripCount = Builder.CreateUDiv(OrigTripCount, TileSize);
2805  Value *FloorTripRem = Builder.CreateURem(OrigTripCount, TileSize);
2806 
2807  // 0 if tripcount divides the tilesize, 1 otherwise.
2808  // 1 means we need an additional iteration for a partial tile.
2809  //
2810  // Unfortunately we cannot just use the roundup-formula
2811  // (tripcount + tilesize - 1)/tilesize
2812  // because the summation might overflow. We do not want introduce undefined
2813  // behavior when the untiled loop nest did not.
2814  Value *FloorTripOverflow =
2815  Builder.CreateICmpNE(FloorTripRem, ConstantInt::get(IVType, 0));
2816 
2817  FloorTripOverflow = Builder.CreateZExt(FloorTripOverflow, IVType);
2818  FloorTripCount =
2819  Builder.CreateAdd(FloorTripCount, FloorTripOverflow,
2820  "omp_floor" + Twine(i) + ".tripcount", true);
2821 
2822  // Remember some values for later use.
2823  FloorCount.push_back(FloorTripCount);
2824  FloorRems.push_back(FloorTripRem);
2825  }
2826 
2827  // Generate the new loop nest, from the outermost to the innermost.
2828  std::vector<CanonicalLoopInfo *> Result;
2829  Result.reserve(NumLoops * 2);
2830 
2831  // The basic block of the surrounding loop that enters the nest generated
2832  // loop.
2833  BasicBlock *Enter = OutermostLoop->getPreheader();
2834 
2835  // The basic block of the surrounding loop where the inner code should
2836  // continue.
2837  BasicBlock *Continue = OutermostLoop->getAfter();
2838 
2839  // Where the next loop basic block should be inserted.
2840  BasicBlock *OutroInsertBefore = InnermostLoop->getExit();
2841 
2842  auto EmbeddNewLoop =
2843  [this, DL, F, InnerEnter, &Enter, &Continue, &OutroInsertBefore](
2844  Value *TripCount, const Twine &Name) -> CanonicalLoopInfo * {
2845  CanonicalLoopInfo *EmbeddedLoop = createLoopSkeleton(
2846  DL, TripCount, F, InnerEnter, OutroInsertBefore, Name);
2847  redirectTo(Enter, EmbeddedLoop->getPreheader(), DL);
2848  redirectTo(EmbeddedLoop->getAfter(), Continue, DL);
2849 
2850  // Setup the position where the next embedded loop connects to this loop.
2851  Enter = EmbeddedLoop->getBody();
2852  Continue = EmbeddedLoop->getLatch();
2853  OutroInsertBefore = EmbeddedLoop->getLatch();
2854  return EmbeddedLoop;
2855  };
2856 
2857  auto EmbeddNewLoops = [&Result, &EmbeddNewLoop](ArrayRef<Value *> TripCounts,
2858  const Twine &NameBase) {
2859  for (auto P : enumerate(TripCounts)) {
2860  CanonicalLoopInfo *EmbeddedLoop =
2861  EmbeddNewLoop(P.value(), NameBase + Twine(P.index()));
2862  Result.push_back(EmbeddedLoop);
2863  }
2864  };
2865 
2866  EmbeddNewLoops(FloorCount, "floor");
2867 
2868  // Within the innermost floor loop, emit the code that computes the tile
2869  // sizes.
2870  Builder.SetInsertPoint(Enter->getTerminator());
2871  SmallVector<Value *, 4> TileCounts;
2872  for (int i = 0; i < NumLoops; ++i) {
2873  CanonicalLoopInfo *FloorLoop = Result[i];
2874  Value *TileSize = TileSizes[i];
2875 
2876  Value *FloorIsEpilogue =
2877  Builder.CreateICmpEQ(FloorLoop->getIndVar(), FloorCount[i]);
2878  Value *TileTripCount =
2879  Builder.CreateSelect(FloorIsEpilogue, FloorRems[i], TileSize);
2880 
2881  TileCounts.push_back(TileTripCount);
2882  }
2883 
2884  // Create the tile loops.
2885  EmbeddNewLoops(TileCounts, "tile");
2886 
2887  // Insert the inbetween code into the body.
2888  BasicBlock *BodyEnter = Enter;
2889  BasicBlock *BodyEntered = nullptr;
2890  for (std::pair<BasicBlock *, BasicBlock *> P : InbetweenCode) {
2891  BasicBlock *EnterBB = P.first;
2892  BasicBlock *ExitBB = P.second;
2893 
2894  if (BodyEnter)
2895  redirectTo(BodyEnter, EnterBB, DL);
2896  else
2897  redirectAllPredecessorsTo(BodyEntered, EnterBB, DL);
2898 
2899  BodyEnter = nullptr;
2900  BodyEntered = ExitBB;
2901  }
2902 
2903  // Append the original loop nest body into the generated loop nest body.
2904  if (BodyEnter)
2905  redirectTo(BodyEnter, InnerEnter, DL);
2906  else
2907  redirectAllPredecessorsTo(BodyEntered, InnerEnter, DL);
2908  redirectAllPredecessorsTo(InnerLatch, Continue, DL);
2909 
2910  // Replace the original induction variable with an induction variable computed
2911  // from the tile and floor induction variables.
2912  Builder.restoreIP(Result.back()->getBodyIP());
2913  for (int i = 0; i < NumLoops; ++i) {
2914  CanonicalLoopInfo *FloorLoop = Result[i];
2915  CanonicalLoopInfo *TileLoop = Result[NumLoops + i];
2916  Value *OrigIndVar = OrigIndVars[i];
2917  Value *Size = TileSizes[i];
2918 
2919  Value *Scale =
2920  Builder.CreateMul(Size, FloorLoop->getIndVar(), {}, /*HasNUW=*/true);
2921  Value *Shift =
2922  Builder.CreateAdd(Scale, TileLoop->getIndVar(), {}, /*HasNUW=*/true);
2923  OrigIndVar->replaceAllUsesWith(Shift);
2924  }
2925 
2926  // Remove unused parts of the original loops.
2927  removeUnusedBlocksFromParent(OldControlBBs);
2928 
2929  for (CanonicalLoopInfo *L : Loops)
2930  L->invalidate();
2931 
2932 #ifndef NDEBUG
2933  for (CanonicalLoopInfo *GenL : Result)
2934  GenL->assertOK();
2935 #endif
2936  return Result;
2937 }
2938 
2939 /// Attach metadata \p Properties to the basic block described by \p BB. If the
2940 /// basic block already has metadata, the basic block properties are appended.
2942  ArrayRef<Metadata *> Properties) {
2943  // Nothing to do if no property to attach.
2944  if (Properties.empty())
2945  return;
2946 
2947  LLVMContext &Ctx = BB->getContext();
2948  SmallVector<Metadata *> NewProperties;
2949  NewProperties.push_back(nullptr);
2950 
2951  // If the basic block already has metadata, prepend it to the new metadata.
2952  MDNode *Existing = BB->getTerminator()->getMetadata(LLVMContext::MD_loop);
2953  if (Existing)
2954  append_range(NewProperties, drop_begin(Existing->operands(), 1));
2955 
2956  append_range(NewProperties, Properties);
2957  MDNode *BasicBlockID = MDNode::getDistinct(Ctx, NewProperties);
2958  BasicBlockID->replaceOperandWith(0, BasicBlockID);
2959 
2960  BB->getTerminator()->setMetadata(LLVMContext::MD_loop, BasicBlockID);
2961 }
2962 
2963 /// Attach loop metadata \p Properties to the loop described by \p Loop. If the
2964 /// loop already has metadata, the loop properties are appended.
2966  ArrayRef<Metadata *> Properties) {
2967  assert(Loop->isValid() && "Expecting a valid CanonicalLoopInfo");
2968 
2969  // Attach metadata to the loop's latch
2970  BasicBlock *Latch = Loop->getLatch();
2971  assert(Latch && "A valid CanonicalLoopInfo must have a unique latch");
2972  addBasicBlockMetadata(Latch, Properties);
2973 }
2974 
2975 /// Attach llvm.access.group metadata to the memref instructions of \p Block
2976 static void addSimdMetadata(BasicBlock *Block, MDNode *AccessGroup,
2977  LoopInfo &LI) {
2978  for (Instruction &I : *Block) {
2979  if (I.mayReadOrWriteMemory()) {
2980  // TODO: This instruction may already have access group from
2981  // other pragmas e.g. #pragma clang loop vectorize. Append
2982  // so that the existing metadata is not overwritten.
2983  I.setMetadata(LLVMContext::MD_access_group, AccessGroup);
2984  }
2985  }
2986 }
2987 
2989  LLVMContext &Ctx = Builder.getContext();
2991  Loop, {MDNode::get(Ctx, MDString::get(Ctx, "llvm.loop.unroll.enable")),
2992  MDNode::get(Ctx, MDString::get(Ctx, "llvm.loop.unroll.full"))});
2993 }
2994 
2996  LLVMContext &Ctx = Builder.getContext();
2998  Loop, {
2999  MDNode::get(Ctx, MDString::get(Ctx, "llvm.loop.unroll.enable")),
3000  });
3001 }
3002 
3003 void OpenMPIRBuilder::createIfVersion(CanonicalLoopInfo *CanonicalLoop,
3004  Value *IfCond, ValueToValueMapTy &VMap,
3005  const Twine &NamePrefix) {
3006  Function *F = CanonicalLoop->getFunction();
3007 
3008  // Define where if branch should be inserted
3009  Instruction *SplitBefore;
3010  if (Instruction::classof(IfCond)) {
3011  SplitBefore = dyn_cast<Instruction>(IfCond);
3012  } else {
3013  SplitBefore = CanonicalLoop->getPreheader()->getTerminator();
3014  }
3015 
3016  // TODO: We should not rely on pass manager. Currently we use pass manager
3017  // only for getting llvm::Loop which corresponds to given CanonicalLoopInfo
3018  // object. We should have a method which returns all blocks between
3019  // CanonicalLoopInfo::getHeader() and CanonicalLoopInfo::getAfter()
3021  FAM.registerPass([]() { return DominatorTreeAnalysis(); });
3022  FAM.registerPass([]() { return LoopAnalysis(); });
3023  FAM.registerPass([]() { return PassInstrumentationAnalysis(); });
3024 
3025  // Get the loop which needs to be cloned
3026  LoopAnalysis LIA;
3027  LoopInfo &&LI = LIA.run(*F, FAM);
3028  Loop *L = LI.getLoopFor(CanonicalLoop->getHeader());
3029 
3030  // Create additional blocks for the if statement
3031  BasicBlock *Head = SplitBefore->getParent();
3032  Instruction *HeadOldTerm = Head->getTerminator();
3033  llvm::LLVMContext &C = Head->getContext();
3035  C, NamePrefix + ".if.then", Head->getParent(), Head->getNextNode());
3037  C, NamePrefix + ".if.else", Head->getParent(), CanonicalLoop->getExit());
3038 
3039  // Create if condition branch.
3040  Builder.SetInsertPoint(HeadOldTerm);
3041  Instruction *BrInstr =
3042  Builder.CreateCondBr(IfCond, ThenBlock, /*ifFalse*/ ElseBlock);
3043  InsertPointTy IP{BrInstr->getParent(), ++BrInstr->getIterator()};
3044  // Then block contains branch to omp loop which needs to be vectorized
3045  spliceBB(IP, ThenBlock, false);
3046  ThenBlock->replaceSuccessorsPhiUsesWith(Head, ThenBlock);
3047 
3048  Builder.SetInsertPoint(ElseBlock);
3049 
3050  // Clone loop for the else branch
3051  SmallVector<BasicBlock *, 8> NewBlocks;
3052 
3053  VMap[CanonicalLoop->getPreheader()] = ElseBlock;
3054  for (BasicBlock *Block : L->getBlocks()) {
3055  BasicBlock *NewBB = CloneBasicBlock(Block, VMap, "", F);
3056  NewBB->moveBefore(CanonicalLoop->getExit());
3057  VMap[Block] = NewBB;
3058  NewBlocks.push_back(NewBB);
3059  }
3060  remapInstructionsInBlocks(NewBlocks, VMap);
3061  Builder.CreateBr(NewBlocks.front());
3062 }
3063 
3065  MapVector<Value *, Value *> AlignedVars,
3066  Value *IfCond, OrderKind Order,
3067  ConstantInt *Simdlen, ConstantInt *Safelen) {
3068  LLVMContext &Ctx = Builder.getContext();
3069 
3070  Function *F = CanonicalLoop->getFunction();
3071 
3072  // TODO: We should not rely on pass manager. Currently we use pass manager
3073  // only for getting llvm::Loop which corresponds to given CanonicalLoopInfo
3074  // object. We should have a method which returns all blocks between
3075  // CanonicalLoopInfo::getHeader() and CanonicalLoopInfo::getAfter()
3077  FAM.registerPass([]() { return DominatorTreeAnalysis(); });
3078  FAM.registerPass([]() { return LoopAnalysis(); });
3079  FAM.registerPass([]() { return PassInstrumentationAnalysis(); });
3080 
3081  LoopAnalysis LIA;
3082  LoopInfo &&LI = LIA.run(*F, FAM);
3083 
3084  Loop *L = LI.getLoopFor(CanonicalLoop->getHeader());
3085  if (AlignedVars.size()) {
3086  InsertPointTy IP = Builder.saveIP();
3087  Builder.SetInsertPoint(CanonicalLoop->getPreheader()->getTerminator());
3088  for (auto &AlignedItem : AlignedVars) {
3089  Value *AlignedPtr = AlignedItem.first;
3090  Value *Alignment = AlignedItem.second;
3091  Builder.CreateAlignmentAssumption(F->getParent()->getDataLayout(),
3092  AlignedPtr, Alignment);
3093  }
3094  Builder.restoreIP(IP);
3095  }
3096 
3097  if (IfCond) {
3098  ValueToValueMapTy VMap;
3099  createIfVersion(CanonicalLoop, IfCond, VMap, "simd");
3100  // Add metadata to the cloned loop which disables vectorization
3101  Value *MappedLatch = VMap.lookup(CanonicalLoop->getLatch());
3102  assert(MappedLatch &&
3103  "Cannot find value which corresponds to original loop latch");
3104  assert(isa<BasicBlock>(MappedLatch) &&
3105  "Cannot cast mapped latch block value to BasicBlock");
3106  BasicBlock *NewLatchBlock = dyn_cast<BasicBlock>(MappedLatch);
3107  ConstantAsMetadata *BoolConst =
3110  NewLatchBlock,
3111  {MDNode::get(Ctx, {MDString::get(Ctx, "llvm.loop.vectorize.enable"),
3112  BoolConst})});
3113  }
3114 
3115  SmallSet<BasicBlock *, 8> Reachable;
3116 
3117  // Get the basic blocks from the loop in which memref instructions
3118  // can be found.
3119  // TODO: Generalize getting all blocks inside a CanonicalizeLoopInfo,
3120  // preferably without running any passes.
3121  for (BasicBlock *Block : L->getBlocks()) {
3122  if (Block == CanonicalLoop->getCond() ||
3123  Block == CanonicalLoop->getHeader())
3124  continue;
3125  Reachable.insert(Block);
3126  }
3127 
3128  SmallVector<Metadata *> LoopMDList;
3129 
3130  // In presence of finite 'safelen', it may be unsafe to mark all
3131  // the memory instructions parallel, because loop-carried
3132  // dependences of 'safelen' iterations are possible.
3133  // If clause order(concurrent) is specified then the memory instructions
3134  // are marked parallel even if 'safelen' is finite.
3135  if ((Safelen == nullptr) || (Order == OrderKind::OMP_ORDER_concurrent)) {
3136  // Add access group metadata to memory-access instructions.
3137  MDNode *AccessGroup = MDNode::getDistinct(Ctx, {});
3138  for (BasicBlock *BB : Reachable)
3139  addSimdMetadata(BB, AccessGroup, LI);
3140  // TODO: If the loop has existing parallel access metadata, have
3141  // to combine two lists.
3142  LoopMDList.push_back(MDNode::get(
3143  Ctx, {MDString::get(Ctx, "llvm.loop.parallel_accesses"), AccessGroup}));
3144  }
3145 
3146  // Use the above access group metadata to create loop level
3147  // metadata, which should be distinct for each loop.
3148  ConstantAsMetadata *BoolConst =
3150  LoopMDList.push_back(MDNode::get(
3151  Ctx, {MDString::get(Ctx, "llvm.loop.vectorize.enable"), BoolConst}));
3152 
3153  if (Simdlen || Safelen) {
3154  // If both simdlen and safelen clauses are specified, the value of the
3155  // simdlen parameter must be less than or equal to the value of the safelen
3156  // parameter. Therefore, use safelen only in the absence of simdlen.
3157  ConstantInt *VectorizeWidth = Simdlen == nullptr ? Safelen : Simdlen;
3158  LoopMDList.push_back(
3159  MDNode::get(Ctx, {MDString::get(Ctx, "llvm.loop.vectorize.width"),
3160  ConstantAsMetadata::get(VectorizeWidth)}));
3161  }
3162 
3163  addLoopMetadata(CanonicalLoop, LoopMDList);
3164 }
3165 
3166 /// Create the TargetMachine object to query the backend for optimization
3167 /// preferences.
3168 ///
3169 /// Ideally, this would be passed from the front-end to the OpenMPBuilder, but
3170 /// e.g. Clang does not pass it to its CodeGen layer and creates it only when
3171 /// needed for the LLVM pass pipline. We use some default options to avoid
3172 /// having to pass too many settings from the frontend that probably do not
3173 /// matter.
3174 ///
3175 /// Currently, TargetMachine is only used sometimes by the unrollLoopPartial
3176 /// method. If we are going to use TargetMachine for more purposes, especially
3177 /// those that are sensitive to TargetOptions, RelocModel and CodeModel, it
3178 /// might become be worth requiring front-ends to pass on their TargetMachine,
3179 /// or at least cache it between methods. Note that while fontends such as Clang
3180 /// have just a single main TargetMachine per translation unit, "target-cpu" and
3181 /// "target-features" that determine the TargetMachine are per-function and can
3182 /// be overrided using __attribute__((target("OPTIONS"))).
3183 static std::unique_ptr<TargetMachine>
3185  Module *M = F->getParent();
3186 
3187  StringRef CPU = F->getFnAttribute("target-cpu").getValueAsString();
3188  StringRef Features = F->getFnAttribute("target-features").getValueAsString();
3189  const std::string &Triple = M->getTargetTriple();
3190 
3191  std::string Error;
3193  if (!TheTarget)
3194  return {};
3195 
3197  return std::unique_ptr<TargetMachine>(TheTarget->createTargetMachine(
3198  Triple, CPU, Features, Options, /*RelocModel=*/None, /*CodeModel=*/None,
3199  OptLevel));
3200 }
3201 
3202 /// Heuristically determine the best-performant unroll factor for \p CLI. This
3203 /// depends on the target processor. We are re-using the same heuristics as the
3204 /// LoopUnrollPass.
3206  Function *F = CLI->getFunction();
3207 
3208  // Assume the user requests the most aggressive unrolling, even if the rest of
3209  // the code is optimized using a lower setting.
3211  std::unique_ptr<TargetMachine> TM = createTargetMachine(F, OptLevel);
3212 
3214  FAM.registerPass([]() { return TargetLibraryAnalysis(); });
3215  FAM.registerPass([]() { return AssumptionAnalysis(); });
3216  FAM.registerPass([]() { return DominatorTreeAnalysis(); });
3217  FAM.registerPass([]() { return LoopAnalysis(); });
3218  FAM.registerPass([]() { return ScalarEvolutionAnalysis(); });
3219  FAM.registerPass([]() { return PassInstrumentationAnalysis(); });
3220  TargetIRAnalysis TIRA;
3221  if (TM)
3222  TIRA = TargetIRAnalysis(
3223  [&](const Function &F) { return TM->getTargetTransformInfo(F); });
3224  FAM.registerPass([&]() { return TIRA; });
3225 
3226  TargetIRAnalysis::Result &&TTI = TIRA.run(*F, FAM);
3228  ScalarEvolution &&SE = SEA.run(*F, FAM);
3230  DominatorTree &&DT = DTA.run(*F, FAM);
3231  LoopAnalysis LIA;
3232  LoopInfo &&LI = LIA.run(*F, FAM);
3233  AssumptionAnalysis ACT;
3234  AssumptionCache &&AC = ACT.run(*F, FAM);
3236 
3237  Loop *L = LI.getLoopFor(CLI->getHeader());
3238  assert(L && "Expecting CanonicalLoopInfo to be recognized as a loop");
3239 
3242  /*BlockFrequencyInfo=*/nullptr,
3243  /*ProfileSummaryInfo=*/nullptr, ORE, OptLevel,
3244  /*UserThreshold=*/None,
3245  /*UserCount=*/None,
3246  /*UserAllowPartial=*/true,
3247  /*UserAllowRuntime=*/true,
3248  /*UserUpperBound=*/None,
3249  /*UserFullUnrollMaxCount=*/None);
3250 
3251  UP.Force = true;
3252 
3253  // Account for additional optimizations taking place before the LoopUnrollPass
3254  // would unroll the loop.
3257 
3258  // Use normal unroll factors even if the rest of the code is optimized for
3259  // size.
3260  UP.OptSizeThreshold = UP.Threshold;
3262 
3263  LLVM_DEBUG(dbgs() << "Unroll heuristic thresholds:\n"
3264  << " Threshold=" << UP.Threshold << "\n"
3265  << " PartialThreshold=" << UP.PartialThreshold << "\n"
3266  << " OptSizeThreshold=" << UP.OptSizeThreshold << "\n"
3267  << " PartialOptSizeThreshold="
3268  << UP.PartialOptSizeThreshold << "\n");
3269 
3270  // Disable peeling.
3273  /*UserAllowPeeling=*/false,
3274  /*UserAllowProfileBasedPeeling=*/false,
3275  /*UnrollingSpecficValues=*/false);
3276 
3278  CodeMetrics::collectEphemeralValues(L, &AC, EphValues);
3279 
3280  // Assume that reads and writes to stack variables can be eliminated by
3281  // Mem2Reg, SROA or LICM. That is, don't count them towards the loop body's
3282  // size.
3283  for (BasicBlock *BB : L->blocks()) {
3284  for (Instruction &I : *BB) {
3285  Value *Ptr;
3286  if (auto *Load = dyn_cast<LoadInst>(&I)) {
3287  Ptr = Load->getPointerOperand();
3288  } else if (auto *Store = dyn_cast<StoreInst>(&I)) {
3289  Ptr = Store->getPointerOperand();
3290  } else
3291  continue;
3292 
3293  Ptr = Ptr->stripPointerCasts();
3294 
3295  if (auto *Alloca = dyn_cast<AllocaInst>(Ptr)) {
3296  if (Alloca->getParent() == &F->getEntryBlock())
3297  EphValues.insert(&I);
3298  }
3299  }
3300  }
3301 
3302  unsigned NumInlineCandidates;
3303  bool NotDuplicatable;
3304  bool Convergent;
3305  InstructionCost LoopSizeIC =
3306  ApproximateLoopSize(L, NumInlineCandidates, NotDuplicatable, Convergent,
3307  TTI, EphValues, UP.BEInsns);
3308  LLVM_DEBUG(dbgs() << "Estimated loop size is " << LoopSizeIC << "\n");
3309 
3310  // Loop is not unrollable if the loop contains certain instructions.
3311  if (NotDuplicatable || Convergent || !LoopSizeIC.isValid()) {
3312  LLVM_DEBUG(dbgs() << "Loop not considered unrollable\n");
3313  return 1;
3314  }
3315  unsigned LoopSize = *LoopSizeIC.getValue();
3316 
3317  // TODO: Determine trip count of \p CLI if constant, computeUnrollCount might
3318  // be able to use it.
3319  int TripCount = 0;
3320  int MaxTripCount = 0;
3321  bool MaxOrZero = false;
3322  unsigned TripMultiple = 0;
3323 
3324  bool UseUpperBound = false;
3325  computeUnrollCount(L, TTI, DT, &LI, &AC, SE, EphValues, &ORE, TripCount,
3326  MaxTripCount, MaxOrZero, TripMultiple, LoopSize, UP, PP,
3327  UseUpperBound);
3328  unsigned Factor = UP.Count;
3329  LLVM_DEBUG(dbgs() << "Suggesting unroll factor of " << Factor << "\n");
3330 
3331  // This function returns 1 to signal to not unroll a loop.
3332  if (Factor == 0)
3333  return 1;
3334  return Factor;
3335 }
3336 
3338  int32_t Factor,
3339  CanonicalLoopInfo **UnrolledCLI) {
3340  assert(Factor >= 0 && "Unroll factor must not be negative");
3341 
3342  Function *F = Loop->getFunction();
3343  LLVMContext &Ctx = F->getContext();
3344 
3345  // If the unrolled loop is not used for another loop-associated directive, it
3346  // is sufficient to add metadata for the LoopUnrollPass.
3347  if (!UnrolledCLI) {
3348  SmallVector<Metadata *, 2> LoopMetadata;
3349  LoopMetadata.push_back(
3350  MDNode::get(Ctx, MDString::get(Ctx, "llvm.loop.unroll.enable")));
3351 
3352  if (Factor >= 1) {
3354  ConstantInt::get(Type::getInt32Ty(Ctx), APInt(32, Factor)));
3355  LoopMetadata.push_back(MDNode::get(
3356  Ctx, {MDString::get(Ctx, "llvm.loop.unroll.count"), FactorConst}));
3357  }
3358 
3359  addLoopMetadata(Loop, LoopMetadata);
3360  return;
3361  }
3362 
3363  // Heuristically determine the unroll factor.
3364  if (Factor == 0)
3366 
3367  // No change required with unroll factor 1.
3368  if (Factor == 1) {
3369  *UnrolledCLI = Loop;
3370  return;
3371  }
3372 
3373  assert(Factor >= 2 &&
3374  "unrolling only makes sense with a factor of 2 or larger");
3375 
3376  Type *IndVarTy = Loop->getIndVarType();
3377 
3378  // Apply partial unrolling by tiling the loop by the unroll-factor, then fully
3379  // unroll the inner loop.
3380  Value *FactorVal =
3381  ConstantInt::get(IndVarTy, APInt(IndVarTy->getIntegerBitWidth(), Factor,
3382  /*isSigned=*/false));
3383  std::vector<CanonicalLoopInfo *> LoopNest =
3384  tileLoops(DL, {Loop}, {FactorVal});
3385  assert(LoopNest.size() == 2 && "Expect 2 loops after tiling");
3386  *UnrolledCLI = LoopNest[0];
3387  CanonicalLoopInfo *InnerLoop = LoopNest[1];
3388 
3389  // LoopUnrollPass can only fully unroll loops with constant trip count.
3390  // Unroll by the unroll factor with a fallback epilog for the remainder
3391  // iterations if necessary.
3393  ConstantInt::get(Type::getInt32Ty(Ctx), APInt(32, Factor)));
3395  InnerLoop,
3396  {MDNode::get(Ctx, MDString::get(Ctx, "llvm.loop.unroll.enable")),
3397  MDNode::get(
3398  Ctx, {MDString::get(Ctx, "llvm.loop.unroll.count"), FactorConst})});
3399 
3400 #ifndef NDEBUG
3401  (*UnrolledCLI)->assertOK();
3402 #endif
3403 }
3404 
3407  llvm::Value *BufSize, llvm::Value *CpyBuf,
3408  llvm::Value *CpyFn, llvm::Value *DidIt) {
3409  if (!updateToLocation(Loc))
3410  return Loc.IP;
3411 
3412  uint32_t SrcLocStrSize;
3413  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
3414  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
3415  Value *ThreadId = getOrCreateThreadID(Ident);
3416 
3417  llvm::Value *DidItLD = Builder.CreateLoad(Builder.getInt32Ty(), DidIt);
3418 
3419  Value *Args[] = {Ident, ThreadId, BufSize, CpyBuf, CpyFn, DidItLD};
3420 
3421  Function *Fn = getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_copyprivate);
3422  Builder.CreateCall(Fn, Args);
3423 
3424  return Builder.saveIP();
3425 }
3426 
3428  const LocationDescription &Loc, BodyGenCallbackTy BodyGenCB,
3429  FinalizeCallbackTy FiniCB, bool IsNowait, llvm::Value *DidIt) {
3430 
3431  if (!updateToLocation(Loc))
3432  return Loc.IP;
3433 
3434  // If needed (i.e. not null), initialize `DidIt` with 0
3435  if (DidIt) {
3436  Builder.CreateStore(Builder.getInt32(0), DidIt);
3437  }
3438 
3439  Directive OMPD = Directive::OMPD_single;
3440  uint32_t SrcLocStrSize;
3441  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
3442  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
3443  Value *ThreadId = getOrCreateThreadID(Ident);
3444  Value *Args[] = {Ident, ThreadId};
3445 
3446  Function *EntryRTLFn = getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_single);
3447  Instruction *EntryCall = Builder.CreateCall(EntryRTLFn, Args);
3448 
3449  Function *ExitRTLFn = getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_end_single);
3450  Instruction *ExitCall = Builder.CreateCall(ExitRTLFn, Args);
3451 
3452  // generates the following:
3453  // if (__kmpc_single()) {
3454  // .... single region ...
3455  // __kmpc_end_single
3456  // }
3457  // __kmpc_barrier
3458 
3459  EmitOMPInlinedRegion(OMPD, EntryCall, ExitCall, BodyGenCB, FiniCB,
3460  /*Conditional*/ true,
3461  /*hasFinalize*/ true);
3462  if (!IsNowait)
3463  createBarrier(LocationDescription(Builder.saveIP(), Loc.DL),
3464  omp::Directive::OMPD_unknown, /* ForceSimpleCall */ false,
3465  /* CheckCancelFlag */ false);
3466  return Builder.saveIP();
3467 }
3468 
3470  const LocationDescription &Loc, BodyGenCallbackTy BodyGenCB,
3471  FinalizeCallbackTy FiniCB, StringRef CriticalName, Value *HintInst) {
3472 
3473  if (!updateToLocation(Loc))
3474  return Loc.IP;
3475 
3476  Directive OMPD = Directive::OMPD_critical;
3477  uint32_t SrcLocStrSize;
3478  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
3479  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
3480  Value *ThreadId = getOrCreateThreadID(Ident);
3481  Value *LockVar = getOMPCriticalRegionLock(CriticalName);
3482  Value *Args[] = {Ident, ThreadId, LockVar};
3483 
3485  Function *RTFn = nullptr;
3486  if (HintInst) {
3487  // Add Hint to entry Args and create call
3488  EnterArgs.push_back(HintInst);
3489  RTFn = getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_critical_with_hint);
3490  } else {
3491  RTFn = getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_critical);
3492  }
3493  Instruction *EntryCall = Builder.CreateCall(RTFn, EnterArgs);
3494 
3495  Function *ExitRTLFn =
3496  getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_end_critical);
3497  Instruction *ExitCall = Builder.CreateCall(ExitRTLFn, Args);
3498 
3499  return EmitOMPInlinedRegion(OMPD, EntryCall, ExitCall, BodyGenCB, FiniCB,
3500  /*Conditional*/ false, /*hasFinalize*/ true);
3501 }
3502 
3505  InsertPointTy AllocaIP, unsigned NumLoops,
3506  ArrayRef<llvm::Value *> StoreValues,
3507  const Twine &Name, bool IsDependSource) {
3508  assert(
3509  llvm::all_of(StoreValues,
3510  [](Value *SV) { return SV->getType()->isIntegerTy(64); }) &&
3511  "OpenMP runtime requires depend vec with i64 type");
3512 
3513  if (!updateToLocation(Loc))
3514  return Loc.IP;
3515 
3516  // Allocate space for vector and generate alloc instruction.
3517  auto *ArrI64Ty = ArrayType::get(Int64, NumLoops);
3518  Builder.restoreIP(AllocaIP);
3519  AllocaInst *ArgsBase = Builder.CreateAlloca(ArrI64Ty, nullptr, Name);
3520  ArgsBase->setAlignment(Align(8));
3521  Builder.restoreIP(Loc.IP);
3522 
3523  // Store the index value with offset in depend vector.
3524  for (unsigned I = 0; I < NumLoops; ++I) {
3525  Value *DependAddrGEPIter = Builder.CreateInBoundsGEP(
3526  ArrI64Ty, ArgsBase, {Builder.getInt64(0), Builder.getInt64(I)});
3527  StoreInst *STInst = Builder.CreateStore(StoreValues[I], DependAddrGEPIter);
3528  STInst->setAlignment(Align(8));
3529  }
3530 
3531  Value *DependBaseAddrGEP = Builder.CreateInBoundsGEP(
3532  ArrI64Ty, ArgsBase, {Builder.getInt64(0), Builder.getInt64(0)});
3533 
3534  uint32_t SrcLocStrSize;
3535  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
3536  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
3537  Value *ThreadId = getOrCreateThreadID(Ident);
3538  Value *Args[] = {Ident, ThreadId, DependBaseAddrGEP};
3539 
3540  Function *RTLFn = nullptr;
3541  if (IsDependSource)
3542  RTLFn = getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_doacross_post);
3543  else
3544  RTLFn = getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_doacross_wait);
3545  Builder.CreateCall(RTLFn, Args);
3546 
3547  return Builder.saveIP();
3548 }
3549 
3551  const LocationDescription &Loc, BodyGenCallbackTy BodyGenCB,
3552  FinalizeCallbackTy FiniCB, bool IsThreads) {
3553  if (!updateToLocation(Loc))
3554  return Loc.IP;
3555 
3556  Directive OMPD = Directive::OMPD_ordered;
3557  Instruction *EntryCall = nullptr;
3558  Instruction *ExitCall = nullptr;
3559 
3560  if (IsThreads) {
3561  uint32_t SrcLocStrSize;
3562  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
3563  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
3564  Value *ThreadId = getOrCreateThreadID(Ident);
3565  Value *Args[] = {Ident, ThreadId};
3566 
3567  Function *EntryRTLFn = getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_ordered);
3568  EntryCall = Builder.CreateCall(EntryRTLFn, Args);
3569 
3570  Function *ExitRTLFn =
3571  getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_end_ordered);
3572  ExitCall = Builder.CreateCall(ExitRTLFn, Args);
3573  }
3574 
3575  return EmitOMPInlinedRegion(OMPD, EntryCall, ExitCall, BodyGenCB, FiniCB,
3576  /*Conditional*/ false, /*hasFinalize*/ true);
3577 }
3578 
3579 OpenMPIRBuilder::InsertPointTy OpenMPIRBuilder::EmitOMPInlinedRegion(
3580  Directive OMPD, Instruction *EntryCall, Instruction *ExitCall,
3581  BodyGenCallbackTy BodyGenCB, FinalizeCallbackTy FiniCB, bool Conditional,
3582  bool HasFinalize, bool IsCancellable) {
3583 
3584  if (HasFinalize)
3585  FinalizationStack.push_back({FiniCB, OMPD, IsCancellable});
3586 
3587  // Create inlined region's entry and body blocks, in preparation
3588  // for conditional creation
3589  BasicBlock *EntryBB = Builder.GetInsertBlock();
3590  Instruction *SplitPos = EntryBB->getTerminator();
3591  if (!isa_and_nonnull<BranchInst>(SplitPos))
3592  SplitPos = new UnreachableInst(Builder.getContext(), EntryBB);
3593  BasicBlock *ExitBB = EntryBB->splitBasicBlock(SplitPos, "omp_region.end");
3594  BasicBlock *FiniBB =
3595  EntryBB->splitBasicBlock(EntryBB->getTerminator(), "omp_region.finalize");
3596 
3597  Builder.SetInsertPoint(EntryBB->getTerminator());
3598  emitCommonDirectiveEntry(OMPD, EntryCall, ExitBB, Conditional);
3599 
3600  // generate body
3601  BodyGenCB(/* AllocaIP */ InsertPointTy(),
3602  /* CodeGenIP */ Builder.saveIP());
3603 
3604  // emit exit call and do any needed finalization.
3605  auto FinIP = InsertPointTy(FiniBB, FiniBB->getFirstInsertionPt());
3606  assert(FiniBB->getTerminator()->getNumSuccessors() == 1 &&
3607  FiniBB->getTerminator()->getSuccessor(0) == ExitBB &&
3608  "Unexpected control flow graph state!!");
3609  emitCommonDirectiveExit(OMPD, FinIP, ExitCall, HasFinalize);
3610  assert(FiniBB->getUniquePredecessor()->getUniqueSuccessor() == FiniBB &&
3611  "Unexpected Control Flow State!");
3612  MergeBlockIntoPredecessor(FiniBB);
3613 
3614  // If we are skipping the region of a non conditional, remove the exit
3615  // block, and clear the builder's insertion point.
3616  assert(SplitPos->getParent() == ExitBB &&
3617  "Unexpected Insertion point location!");
3618  auto merged = MergeBlockIntoPredecessor(ExitBB);
3619  BasicBlock *ExitPredBB = SplitPos->getParent();
3620  auto InsertBB = merged ? ExitPredBB : ExitBB;
3621  if (!isa_and_nonnull<BranchInst>(SplitPos))
3622  SplitPos->eraseFromParent();
3623  Builder.SetInsertPoint(InsertBB);
3624 
3625  return Builder.saveIP();
3626 }
3627 
3628 OpenMPIRBuilder::InsertPointTy OpenMPIRBuilder::emitCommonDirectiveEntry(
3629  Directive OMPD, Value *EntryCall, BasicBlock *ExitBB, bool Conditional) {
3630  // if nothing to do, Return current insertion point.
3631  if (!Conditional || !EntryCall)
3632  return Builder.saveIP();
3633 
3634  BasicBlock *EntryBB = Builder.GetInsertBlock();
3635  Value *CallBool = Builder.CreateIsNotNull(EntryCall);
3636  auto *ThenBB = BasicBlock::Create(M.getContext(), "omp_region.body");
3637  auto *UI = new UnreachableInst(Builder.getContext(), ThenBB);
3638 
3639  // Emit thenBB and set the Builder's insertion point there for
3640  // body generation next. Place the block after the current block.
3641  Function *CurFn = EntryBB->getParent();
3642  CurFn->getBasicBlockList().insertAfter(EntryBB->getIterator(), ThenBB);
3643 
3644  // Move Entry branch to end of ThenBB, and replace with conditional
3645  // branch (If-stmt)
3646  Instruction *EntryBBTI = EntryBB->getTerminator();
3647  Builder.CreateCondBr(CallBool, ThenBB, ExitBB);
3648  EntryBBTI->removeFromParent();
3649  Builder.SetInsertPoint(UI);
3650  Builder.Insert(EntryBBTI);
3651  UI->eraseFromParent();
3652  Builder.SetInsertPoint(ThenBB->getTerminator());
3653 
3654  // return an insertion point to ExitBB.
3655  return IRBuilder<>::InsertPoint(ExitBB, ExitBB->getFirstInsertionPt());
3656 }
3657 
3658 OpenMPIRBuilder::InsertPointTy OpenMPIRBuilder::emitCommonDirectiveExit(
3659  omp::Directive OMPD, InsertPointTy FinIP, Instruction *ExitCall,
3660  bool HasFinalize) {
3661 
3662  Builder.restoreIP(FinIP);
3663 
3664  // If there is finalization to do, emit it before the exit call
3665  if (HasFinalize) {
3666  assert(!FinalizationStack.empty() &&
3667  "Unexpected finalization stack state!");
3668 
3669  FinalizationInfo Fi = FinalizationStack.pop_back_val();
3670  assert(Fi.DK == OMPD && "Unexpected Directive for Finalization call!");
3671 
3672  Fi.FiniCB(FinIP);
3673 
3674  BasicBlock *FiniBB = FinIP.getBlock();
3675  Instruction *FiniBBTI = FiniBB->getTerminator();
3676 
3677  // set Builder IP for call creation
3678  Builder.SetInsertPoint(FiniBBTI);
3679  }
3680 
3681  if (!ExitCall)
3682  return Builder.saveIP();
3683 
3684  // place the Exitcall as last instruction before Finalization block terminator
3685  ExitCall->removeFromParent();
3686  Builder.Insert(ExitCall);
3687 
3688  return IRBuilder<>::InsertPoint(ExitCall->getParent(),
3689  ExitCall->getIterator());
3690 }
3691 
3693  InsertPointTy IP, Value *MasterAddr, Value *PrivateAddr,
3694  llvm::IntegerType *IntPtrTy, bool BranchtoEnd) {
3695  if (!IP.isSet())
3696  return IP;
3697 
3699 
3700  // creates the following CFG structure
3701  // OMP_Entry : (MasterAddr != PrivateAddr)?
3702  // F T
3703  // | \
3704  // | copin.not.master
3705  // | /
3706  // v /
3707  // copyin.not.master.end
3708  // |
3709  // v
3710  // OMP.Entry.Next
3711 
3712  BasicBlock *OMP_Entry = IP.getBlock();
3713  Function *CurFn = OMP_Entry->getParent();
3714  BasicBlock *CopyBegin =
3715  BasicBlock::Create(M.getContext(), "copyin.not.master", CurFn);
3716  BasicBlock *CopyEnd = nullptr;
3717 
3718  // If entry block is terminated, split to preserve the branch to following
3719  // basic block (i.e. OMP.Entry.Next), otherwise, leave everything as is.
3720  if (isa_and_nonnull<BranchInst>(OMP_Entry->getTerminator())) {
3721  CopyEnd = OMP_Entry->splitBasicBlock(OMP_Entry->getTerminator(),
3722  "copyin.not.master.end");
3723  OMP_Entry->getTerminator()->eraseFromParent();
3724  } else {
3725  CopyEnd =
3726  BasicBlock::Create(M.getContext(), "copyin.not.master.end", CurFn);
3727  }
3728 
3729  Builder.SetInsertPoint(OMP_Entry);
3730  Value *MasterPtr = Builder.CreatePtrToInt(MasterAddr, IntPtrTy);
3731  Value *PrivatePtr = Builder.CreatePtrToInt(PrivateAddr, IntPtrTy);
3732  Value *cmp = Builder.CreateICmpNE(MasterPtr, PrivatePtr);
3733  Builder.CreateCondBr(cmp, CopyBegin, CopyEnd);
3734 
3735  Builder.SetInsertPoint(CopyBegin);
3736  if (BranchtoEnd)
3737  Builder.SetInsertPoint(Builder.CreateBr(CopyEnd));
3738 
3739  return Builder.saveIP();
3740 }
3741 
3743  Value *Size, Value *Allocator,
3744  std::string Name) {
3746  Builder.restoreIP(Loc.IP);
3747 
3748  uint32_t SrcLocStrSize;
3749  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
3750  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
3751  Value *ThreadId = getOrCreateThreadID(Ident);
3752  Value *Args[] = {ThreadId, Size, Allocator};
3753 
3754  Function *Fn = getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_alloc);
3755 
3756  return Builder.CreateCall(Fn, Args, Name);
3757 }
3758 
3761  std::string Name) {
3763  Builder.restoreIP(Loc.IP);
3764 
3765  uint32_t SrcLocStrSize;
3766  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
3767  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
3768  Value *ThreadId = getOrCreateThreadID(Ident);
3769  Value *Args[] = {ThreadId, Addr, Allocator};
3770  Function *Fn = getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_free);
3771  return Builder.CreateCall(Fn, Args, Name);
3772 }
3773 
3775  const LocationDescription &Loc, Value *InteropVar,
3776  omp::OMPInteropType InteropType, Value *Device, Value *NumDependences,
3777  Value *DependenceAddress, bool HaveNowaitClause) {
3779  Builder.restoreIP(Loc.IP);
3780 
3781  uint32_t SrcLocStrSize;
3782  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
3783  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
3784  Value *ThreadId = getOrCreateThreadID(Ident);
3785  if (Device == nullptr)
3786  Device = ConstantInt::get(Int32, -1);
3787  Constant *InteropTypeVal = ConstantInt::get(Int64, (int)InteropType);
3788  if (NumDependences == nullptr) {
3789  NumDependences = ConstantInt::get(Int32, 0);
3790  PointerType *PointerTypeVar = Type::getInt8PtrTy(M.getContext());
3791  DependenceAddress = ConstantPointerNull::get(PointerTypeVar);
3792  }
3793  Value *HaveNowaitClauseVal = ConstantInt::get(Int32, HaveNowaitClause);
3794  Value *Args[] = {
3795  Ident, ThreadId, InteropVar, InteropTypeVal,
3796  Device, NumDependences, DependenceAddress, HaveNowaitClauseVal};
3797 
3798  Function *Fn = getOrCreateRuntimeFunctionPtr(OMPRTL___tgt_interop_init);
3799 
3800  return Builder.CreateCall(Fn, Args);
3801 }
3802 
3804  const LocationDescription &Loc, Value *InteropVar, Value *Device,
3805  Value *NumDependences, Value *DependenceAddress, bool HaveNowaitClause) {
3807  Builder.restoreIP(Loc.IP);
3808 
3809  uint32_t SrcLocStrSize;
3810  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
3811  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
3812  Value *ThreadId = getOrCreateThreadID(Ident);
3813  if (Device == nullptr)
3814  Device = ConstantInt::get(Int32, -1);
3815  if (NumDependences == nullptr) {
3816  NumDependences = ConstantInt::get(Int32, 0);
3817  PointerType *PointerTypeVar = Type::getInt8PtrTy(M.getContext());
3818  DependenceAddress = ConstantPointerNull::get(PointerTypeVar);
3819  }
3820  Value *HaveNowaitClauseVal = ConstantInt::get(Int32, HaveNowaitClause);
3821  Value *Args[] = {
3822  Ident, ThreadId, InteropVar, Device,
3823  NumDependences, DependenceAddress, HaveNowaitClauseVal};
3824 
3825  Function *Fn = getOrCreateRuntimeFunctionPtr(OMPRTL___tgt_interop_destroy);
3826 
3827  return Builder.CreateCall(Fn, Args);
3828 }
3829 
3831  Value *InteropVar, Value *Device,
3832  Value *NumDependences,
3833  Value *DependenceAddress,
3834  bool HaveNowaitClause) {
3836  Builder.restoreIP(Loc.IP);
3837  uint32_t SrcLocStrSize;
3838  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
3839  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
3840  Value *ThreadId = getOrCreateThreadID(Ident);
3841  if (Device == nullptr)
3842  Device = ConstantInt::get(Int32, -1);
3843  if (NumDependences == nullptr) {
3844  NumDependences = ConstantInt::get(Int32, 0);
3845  PointerType *PointerTypeVar = Type::getInt8PtrTy(M.getContext());
3846  DependenceAddress = ConstantPointerNull::get(PointerTypeVar);
3847  }
3848  Value *HaveNowaitClauseVal = ConstantInt::get(Int32, HaveNowaitClause);
3849  Value *Args[] = {
3850  Ident, ThreadId, InteropVar, Device,
3851  NumDependences, DependenceAddress, HaveNowaitClauseVal};
3852 
3853  Function *Fn = getOrCreateRuntimeFunctionPtr(OMPRTL___tgt_interop_use);
3854 
3855  return Builder.CreateCall(Fn, Args);
3856 }
3857 
3859  const LocationDescription &Loc, llvm::Value *Pointer,
3860  llvm::ConstantInt *Size, const llvm::Twine &Name) {
3862  Builder.restoreIP(Loc.IP);
3863 
3864  uint32_t SrcLocStrSize;
3865  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
3866  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
3867  Value *ThreadId = getOrCreateThreadID(Ident);
3868  Constant *ThreadPrivateCache =
3869  getOrCreateInternalVariable(Int8PtrPtr, Name.str());
3870  llvm::Value *Args[] = {Ident, ThreadId, Pointer, Size, ThreadPrivateCache};
3871 
3872  Function *Fn =
3873  getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_threadprivate_cached);
3874 
3875  return Builder.CreateCall(Fn, Args);
3876 }
3877 
3880  bool RequiresFullRuntime) {
3881  if (!updateToLocation(Loc))
3882  return Loc.IP;
3883 
3884  uint32_t SrcLocStrSize;
3885  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
3886  Constant *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
3887  ConstantInt *IsSPMDVal = ConstantInt::getSigned(
3888  IntegerType::getInt8Ty(Int8->getContext()),
3890  ConstantInt *UseGenericStateMachine =
3891  ConstantInt::getBool(Int32->getContext(), !IsSPMD);
3892  ConstantInt *RequiresFullRuntimeVal =
3893  ConstantInt::getBool(Int32->getContext(), RequiresFullRuntime);
3894 
3895  Function *Fn = getOrCreateRuntimeFunctionPtr(
3896  omp::RuntimeFunction::OMPRTL___kmpc_target_init);
3897 
3898  CallInst *ThreadKind = Builder.CreateCall(
3899  Fn, {Ident, IsSPMDVal, UseGenericStateMachine, RequiresFullRuntimeVal});
3900 
3901  Value *ExecUserCode = Builder.CreateICmpEQ(
3902  ThreadKind, ConstantInt::get(ThreadKind->getType(), -1),
3903  "exec_user_code");
3904 
3905  // ThreadKind = __kmpc_target_init(...)
3906  // if (ThreadKind == -1)
3907  // user_code
3908  // else
3909  // return;
3910 
3911  auto *UI = Builder.CreateUnreachable();
3912  BasicBlock *CheckBB = UI->getParent();
3913  BasicBlock *UserCodeEntryBB = CheckBB->splitBasicBlock(UI, "user_code.entry");
3914 
3915  BasicBlock *WorkerExitBB = BasicBlock::Create(
3916  CheckBB->getContext(), "worker.exit", CheckBB->getParent());
3917  Builder.SetInsertPoint(WorkerExitBB);
3918  Builder.CreateRetVoid();
3919 
3920  auto *CheckBBTI = CheckBB->getTerminator();
3921  Builder.SetInsertPoint(CheckBBTI);
3922  Builder.CreateCondBr(ExecUserCode, UI->getParent(), WorkerExitBB);
3923 
3924  CheckBBTI->eraseFromParent();
3925  UI->eraseFromParent();
3926 
3927  // Continue in the "user_code" block, see diagram above and in
3928  // openmp/libomptarget/deviceRTLs/common/include/target.h .
3929  return InsertPointTy(UserCodeEntryBB, UserCodeEntryBB->getFirstInsertionPt());
3930 }
3931 
3933  bool IsSPMD,
3934  bool RequiresFullRuntime) {
3935  if (!updateToLocation(Loc))
3936  return;
3937 
3938  uint32_t SrcLocStrSize;
3939  Constant *SrcLocStr = getOrCreateSrcLocStr(Loc, SrcLocStrSize);
3940  Value *Ident = getOrCreateIdent(SrcLocStr, SrcLocStrSize);
3941  ConstantInt *IsSPMDVal = ConstantInt::getSigned(
3942  IntegerType::getInt8Ty(Int8->getContext()),
3944  ConstantInt *RequiresFullRuntimeVal =
3945  ConstantInt::getBool(Int32->getContext(), RequiresFullRuntime);
3946 
3947  Function *Fn = getOrCreateRuntimeFunctionPtr(
3948  omp::RuntimeFunction::OMPRTL___kmpc_target_deinit);
3949 
3950  Builder.CreateCall(Fn, {Ident, IsSPMDVal, RequiresFullRuntimeVal});
3951 }
3952 
3953 void OpenMPIRBuilder::setOutlinedTargetRegionFunctionAttributes(
3954  Function *OutlinedFn, int32_t NumTeams, int32_t NumThreads) {
3955  if (Config.isEmbedded()) {
3957  // TODO: Determine if DSO local can be set to true.
3958  OutlinedFn->setDSOLocal(false);
3960  if (Triple(M.getTargetTriple()).isAMDGCN())
3962  }
3963 
3964  if (NumTeams > 0)
3965  OutlinedFn->addFnAttr("omp_target_num_teams", std::to_string(NumTeams));
3966  if (NumThreads > 0)
3967  OutlinedFn->addFnAttr("omp_target_thread_limit",
3968  std::to_string(NumThreads));
3969 }
3970 
3971 Constant *OpenMPIRBuilder::createOutlinedFunctionID(Function *OutlinedFn,
3972  StringRef EntryFnIDName) {
3973  if (Config.isEmbedded()) {
3974  assert(OutlinedFn && "The outlined function must exist if embedded");
3975  return ConstantExpr::getBitCast(OutlinedFn, Builder.getInt8PtrTy());
3976  }
3977 
3978  return new GlobalVariable(
3979  M, Builder.getInt8Ty(), /*isConstant=*/true, GlobalValue::WeakAnyLinkage,
3980  Constant::getNullValue(Builder.getInt8Ty()), EntryFnIDName);
3981 }
3982 
3983 Constant *OpenMPIRBuilder::createTargetRegionEntryAddr(Function *OutlinedFn,
3984  StringRef EntryFnName) {
3985  if (OutlinedFn)
3986  return OutlinedFn;
3987 
3988  assert(!M.getGlobalVariable(EntryFnName, true) &&
3989  "Named kernel already exists?");
3990  return new GlobalVariable(
3991  M, Builder.getInt8Ty(), /*isConstant=*/true, GlobalValue::InternalLinkage,
3992  Constant::getNullValue(Builder.getInt8Ty()), EntryFnName);
3993 }
3994 
3996  OffloadEntriesInfoManager &InfoManager, TargetRegionEntryInfo &EntryInfo,
3997  Function *OutlinedFn, StringRef EntryFnName, StringRef EntryFnIDName,
3998  int32_t NumTeams, int32_t NumThreads) {
3999  if (OutlinedFn)
4000  setOutlinedTargetRegionFunctionAttributes(OutlinedFn, NumTeams, NumThreads);
4001  auto OutlinedFnID = createOutlinedFunctionID(OutlinedFn, EntryFnIDName);
4002  auto EntryAddr = createTargetRegionEntryAddr(OutlinedFn, EntryFnName);
4003  InfoManager.registerTargetRegionEntryInfo(
4004  EntryInfo, EntryAddr, OutlinedFnID,
4006  return OutlinedFnID;
4007 }
4008 
4009 std::string OpenMPIRBuilder::getNameWithSeparators(ArrayRef<StringRef> Parts,
4010  StringRef FirstSeparator,
4011  StringRef Separator) {
4012  SmallString<128> Buffer;
4013  llvm::raw_svector_ostream OS(Buffer);
4014  StringRef Sep = FirstSeparator;
4015  for (StringRef Part : Parts) {
4016  OS << Sep << Part;
4017  Sep = Separator;
4018  }
4019  return OS.str().str();
4020 }
4021 
4022 std::string
4024  return OpenMPIRBuilder::getNameWithSeparators(Parts, Config.firstSeparator(),
4025  Config.separator());
4026 }
4027 
4030  unsigned AddressSpace) {
4031  auto &Elem = *InternalVars.try_emplace(Name, nullptr).first;
4032  if (Elem.second) {
4033  assert(cast<PointerType>(Elem.second->getType())
4034  ->isOpaqueOrPointeeTypeMatches(Ty) &&
4035  "OMP internal variable has different type than requested");
4036  } else {
4037  // TODO: investigate the appropriate linkage type used for the global
4038  // variable for possibly changing that to internal or private, or maybe
4039  // create different versions of the function for different OMP internal
4040  // variables.
4041  Elem.second = new GlobalVariable(
4042  M, Ty, /*IsConstant=*/false, GlobalValue::CommonLinkage,
4043  Constant::getNullValue(Ty), Elem.first(),
4044  /*InsertBefore=*/nullptr, GlobalValue::NotThreadLocal, AddressSpace);
4045  }
4046 
4047  return cast<GlobalVariable>(&*Elem.second);
4048 }
4049 
4050 Value *OpenMPIRBuilder::getOMPCriticalRegionLock(StringRef CriticalName) {
4051  std::string Prefix = Twine("gomp_critical_user_", CriticalName).str();
4052  std::string Name = getNameWithSeparators({Prefix, "var"}, ".", ".");
4053  return getOrCreateInternalVariable(KmpCriticalNameTy, Name);
4054 }
4055 
4058  std::string VarName) {
4059  llvm::Constant *MaptypesArrayInit =
4060  llvm::ConstantDataArray::get(M.getContext(), Mappings);
4061  auto *MaptypesArrayGlobal = new llvm::GlobalVariable(
4062  M, MaptypesArrayInit->getType(),
4063  /*isConstant=*/true, llvm::GlobalValue::PrivateLinkage, MaptypesArrayInit,
4064  VarName);
4065  MaptypesArrayGlobal->setUnnamedAddr(llvm::GlobalValue::UnnamedAddr::Global);
4066  return MaptypesArrayGlobal;
4067 }
4068 
4070  InsertPointTy AllocaIP,
4071  unsigned NumOperands,
4072  struct MapperAllocas &MapperAllocas) {
4073  if (!updateToLocation(Loc))
4074  return;
4075 
4076  auto *ArrI8PtrTy = ArrayType::get(Int8Ptr, NumOperands);
4077  auto *ArrI64Ty = ArrayType::get(Int64, NumOperands);
4078  Builder.restoreIP(AllocaIP);
4079  AllocaInst *ArgsBase = Builder.CreateAlloca(ArrI8PtrTy);
4080  AllocaInst *Args = Builder.CreateAlloca(ArrI8PtrTy);
4081  AllocaInst *ArgSizes = Builder.CreateAlloca(ArrI64Ty);
4082  Builder.restoreIP(Loc.IP);
4083  MapperAllocas.ArgsBase = ArgsBase;
4085  MapperAllocas.ArgSizes = ArgSizes;
4086 }
4087 
4089  Function *MapperFunc, Value *SrcLocInfo,
4090  Value *MaptypesArg, Value *MapnamesArg,
4091  struct MapperAllocas &MapperAllocas,
4092  int64_t DeviceID, unsigned NumOperands) {
4093  if (!updateToLocation(Loc))
4094  return;
4095 
4096  auto *ArrI8PtrTy = ArrayType::get(Int8Ptr, NumOperands);
4097  auto *ArrI64Ty = ArrayType::get(Int64, NumOperands);
4098  Value *ArgsBaseGEP =
4099  Builder.CreateInBoundsGEP(ArrI8PtrTy, MapperAllocas.ArgsBase,
4100  {Builder.getInt32(0), Builder.getInt32(0)});
4101  Value *ArgsGEP =
4102  Builder.CreateInBoundsGEP(ArrI8PtrTy, MapperAllocas.Args,
4103  {Builder.getInt32(0), Builder.getInt32(0)});
4104  Value *ArgSizesGEP =
4105  Builder.CreateInBoundsGEP(ArrI64Ty, MapperAllocas.ArgSizes,
4106  {Builder.getInt32(0), Builder.getInt32(0)});
4107  Value *NullPtr = Constant::getNullValue(Int8Ptr->getPointerTo());
4108  Builder.CreateCall(MapperFunc,
4109  {SrcLocInfo, Builder.getInt64(DeviceID),
4110  Builder.getInt32(NumOperands), ArgsBaseGEP, ArgsGEP,
4111  ArgSizesGEP, MaptypesArg, MapnamesArg, NullPtr});
4112 }
4113 
4115  TargetDataRTArgs &RTArgs,
4117  bool EmitDebug,
4118  bool ForEndCall) {
4119  assert((!ForEndCall || Info.separateBeginEndCalls()) &&
4120  "expected region end call to runtime only when end call is separate");
4121  auto VoidPtrTy = Type::getInt8PtrTy(M.getContext());
4122  auto VoidPtrPtrTy = VoidPtrTy->getPointerTo(0);
4123  auto Int64Ty = Type::getInt64Ty(M.getContext());
4124  auto Int64PtrTy = Type::getInt64PtrTy(M.getContext());
4125 
4126  if (!Info.NumberOfPtrs) {
4127  RTArgs.BasePointersArray = ConstantPointerNull::get(VoidPtrPtrTy);
4128  RTArgs.PointersArray = ConstantPointerNull::get(VoidPtrPtrTy);
4129  RTArgs.SizesArray = ConstantPointerNull::get(Int64PtrTy);
4130  RTArgs.MapTypesArray = ConstantPointerNull::get(Int64PtrTy);
4131  RTArgs.MapNamesArray = ConstantPointerNull::get(VoidPtrPtrTy);
4132  RTArgs.MappersArray = ConstantPointerNull::get(VoidPtrPtrTy);
4133  return;
4134  }
4135 
4136  RTArgs.BasePointersArray = Builder.CreateConstInBoundsGEP2_32(
4137  ArrayType::get(VoidPtrTy, Info.NumberOfPtrs),
4138  Info.RTArgs.BasePointersArray,
4139  /*Idx0=*/0, /*Idx1=*/0);
4140  RTArgs.PointersArray = Builder.CreateConstInBoundsGEP2_32(
4141  ArrayType::get(VoidPtrTy, Info.NumberOfPtrs), Info.RTArgs.PointersArray,
4142  /*Idx0=*/0,
4143  /*Idx1=*/0);
4144  RTArgs.SizesArray = Builder.CreateConstInBoundsGEP2_32(
4145  ArrayType::get(Int64Ty, Info.NumberOfPtrs), Info.RTArgs.SizesArray,
4146  /*Idx0=*/0, /*Idx1=*/0);
4147  RTArgs.MapTypesArray = Builder.CreateConstInBoundsGEP2_32(
4148  ArrayType::get(Int64Ty, Info.NumberOfPtrs),
4149  ForEndCall && Info.RTArgs.MapTypesArrayEnd ? Info.RTArgs.MapTypesArrayEnd
4150  : Info.RTArgs.MapTypesArray,
4151  /*Idx0=*/0,
4152  /*Idx1=*/0);
4153 
4154  // Only emit the mapper information arrays if debug information is
4155  // requested.
4156  if (!EmitDebug)
4157  RTArgs.MapNamesArray = ConstantPointerNull::get(VoidPtrPtrTy);
4158  else
4159  RTArgs.MapNamesArray = Builder.CreateConstInBoundsGEP2_32(
4160  ArrayType::get(VoidPtrTy, Info.NumberOfPtrs), Info.RTArgs.MapNamesArray,
4161  /*Idx0=*/0,
4162  /*Idx1=*/0);
4163  // If there is no user-defined mapper, set the mapper array to nullptr to
4164  // avoid an unnecessary data privatization
4165  if (!Info.HasMapper)
4166  RTArgs.MappersArray = ConstantPointerNull::get(VoidPtrPtrTy);
4167  else
4168  RTArgs.MappersArray =
4169  Builder.CreatePointerCast(Info.RTArgs.MappersArray, VoidPtrPtrTy);
4170 }
4171 
4172 bool OpenMPIRBuilder::checkAndEmitFlushAfterAtomic(
4173  const LocationDescription &Loc, llvm::AtomicOrdering AO, AtomicKind AK) {
4176  "Unexpected Atomic Ordering.");
4177 
4178  bool Flush = false;
4180 
4181  switch (AK) {
4182  case Read:
4185  FlushAO = AtomicOrdering::Acquire;
4186  Flush = true;
4187  }
4188  break;
4189  case Write:
4190  case Compare:
4191  case Update:
4194  FlushAO = AtomicOrdering::Release;
4195  Flush = true;
4196  }
4197  break;
4198  case Capture:
4199  switch (AO) {
4201  FlushAO = AtomicOrdering::Acquire;
4202  Flush = true;
4203  break;
4205  FlushAO = AtomicOrdering::Release;
4206  Flush = true;
4207  break;
4211  Flush = true;
4212  break;
4213  default:
4214  // do nothing - leave silently.
4215  break;
4216  }
4217  }
4218 
4219  if (Flush) {
4220  // Currently Flush RT call still doesn't take memory_ordering, so for when
4221  // that happens, this tries to do the resolution of which atomic ordering
4222  // to use with but issue the flush call
4223  // TODO: pass `FlushAO` after memory ordering support is added
4224  (void)FlushAO;
4225  emitFlush(Loc);
4226  }
4227 
4228  // for AO == AtomicOrdering::Monotonic and all other case combinations
4229  // do nothing
4230  return Flush;
4231 }
4232 
4236  AtomicOrdering AO) {
4237  if (!updateToLocation(Loc))
4238  return Loc.IP;
4239 
4240  Type *XTy = X.Var->getType();
4241  assert(XTy->isPointerTy() && "OMP Atomic expects a pointer to target memory");
4242  Type *XElemTy = X.ElemTy;
4243  assert((XElemTy->isFloatingPointTy() || XElemTy->isIntegerTy() ||
4244  XElemTy->isPointerTy()) &&
4245  "OMP atomic read expected a scalar type");
4246 
4247  Value *XRead = nullptr;
4248 
4249  if (XElemTy->isIntegerTy()) {
4250  LoadInst *XLD =
4251  Builder.CreateLoad(XElemTy, X.Var, X.IsVolatile, "omp.atomic.read");
4252  XLD->setAtomic(AO);
4253  XRead = cast<Value>(XLD);
4254  } else {
4255  // We need to bitcast and perform atomic op as integer
4256  unsigned Addrspace = cast<PointerType>(XTy)->getAddressSpace();
4257  IntegerType *IntCastTy =
4258  IntegerType::get(M.getContext(), XElemTy->getScalarSizeInBits());
4259  Value *XBCast = Builder.CreateBitCast(
4260  X.Var, IntCastTy->getPointerTo(Addrspace), "atomic.src.int.cast");
4261  LoadInst *XLoad =
4262  Builder.CreateLoad(IntCastTy, XBCast, X.IsVolatile, "omp.atomic.load");
4263  XLoad->setAtomic(AO);
4264  if (XElemTy->isFloatingPointTy()) {
4265  XRead = Builder.CreateBitCast(XLoad, XElemTy, "atomic.flt.cast");
4266  } else {
4267  XRead = Builder.CreateIntToPtr(XLoad, XElemTy, "atomic.ptr.cast");
4268  }
4269  }
4270  checkAndEmitFlushAfterAtomic(Loc, AO, AtomicKind::Read);
4271  Builder.CreateStore(XRead, V.Var, V.IsVolatile);
4272  return Builder.saveIP();
4273 }
4274 
4277  AtomicOpValue &X, Value *Expr,
4278  AtomicOrdering AO) {
4279  if (!updateToLocation(Loc))
4280  return Loc.IP;
4281 
4282  Type *XTy = X.Var->getType();
4283  assert(XTy->isPointerTy() && "OMP Atomic expects a pointer to target memory");
4284  Type *XElemTy = X.ElemTy;
4285  assert((XElemTy->isFloatingPointTy() || XElemTy->isIntegerTy() ||
4286  XElemTy->isPointerTy()) &&
4287  "OMP atomic write expected a scalar type");
4288 
4289  if (XElemTy->isIntegerTy()) {
4290  StoreInst *XSt = Builder.CreateStore(Expr, X.Var, X.IsVolatile);
4291  XSt->setAtomic(AO);
4292  } else {
4293  // We need to bitcast and perform atomic op as integers
4294  unsigned Addrspace = cast<PointerType>(XTy)->getAddressSpace();
4295  IntegerType *IntCastTy =
4296  IntegerType::get(M.getContext(), XElemTy->getScalarSizeInBits());
4297  Value *XBCast = Builder.CreateBitCast(
4298  X.Var, IntCastTy->getPointerTo(Addrspace), "atomic.dst.int.cast");
4299  Value *ExprCast =
4300  Builder.CreateBitCast(Expr, IntCastTy, "atomic.src.int.cast");
4301  StoreInst *XSt = Builder.CreateStore(ExprCast, XBCast, X.IsVolatile);
4302  XSt->setAtomic(AO);
4303  }
4304 
4305  checkAndEmitFlushAfterAtomic(Loc, AO, AtomicKind::Write);
4306  return Builder.saveIP();
4307 }
4308 
4310  const LocationDescription &Loc, InsertPointTy AllocaIP, AtomicOpValue &X,
4311  Value *Expr, AtomicOrdering AO, AtomicRMWInst::BinOp RMWOp,
4312  AtomicUpdateCallbackTy &UpdateOp, bool IsXBinopExpr) {
4313  assert(!isConflictIP(Loc.IP, AllocaIP) && "IPs must not be ambiguous");
4314  if (!updateToLocation(Loc))
4315  return Loc.IP;
4316 
4317  LLVM_DEBUG({
4318  Type *XTy = X.Var->getType();
4319  assert(XTy->isPointerTy() &&
4320  "OMP Atomic expects a pointer to target memory");
4321  Type *XElemTy = X.ElemTy;
4322  assert((XElemTy->isFloatingPointTy() || XElemTy->isIntegerTy() ||
4323  XElemTy->isPointerTy()) &&
4324  "OMP atomic update expected a scalar type");
4325  assert((RMWOp != AtomicRMWInst::Max) && (RMWOp != AtomicRMWInst::Min) &&
4326  (RMWOp != AtomicRMWInst::UMax) && (RMWOp != AtomicRMWInst::UMin) &&
4327  "OpenMP atomic does not support LT or GT operations");
4328  });
4329 
4330  emitAtomicUpdate(AllocaIP, X.Var, X.ElemTy, Expr, AO, RMWOp, UpdateOp,
4331  X.IsVolatile, IsXBinopExpr);
4332  checkAndEmitFlushAfterAtomic(Loc, AO, AtomicKind::Update);
4333  return Builder.saveIP();
4334 }
4335 
4336 Value *OpenMPIRBuilder::emitRMWOpAsInstruction(Value *Src1, Value *Src2,
4337  AtomicRMWInst::BinOp RMWOp) {
4338  switch (RMWOp) {
4339  case AtomicRMWInst::Add:
4340  return Builder.CreateAdd(Src1, Src2);
4341  case AtomicRMWInst::Sub:
4342  return Builder.CreateSub(Src1, Src2);
4343  case AtomicRMWInst::And:
4344  return Builder.CreateAnd(Src1, Src2);
4345  case AtomicRMWInst::Nand:
4346  return Builder.CreateNeg(Builder.CreateAnd(Src1, Src2));
4347  case AtomicRMWInst::Or:
4348  return Builder.CreateOr(Src1, Src2);
4349  case AtomicRMWInst::Xor:
4350  return Builder.CreateXor(Src1, Src2);
4351  case AtomicRMWInst::Xchg:
4352  case AtomicRMWInst::FAdd:
4353  case AtomicRMWInst::FSub:
4355  case AtomicRMWInst::Max:
4356  case AtomicRMWInst::Min:
4357  case AtomicRMWInst::UMax:
4358  case AtomicRMWInst::UMin:
4359  case AtomicRMWInst::FMax:
4360  case AtomicRMWInst::FMin:
4361  llvm_unreachable("Unsupported atomic update operation");
4362  }
4363  llvm_unreachable("Unsupported atomic update operation");
4364 }
4365 
4366 std::pair<Value *, Value *> OpenMPIRBuilder::emitAtomicUpdate(
4367  InsertPointTy AllocaIP, Value *X, Type *XElemTy, Value *Expr,
4369  AtomicUpdateCallbackTy &UpdateOp, bool VolatileX, bool IsXBinopExpr) {
4370  // TODO: handle the case where XElemTy is not byte-sized or not a power of 2
4371  // or a complex datatype.
4372  bool emitRMWOp = false;
4373  switch (RMWOp) {
4374  case AtomicRMWInst::Add:
4375  case AtomicRMWInst::And:
4376  case AtomicRMWInst::Nand:
4377  case AtomicRMWInst::Or:
4378  case AtomicRMWInst::Xor:
4379  case AtomicRMWInst::Xchg:
4380  emitRMWOp = XElemTy;
4381  break;
4382  case AtomicRMWInst::Sub:
4383  emitRMWOp = (IsXBinopExpr && XElemTy);
4384  break;
4385  default:
4386  emitRMWOp = false;
4387  }
4388  emitRMWOp &= XElemTy->isIntegerTy();
4389 
4390  std::pair<Value *, Value *> Res;
4391  if (emitRMWOp) {
4392  Res.first = Builder.CreateAtomicRMW(RMWOp, X, Expr, llvm::MaybeAlign(), AO);
4393  // not needed except in case of postfix captures. Generate anyway for
4394  // consistency with the else part. Will be removed with any DCE pass.
4395  // AtomicRMWInst::Xchg does not have a coressponding instruction.
4396  if (RMWOp == AtomicRMWInst::Xchg)
4397  Res.second = Res.first;
4398  else
4399  Res.second = emitRMWOpAsInstruction(Res.first, Expr, RMWOp);
4400  } else {
4401  unsigned Addrspace = cast<PointerType>(X->getType())->getAddressSpace();
4402  IntegerType *IntCastTy =
4403  IntegerType::get(M.getContext(), XElemTy->getScalarSizeInBits());
4404  Value *XBCast =
4405  Builder.CreateBitCast(X, IntCastTy->getPointerTo(Addrspace));
4406  LoadInst *OldVal =
4407  Builder.CreateLoad(IntCastTy, XBCast, X->getName() + ".atomic.load");
4408  OldVal->setAtomic(AO);
4409  // CurBB
4410  // | /---\
4411  // ContBB |
4412  // | \---/
4413  // ExitBB
4414  BasicBlock *CurBB = Builder.GetInsertBlock();
4415  Instruction *CurBBTI = CurBB->getTerminator();
4416  CurBBTI = CurBBTI ? CurBBTI : Builder.CreateUnreachable();
4417  BasicBlock *ExitBB =
4418  CurBB->splitBasicBlock(CurBBTI, X->getName() + ".atomic.exit");
4419  BasicBlock *ContBB = CurBB->splitBasicBlock(CurBB->getTerminator(),
4420  X->getName() + ".atomic.cont");
4421  ContBB->getTerminator()->eraseFromParent();
4422  Builder.restoreIP(AllocaIP);
4423  AllocaInst *NewAtomicAddr = Builder.CreateAlloca(XElemTy);
4424  NewAtomicAddr->setName(X->getName() + "x.new.val");
4425  Builder.SetInsertPoint(ContBB);
4426  llvm::PHINode *PHI = Builder.CreatePHI(OldVal->getType(), 2);
4427  PHI->addIncoming(OldVal, CurBB);
4428  IntegerType *NewAtomicCastTy =
4429  IntegerType::get(M.getContext(), XElemTy->getScalarSizeInBits());
4430  bool IsIntTy = XElemTy->isIntegerTy();
4431  Value *NewAtomicIntAddr =
4432  (IsIntTy)
4433  ? NewAtomicAddr
4434  : Builder.CreateBitCast(NewAtomicAddr,
4435  NewAtomicCastTy->getPointerTo(Addrspace));
4436  Value *OldExprVal = PHI;
4437  if (!IsIntTy) {
4438  if (XElemTy->isFloatingPointTy()) {
4439  OldExprVal = Builder.CreateBitCast(PHI, XElemTy,
4440  X->getName() + ".atomic.fltCast");
4441  } else {
4442  OldExprVal = Builder.CreateIntToPtr(PHI, XElemTy,
4443  X->getName() + ".atomic.ptrCast");
4444  }
4445  }
4446 
4447  Value *Upd = UpdateOp(OldExprVal, Builder);
4448  Builder.CreateStore(Upd, NewAtomicAddr);
4449  LoadInst *DesiredVal = Builder.CreateLoad(IntCastTy, NewAtomicIntAddr);
4450  Value *XAddr =
4451  (IsIntTy)
4452  ? X
4453  : Builder.CreateBitCast(X, IntCastTy->getPointerTo(Addrspace));
4456  AtomicCmpXchgInst *Result = Builder.CreateAtomicCmpXchg(
4457  XAddr, PHI, DesiredVal, llvm::MaybeAlign(), AO, Failure);
4458  Result->setVolatile(VolatileX);
4459  Value *PreviousVal = Builder.CreateExtractValue(Result, /*Idxs=*/0);
4460  Value *SuccessFailureVal = Builder.CreateExtractValue(Result, /*Idxs=*/1);
4461  PHI->addIncoming(PreviousVal, Builder.GetInsertBlock());
4462  Builder.CreateCondBr(SuccessFailureVal, ExitBB, ContBB);
4463 
4464  Res.first = OldExprVal;
4465  Res.second = Upd;
4466 
4467  // set Insertion point in exit block
4468  if (UnreachableInst *ExitTI =
4469  dyn_cast<UnreachableInst>(ExitBB->getTerminator())) {
4470  CurBBTI->eraseFromParent();
4471  Builder.SetInsertPoint(ExitBB);
4472  } else {
4473  Builder.SetInsertPoint(ExitTI);
4474  }
4475  }
4476 
4477  return Res;
4478 }
4479 
4481  const LocationDescription &Loc, InsertPointTy AllocaIP, AtomicOpValue &X,
4482  AtomicOpValue &V, Value *Expr, AtomicOrdering AO,
4484  bool UpdateExpr, bool IsPostfixUpdate, bool IsXBinopExpr) {
4485  if (!updateToLocation(Loc))
4486  return Loc.IP;
4487 
4488  LLVM_DEBUG({
4489  Type *XTy = X.Var->getType();
4490  assert(XTy->isPointerTy() &&
4491  "OMP Atomic expects a pointer to target memory");
4492  Type *XElemTy = X.ElemTy;
4493  assert((XElemTy->isFloatingPointTy() || XElemTy->isIntegerTy() ||
4494  XElemTy->isPointerTy()) &&
4495  "OMP atomic capture expected a scalar type");
4496  assert((RMWOp != AtomicRMWInst::Max) && (RMWOp != AtomicRMWInst::Min) &&
4497  "OpenMP atomic does not support LT or GT operations");
4498  });
4499 
4500  // If UpdateExpr is 'x' updated with some `expr` not based on 'x',
4501  // 'x' is simply atomically rewritten with 'expr'.
4502  AtomicRMWInst::BinOp AtomicOp = (UpdateExpr ? RMWOp : AtomicRMWInst::Xchg);
4503  std::pair<Value *, Value *> Result =
4504  emitAtomicUpdate(AllocaIP, X.Var, X.ElemTy, Expr, AO, AtomicOp, UpdateOp,
4505  X.IsVolatile, IsXBinopExpr);
4506 
4507  Value *CapturedVal = (IsPostfixUpdate ? Result.first : Result.second);
4508  Builder.CreateStore(CapturedVal, V.Var, V.IsVolatile);
4509 
4510  checkAndEmitFlushAfterAtomic(Loc, AO, AtomicKind::Capture);
4511  return Builder.saveIP();
4512 }
4513 
4517  omp::OMPAtomicCompareOp Op, bool IsXBinopExpr, bool IsPostfixUpdate,
4518  bool IsFailOnly) {
4519 
4520  if (!updateToLocation(Loc))
4521  return Loc.IP;
4522 
4523  assert(X.Var->getType()->isPointerTy() &&
4524  "OMP atomic expects a pointer to target memory");
4525  // compare capture
4526  if (V.Var) {
4527  assert(V.Var->getType()->isPointerTy() && "v.var must be of pointer type");
4528  assert(V.ElemTy == X.ElemTy && "x and v must be of same type");
4529  }
4530 
4531  bool IsInteger = E->getType()->isIntegerTy();
4532 
4533  if (Op == OMPAtomicCompareOp::EQ) {
4535  AtomicCmpXchgInst *Result = nullptr;
4536  if (!IsInteger) {
4537  unsigned Addrspace =
4538  cast<PointerType>(X.Var->getType())->getAddressSpace();
4539  IntegerType *IntCastTy =
4540  IntegerType::get(M.getContext(), X.ElemTy->getScalarSizeInBits());
4541  Value *XBCast =
4542  Builder.CreateBitCast(X.Var, IntCastTy->getPointerTo(Addrspace));
4543  Value *EBCast = Builder.CreateBitCast(E, IntCastTy);
4544  Value *DBCast = Builder.CreateBitCast(D, IntCastTy);
4545  Result = Builder.CreateAtomicCmpXchg(XBCast, EBCast, DBCast, MaybeAlign(),
4546  AO, Failure);
4547  } else {
4548  Result =
4549  Builder.CreateAtomicCmpXchg(X.Var, E, D, MaybeAlign(), AO, Failure);
4550  }
4551 
4552  if (V.Var) {
4553  Value *OldValue = Builder.CreateExtractValue(Result, /*Idxs=*/0);
4554  if (!IsInteger)
4555  OldValue = Builder.CreateBitCast(OldValue, X.ElemTy);
4556  assert(OldValue->getType() == V.ElemTy &&
4557  "OldValue and V must be of same type");
4558  if (IsPostfixUpdate) {
4559  Builder.CreateStore(OldValue, V.Var, V.IsVolatile);
4560  } else {
4561  Value *SuccessOrFail = Builder.CreateExtractValue(Result, /*Idxs=*/1);
4562  if (IsFailOnly) {
4563  // CurBB----
4564  // | |
4565  // v |
4566  // ContBB |
4567  // | |
4568  // v |
4569  // ExitBB <-
4570  //
4571  // where ContBB only contains the store of old value to 'v'.
4572  BasicBlock *CurBB = Builder.GetInsertBlock();
4573  Instruction *CurBBTI = CurBB->getTerminator();
4574  CurBBTI = CurBBTI ? CurBBTI : Builder.CreateUnreachable();
4575  BasicBlock *ExitBB = CurBB->splitBasicBlock(
4576  CurBBTI, X.Var->getName() + ".atomic.exit");
4577  BasicBlock *ContBB = CurBB->splitBasicBlock(
4578  CurBB->getTerminator(), X.Var->getName() + ".atomic.cont");
4579  ContBB->getTerminator()->eraseFromParent();
4580  CurBB->getTerminator()->eraseFromParent();
4581 
4582  Builder.CreateCondBr(SuccessOrFail, ExitBB, ContBB);
4583 
4584  Builder.SetInsertPoint(ContBB);
4585  Builder.CreateStore(OldValue, V.Var);
4586  Builder.CreateBr(ExitBB);
4587 
4588  if (UnreachableInst *ExitTI =
4589  dyn_cast<UnreachableInst>(ExitBB->getTerminator())) {
4590  CurBBTI->eraseFromParent();
4591  Builder.SetInsertPoint(ExitBB);
4592  } else {
4593  Builder.SetInsertPoint(ExitTI);
4594  }
4595  } else {
4596  Value *CapturedValue =
4597  Builder.CreateSelect(SuccessOrFail, E, OldValue);
4598  Builder.CreateStore(CapturedValue, V.Var, V.IsVolatile);
4599  }
4600  }
4601  }
4602  // The comparison result has to be stored.
4603  if (R.Var) {
4604  assert(R.Var->getType()->isPointerTy() &&
4605  "r.var must be of pointer type");
4606  assert(R.ElemTy->isIntegerTy() && "r must be of integral type");
4607 
4608  Value *SuccessFailureVal = Builder.CreateExtractValue(Result, /*Idxs=*/1);
4609  Value *ResultCast = R.IsSigned
4610  ? Builder.CreateSExt(SuccessFailureVal, R.ElemTy)
4611  : Builder.CreateZExt(SuccessFailureVal, R.ElemTy);
4612  Builder.CreateStore(ResultCast, R.Var, R.IsVolatile);
4613  }
4614  } else {
4616  "Op should be either max or min at this point");
4617  assert(!IsFailOnly && "IsFailOnly is only valid when the comparison is ==");
4618 
4619  // Reverse the ordop as the OpenMP forms are different from LLVM forms.
4620  // Let's take max as example.
4621  // OpenMP form:
4622  // x = x > expr ? expr : x;
4623  // LLVM form:
4624  // *ptr = *ptr > val ? *ptr : val;
4625  // We need to transform to LLVM form.
4626  // x = x <= expr ? x : expr;
4627  AtomicRMWInst::BinOp NewOp;
4628  if (IsXBinopExpr) {
4629  if (IsInteger) {
4630  if (X.IsSigned)
4633  else
4636  } else {
4639  }
4640  } else {
4641  if (IsInteger) {
4642  if (X.IsSigned)
4645  else
4648  } else {
4651  }
4652  }
4653 
4654  AtomicRMWInst *OldValue =
4655  Builder.CreateAtomicRMW(NewOp, X.Var, E, MaybeAlign(), AO);
4656  if (V.Var) {
4657  Value *CapturedValue = nullptr;
4658  if (IsPostfixUpdate) {
4659  CapturedValue = OldValue;
4660  } else {
4661  CmpInst::Predicate Pred;
4662  switch (NewOp) {
4663  case AtomicRMWInst::Max:
4664  Pred = CmpInst::ICMP_SGT;
4665  break;
4666  case AtomicRMWInst::UMax:
4667  Pred = CmpInst::ICMP_UGT;
4668  break;
4669  case AtomicRMWInst::FMax:
4670  Pred = CmpInst::FCMP_OGT;
4671  break;
4672  case AtomicRMWInst::Min:
4673  Pred = CmpInst::ICMP_SLT;
4674  break;
4675  case AtomicRMWInst::UMin:
4676  Pred = CmpInst::ICMP_ULT;
4677  break;
4678  case AtomicRMWInst::FMin:
4679  Pred = CmpInst::FCMP_OLT;
4680  break;
4681  default:
4682  llvm_unreachable("unexpected comparison op");
4683  }
4684  Value *NonAtomicCmp = Builder.CreateCmp(Pred, OldValue, E);
4685  CapturedValue = Builder.CreateSelect(NonAtomicCmp, E, OldValue);
4686  }
4687  Builder.CreateStore(CapturedValue, V.Var, V.IsVolatile);
4688  }
4689  }
4690 
4691  checkAndEmitFlushAfterAtomic(Loc, AO, AtomicKind::Compare);
4692 
4693  return Builder.saveIP();
4694 }
4695 
4698  std::string VarName) {
4699  llvm::Constant *MapNamesArrayInit = llvm::ConstantArray::get(
4701  llvm::Type::getInt8Ty(M.getContext())->getPointerTo(), Names.size()),
4702  Names);
4703  auto *MapNamesArrayGlobal = new llvm::GlobalVariable(
4704  M, MapNamesArrayInit->getType(),
4705  /*isConstant=*/true, llvm::GlobalValue::PrivateLinkage, MapNamesArrayInit,
4706  VarName);
4707  return MapNamesArrayGlobal;
4708 }
4709 
4710 // Create all simple and struct types exposed by the runtime and remember
4711 // the llvm::PointerTypes of them for easy access later.
4712 void OpenMPIRBuilder::initializeTypes(Module &M) {
4713  LLVMContext &Ctx = M.getContext();
4714  StructType *T;
4715 #define OMP_TYPE(VarName, InitValue) VarName = InitValue;
4716 #define OMP_ARRAY_TYPE(VarName, ElemTy, ArraySize) \
4717  VarName##Ty = ArrayType::get(ElemTy, ArraySize); \
4718  VarName##PtrTy = PointerType::getUnqual(VarName##Ty);
4719 #define OMP_FUNCTION_TYPE(VarName, IsVarArg, ReturnType, ...) \
4720  VarName = FunctionType::get(ReturnType, {__VA_ARGS__}, IsVarArg); \
4721  VarName##Ptr = PointerType::getUnqual(VarName);
4722 #define OMP_STRUCT_TYPE(VarName, StructName, ...) \
4723  T = StructType::getTypeByName(Ctx, StructName); \
4724  if (!T) \
4725  T = StructType::create(Ctx, {__VA_ARGS__}, StructName); \
4726  VarName = T; \
4727  VarName##Ptr = PointerType::getUnqual(T);
4728 #include "llvm/Frontend/OpenMP/OMPKinds.def"
4729 }
4730 
4733  SmallVectorImpl<BasicBlock *> &BlockVector) {
4735  BlockSet.insert(EntryBB);
4736  BlockSet.insert(ExitBB);
4737 
4738  Worklist.push_back(EntryBB);
4739  while (!Worklist.empty()) {
4740  BasicBlock *BB = Worklist.pop_back_val();
4741  BlockVector.push_back(BB);
4742  for (BasicBlock *SuccBB : successors(BB))
4743  if (BlockSet.insert(SuccBB).second)
4744  Worklist.push_back(SuccBB);
4745  }
4746 }
4747 
4749  uint64_t Size, int32_t Flags,
4751  if (!Config.isTargetCodegen()) {
4752  emitOffloadingEntry(ID, Addr->getName(), Size, Flags);
4753  return;
4754  }
4755  // TODO: Add support for global variables on the device after declare target
4756  // support.
4757  Function *Fn = dyn_cast<Function>(Addr);
4758  if (!Fn)
4759  return;
4760 
4761  Module &M = *(Fn->getParent());
4762  LLVMContext &Ctx = M.getContext();
4763 
4764  // Get "nvvm.annotations" metadata node.
4765  NamedMDNode *MD = M.getOrInsertNamedMetadata("nvvm.annotations");
4766 
4767  Metadata *MDVals[] = {
4768  ConstantAsMetadata::get(Fn), MDString::get(Ctx, "kernel"),
4770  // Append metadata to nvvm.annotations.
4771  MD->addOperand(MDNode::get(Ctx, MDVals));
4772 
4773  // Add a function attribute for the kernel.
4774  Fn->addFnAttr(Attribute::get(Ctx, "kernel"));
4775 }
4776 
4777 // We only generate metadata for function that contain target regions.
4781 
4782  // If there are no entries, we don't need to do anything.
4784  return;
4785 
4786  LLVMContext &C = M.getContext();
4789  16>
4790  OrderedEntries(OffloadEntriesInfoManager.size());
4791 
4792  // Auxiliary methods to create metadata values and strings.
4793  auto &&GetMDInt = [this](unsigned V) {
4794  return ConstantAsMetadata::get(ConstantInt::get(Builder.getInt32Ty(), V));
4795  };
4796 
4797  auto &&GetMDString = [&C](StringRef V) { return MDString::get(C, V); };
4798 
4799  // Create the offloading info metadata node.
4800  NamedMDNode *MD = M.getOrInsertNamedMetadata("omp_offload.info");
4801  auto &&TargetRegionMetadataEmitter =
4802  [&C, MD, &OrderedEntries, &GetMDInt, &GetMDString](
4803  const TargetRegionEntryInfo &EntryInfo,
4805  // Generate metadata for target regions. Each entry of this metadata
4806  // contains:
4807  // - Entry 0 -> Kind of this type of metadata (0).
4808  // - Entry 1 -> Device ID of the file where the entry was identified.
4809  // - Entry 2 -> File ID of the file where the entry was identified.
4810  // - Entry 3 -> Mangled name of the function where the entry was
4811  // identified.
4812  // - Entry 4 -> Line in the file where the entry was identified.
4813  // - Entry 5 -> Count of regions at this DeviceID/FilesID/Line.
4814  // - Entry 6 -> Order the entry was created.
4815  // The first element of the metadata node is the kind.
4816  Metadata *Ops[] = {
4817  GetMDInt(E.getKind()), GetMDInt(EntryInfo.DeviceID),
4818  GetMDInt(EntryInfo.FileID), GetMDString(EntryInfo.ParentName),
4819  GetMDInt(EntryInfo.Line), GetMDInt(EntryInfo.Count),
4820  GetMDInt(E.getOrder())};
4821 
4822  // Save this entry in the right position of the ordered entries array.
4823  OrderedEntries[E.getOrder()] = std::make_pair(&E, EntryInfo);
4824 
4825  // Add metadata to the named metadata node.
4826  MD->addOperand(MDNode::get(C, Ops));
4827  };
4828 
4830  TargetRegionMetadataEmitter);
4831 
4832  // Create function that emits metadata for each device global variable entry;
4833  auto &&DeviceGlobalVarMetadataEmitter =
4834  [&C, &OrderedEntries, &GetMDInt, &GetMDString, MD](
4835  StringRef MangledName,
4837  // Generate metadata for global variables. Each entry of this metadata
4838  // contains:
4839  // - Entry 0 -> Kind of this type of metadata (1).
4840  // - Entry 1 -> Mangled name of the variable.
4841  // - Entry 2 -> Declare target kind.
4842  // - Entry 3 -> Order the entry was created.
4843  // The first element of the metadata node is the kind.
4844  Metadata *Ops[] = {GetMDInt(E.getKind()), GetMDString(MangledName),
4845  GetMDInt(E.getFlags()), GetMDInt(E.getOrder())};
4846 
4847  // Save this entry in the right position of the ordered entries array.
4848  TargetRegionEntryInfo varInfo(MangledName, 0, 0, 0);
4849  OrderedEntries[E.getOrder()] = std::make_pair(&E, varInfo);
4850 
4851  // Add metadata to the named metadata node.
4852  MD->addOperand(MDNode::get(C, Ops));
4853  };
4854 
4856  DeviceGlobalVarMetadataEmitter);
4857 
4858  for (const auto &E : OrderedEntries) {
4859  assert(E.first && "All ordered entries must exist!");
4860  if (const auto *CE =
4861  dyn_cast<OffloadEntriesInfoManager::OffloadEntryInfoTargetRegion>(
4862  E.first)) {
4863  if (!CE->getID() || !CE->getAddress()) {
4864  // Do not blame the entry if the parent funtion is not emitted.
4865  TargetRegionEntryInfo EntryInfo = E.second;
4866  StringRef FnName = EntryInfo.ParentName;
4867  if (!M.getNamedValue(FnName))
4868  continue;
4869  ErrorFn(EMIT_MD_TARGET_REGION_ERROR, EntryInfo);
4870  continue;
4871  }
4872  createOffloadEntry(CE->getID(), CE->getAddress(),
4873  /*Size=*/0, CE->getFlags(),
4875  } else if (const auto *CE = dyn_cast<
4877  E.first)) {
4880  CE->getFlags());
4881  switch (Flags) {
4883  if (Config.isEmbedded() && Config.hasRequiresUnifiedSharedMemory())
4884  continue;
4885  if (!CE->getAddress()) {
4886  ErrorFn(EMIT_MD_DECLARE_TARGET_ERROR, E.second);
4887  continue;
4888  }
4889  // The vaiable has no definition - no need to add the entry.
4890  if (CE->getVarSize() == 0)
4891  continue;
4892  break;
4893  }
4895  assert(((Config.isEmbedded() && !CE->getAddress()) ||
4896  (!Config.isEmbedded() && CE->getAddress())) &&
4897  "Declaret target link address is set.");
4898  if (Config.isEmbedded())
4899  continue;
4900  if (!CE->getAddress()) {
4901  ErrorFn(EMIT_MD_GLOBAL_VAR_LINK_ERROR, TargetRegionEntryInfo());
4902  continue;
4903  }
4904  break;
4905  }
4906 
4907  // Hidden or internal symbols on the device are not externally visible.
4908  // We should not attempt to register them by creating an offloading
4909  // entry.
4910  if (auto *GV = dyn_cast<GlobalValue>(CE->getAddress()))
4911  if (GV->hasLocalLinkage() || GV->hasHiddenVisibility())
4912  continue;
4913 
4914  createOffloadEntry(CE->getAddress(), CE->getAddress(), CE->getVarSize(),
4915  Flags, CE->getLinkage());
4916 
4917  } else {
4918  llvm_unreachable("Unsupported entry kind.");
4919  }
4920  }
4921 }
4922 
4924  SmallVectorImpl<char> &Name, StringRef ParentName, unsigned DeviceID,
4925  unsigned FileID, unsigned Line, unsigned Count) {
4926  raw_svector_ostream OS(Name);
4927  OS << "__omp_offloading" << llvm::format("_%x", DeviceID)
4928  << llvm::format("_%x_", FileID) << ParentName << "_l" << Line;
4929  if (Count)
4930  OS << "_" << Count;
4931 }
4932 
4934  SmallVectorImpl<char> &Name, const TargetRegionEntryInfo &EntryInfo) {
4935  unsigned NewCount = getTargetRegionEntryInfoCount(EntryInfo);
4937  Name, EntryInfo.ParentName, EntryInfo.DeviceID, EntryInfo.FileID,
4938  EntryInfo.Line, NewCount);
4939 }
4940 
4941 /// Loads all the offload entries information from the host IR
4942 /// metadata.
4945  // If we are in target mode, load the metadata from the host IR. This code has
4946  // to match the metadata creation in createOffloadEntriesAndInfoMetadata().
4947 
4948  NamedMDNode *MD = M.getNamedMetadata(ompOffloadInfoName);
4949  if (!MD)
4950  return;
4951 
4952  for (MDNode *MN : MD->operands()) {
4953  auto &&GetMDInt = [MN](unsigned Idx) {
4954  auto *V = cast<ConstantAsMetadata>(MN->getOperand(Idx));
4955  return cast<ConstantInt>(V->getValue())->getZExtValue();
4956  };
4957 
4958  auto &&GetMDString = [MN](unsigned Idx) {
4959  auto *V = cast<MDString>(MN->getOperand(Idx));
4960  return V->getString();
4961  };
4962 
4963  switch (GetMDInt(0)) {
4964  default:
4965  llvm_unreachable("Unexpected metadata!");
4966  break;
4969  TargetRegionEntryInfo EntryInfo(/*ParentName=*/GetMDString(3),
4970  /*DeviceID=*/GetMDInt(1),
4971  /*FileID=*/GetMDInt(2),
4972  /*Line=*/GetMDInt(4),
4973  /*Count=*/GetMDInt(5));
4975  EntryInfo, /*Order=*/GetMDInt(6));
4976  break;
4977  }
4981  /*MangledName=*/GetMDString(1),
4982  static_cast<