Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- IR/OpenMPIRBuilder.h - OpenMP encoding builder for LLVM IR - C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

// This file defines the OpenMPIRBuilder class and helpers used as a convenient

// way to create LLVM instructions for OpenMP directives.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_FRONTEND_OPENMP_OMPIRBUILDER_H

#define LLVM_FRONTEND_OPENMP_OMPIRBUILDER_H

#include "llvm/Analysis/MemorySSAUpdater.h"

#include "llvm/Frontend/OpenMP/OMPConstants.h"

#include "llvm/IR/DebugLoc.h"

#include "llvm/IR/IRBuilder.h"

#include "llvm/Support/Allocator.h"

#include <forward_list>

#include <map>

#include <optional>

namespace llvm {

class CanonicalLoopInfo;

struct TargetRegionEntryInfo;

class OffloadEntriesInfoManager;

/// Move the instruction after an InsertPoint to the beginning of another

/// BasicBlock.

///

/// The instructions after \p IP are moved to the beginning of \p New which must

/// not have any PHINodes. If \p CreateBranch is true, a branch instruction to

/// \p New will be added such that there is no semantic change. Otherwise, the

/// \p IP insert block remains degenerate and it is up to the caller to insert a

/// terminator.

void spliceBB(IRBuilderBase::InsertPoint IP, BasicBlock *New,

              bool CreateBranch);

/// Splice a BasicBlock at an IRBuilder's current insertion point. Its new

/// insert location will stick to after the instruction before the insertion

/// point (instead of moving with the instruction the InsertPoint stores

/// internally).

void spliceBB(IRBuilder<> &Builder, BasicBlock *New, bool CreateBranch);

/// Split a BasicBlock at an InsertPoint, even if the block is degenerate

/// (missing the terminator).

///

/// llvm::SplitBasicBlock and BasicBlock::splitBasicBlock require a well-formed

/// BasicBlock. \p Name is used for the new successor block. If \p CreateBranch

/// is true, a branch to the new successor will new created such that

/// semantically there is no change; otherwise the block of the insertion point

/// remains degenerate and it is the caller's responsibility to insert a

/// terminator. Returns the new successor block.

BasicBlock *splitBB(IRBuilderBase::InsertPoint IP, bool CreateBranch,

                    llvm::Twine Name = {});

/// Split a BasicBlock at \p Builder's insertion point, even if the block is

/// degenerate (missing the terminator).  Its new insert location will stick to

/// after the instruction before the insertion point (instead of moving with the

/// instruction the InsertPoint stores internally).

BasicBlock *splitBB(IRBuilderBase &Builder, bool CreateBranch,

                    llvm::Twine Name = {});

/// Split a BasicBlock at \p Builder's insertion point, even if the block is

/// degenerate (missing the terminator).  Its new insert location will stick to

/// after the instruction before the insertion point (instead of moving with the

/// instruction the InsertPoint stores internally).

BasicBlock *splitBB(IRBuilder<> &Builder, bool CreateBranch, llvm::Twine Name);

/// Like splitBB, but reuses the current block's name for the new name.

BasicBlock *splitBBWithSuffix(IRBuilderBase &Builder, bool CreateBranch,

                              llvm::Twine Suffix = ".split");

/// Captures attributes that affect generating LLVM-IR using the

/// OpenMPIRBuilder and related classes. Note that not all attributes are

/// required for all classes or functions. In some use cases the configuration

/// is not necessary at all, because because the only functions that are called

/// are ones that are not dependent on the configuration.

class OpenMPIRBuilderConfig {

public:

  /// Flag for specifying if the compilation is done for embedded device code

  /// or host code.

  std::optional<bool> IsEmbedded;

  /// Flag for specifying if the compilation is done for an offloading target,

  /// like GPU.

  std::optional<bool> IsTargetCodegen;

  /// Flag for specifying weather a requires unified_shared_memory

  /// directive is present or not.

  std::optional<bool> HasRequiresUnifiedSharedMemory;

  // Flag for specifying if offloading is mandatory.

  std::optional<bool> OpenMPOffloadMandatory;

  /// First separator used between the initial two parts of a name.

  std::optional<StringRef> FirstSeparator;

  /// Separator used between all of the rest consecutive parts of s name

  std::optional<StringRef> Separator;

  OpenMPIRBuilderConfig() {}

  OpenMPIRBuilderConfig(bool IsEmbedded, bool IsTargetCodegen,

                        bool HasRequiresUnifiedSharedMemory,

                        bool OpenMPOffloadMandatory)

      : IsEmbedded(IsEmbedded), IsTargetCodegen(IsTargetCodegen),

        HasRequiresUnifiedSharedMemory(HasRequiresUnifiedSharedMemory),

        OpenMPOffloadMandatory(OpenMPOffloadMandatory) {}

  // Getters functions that assert if the required values are not present.

  bool isEmbedded() const {

    assert(IsEmbedded.has_value() && "IsEmbedded is not set");

    return *IsEmbedded;

  }

  bool isTargetCodegen() const {

    assert(IsTargetCodegen.has_value() && "IsTargetCodegen is not set");

    return *IsTargetCodegen;

  }

  bool hasRequiresUnifiedSharedMemory() const {

    assert(HasRequiresUnifiedSharedMemory.has_value() &&

           "HasUnifiedSharedMemory is not set");

    return *HasRequiresUnifiedSharedMemory;

  }

  bool openMPOffloadMandatory() const {

    assert(OpenMPOffloadMandatory.has_value() &&

           "OpenMPOffloadMandatory is not set");

    return *OpenMPOffloadMandatory;

  }

  // Returns the FirstSeparator if set, otherwise use the default

  // separator depending on isTargetCodegen

  StringRef firstSeparator() const {

    if (FirstSeparator.has_value())

      return *FirstSeparator;

    if (isTargetCodegen())

      return "_";

    return ".";

  }

  // Returns the Separator if set, otherwise use the default

  // separator depending on isTargetCodegen

  StringRef separator() const {

    if (Separator.has_value())

      return *Separator;

    if (isTargetCodegen())

      return "$";

    return ".";

  }

  void setIsEmbedded(bool Value) { IsEmbedded = Value; }

  void setIsTargetCodegen(bool Value) { IsTargetCodegen = Value; }

  void setHasRequiresUnifiedSharedMemory(bool Value) {

    HasRequiresUnifiedSharedMemory = Value;

  }

  void setFirstSeparator(StringRef FS) { FirstSeparator = FS; }

  void setSeparator(StringRef S) { Separator = S; }

};

/// An interface to create LLVM-IR for OpenMP directives.

///

/// Each OpenMP directive has a corresponding public generator method.

class OpenMPIRBuilder {

public:

  /// Create a new OpenMPIRBuilder operating on the given module \p M. This will

  /// not have an effect on \p M (see initialize)

  OpenMPIRBuilder(Module &M) : M(M), Builder(M.getContext()) {}

  ~OpenMPIRBuilder();

  /// Initialize the internal state, this will put structures types and

  /// potentially other helpers into the underlying module. Must be called

  /// before any other method and only once!

  void initialize();

  void setConfig(OpenMPIRBuilderConfig C) { Config = C; }

  /// Finalize the underlying module, e.g., by outlining regions.

  /// \param Fn                    The function to be finalized. If not used,

  ///                              all functions are finalized.

  void finalize(Function *Fn = nullptr);

  /// Add attributes known for \p FnID to \p Fn.

  void addAttributes(omp::RuntimeFunction FnID, Function &Fn);

  /// Type used throughout for insertion points.

  using InsertPointTy = IRBuilder<>::InsertPoint;

  /// Get the create a name using the platform specific separators.

  /// \param Parts parts of the final name that needs separation

  /// The created name has a first separator between the first and second part

  /// and a second separator between all other parts.

  /// E.g. with FirstSeparator "$" and Separator "." and

  /// parts: "p1", "p2", "p3", "p4"

  /// The resulting name is "p1$p2.p3.p4"

  /// The separators are retrieved from the OpenMPIRBuilderConfig.

  std::string createPlatformSpecificName(ArrayRef<StringRef> Parts) const;

  /// Callback type for variable finalization (think destructors).

  ///

  /// \param CodeGenIP is the insertion point at which the finalization code

  ///                  should be placed.

  ///

  /// A finalize callback knows about all objects that need finalization, e.g.

  /// destruction, when the scope of the currently generated construct is left

  /// at the time, and location, the callback is invoked.

  using FinalizeCallbackTy = std::function<void(InsertPointTy CodeGenIP)>;

  struct FinalizationInfo {

    /// The finalization callback provided by the last in-flight invocation of

    /// createXXXX for the directive of kind DK.

    FinalizeCallbackTy FiniCB;

    /// The directive kind of the innermost directive that has an associated

    /// region which might require finalization when it is left.

    omp::Directive DK;

    /// Flag to indicate if the directive is cancellable.

    bool IsCancellable;

  };

  /// Push a finalization callback on the finalization stack.

  ///

  /// NOTE: Temporary solution until Clang CG is gone.

  void pushFinalizationCB(const FinalizationInfo &FI) {

    FinalizationStack.push_back(FI);

  }

  /// Pop the last finalization callback from the finalization stack.

  ///

  /// NOTE: Temporary solution until Clang CG is gone.

  void popFinalizationCB() { FinalizationStack.pop_back(); }

  /// Callback type for body (=inner region) code generation

  ///

  /// The callback takes code locations as arguments, each describing a

  /// location where additional instructions can be inserted.

  ///

  /// The CodeGenIP may be in the middle of a basic block or point to the end of

  /// it. The basic block may have a terminator or be degenerate. The callback

  /// function may just insert instructions at that position, but also split the

  /// block (without the Before argument of BasicBlock::splitBasicBlock such

  /// that the identify of the split predecessor block is preserved) and insert

  /// additional control flow, including branches that do not lead back to what

  /// follows the CodeGenIP. Note that since the callback is allowed to split

  /// the block, callers must assume that InsertPoints to positions in the

  /// BasicBlock after CodeGenIP including CodeGenIP itself are invalidated. If

  /// such InsertPoints need to be preserved, it can split the block itself

  /// before calling the callback.

  ///

  /// AllocaIP and CodeGenIP must not point to the same position.

  ///

  /// \param AllocaIP is the insertion point at which new alloca instructions

  ///                 should be placed. The BasicBlock it is pointing to must

  ///                 not be split.

  /// \param CodeGenIP is the insertion point at which the body code should be

  ///                  placed.

  using BodyGenCallbackTy =

      function_ref<void(InsertPointTy AllocaIP, InsertPointTy CodeGenIP)>;

  // This is created primarily for sections construct as llvm::function_ref

  // (BodyGenCallbackTy) is not storable (as described in the comments of

  // function_ref class - function_ref contains non-ownable reference

  // to the callable.

  using StorableBodyGenCallbackTy =

      std::function<void(InsertPointTy AllocaIP, InsertPointTy CodeGenIP)>;

  /// Callback type for loop body code generation.

  ///

  /// \param CodeGenIP is the insertion point where the loop's body code must be

  ///                  placed. This will be a dedicated BasicBlock with a

  ///                  conditional branch from the loop condition check and

  ///                  terminated with an unconditional branch to the loop

  ///                  latch.

  /// \param IndVar    is the induction variable usable at the insertion point.

  using LoopBodyGenCallbackTy =

      function_ref<void(InsertPointTy CodeGenIP, Value *IndVar)>;

  /// Callback type for variable privatization (think copy & default

  /// constructor).

  ///

  /// \param AllocaIP is the insertion point at which new alloca instructions

  ///                 should be placed.

  /// \param CodeGenIP is the insertion point at which the privatization code

  ///                  should be placed.

  /// \param Original The value being copied/created, should not be used in the

  ///                 generated IR.

  /// \param Inner The equivalent of \p Original that should be used in the

  ///              generated IR; this is equal to \p Original if the value is

  ///              a pointer and can thus be passed directly, otherwise it is

  ///              an equivalent but different value.

  /// \param ReplVal The replacement value, thus a copy or new created version

  ///                of \p Inner.

  ///

  /// \returns The new insertion point where code generation continues and

  ///          \p ReplVal the replacement value.

  using PrivatizeCallbackTy = function_ref<InsertPointTy(

      InsertPointTy AllocaIP, InsertPointTy CodeGenIP, Value &Original,

      Value &Inner, Value *&ReplVal)>;

  /// Description of a LLVM-IR insertion point (IP) and a debug/source location

  /// (filename, line, column, ...).

  struct LocationDescription {

    LocationDescription(const IRBuilderBase &IRB)

        : IP(IRB.saveIP()), DL(IRB.getCurrentDebugLocation()) {}

    LocationDescription(const InsertPointTy &IP) : IP(IP) {}

    LocationDescription(const InsertPointTy &IP, const DebugLoc &DL)

        : IP(IP), DL(DL) {}

    InsertPointTy IP;

    DebugLoc DL;

  };

  /// Emitter methods for OpenMP directives.

  ///

  ///{

  /// Generator for '#omp barrier'

  ///

  /// \param Loc The location where the barrier directive was encountered.

  /// \param DK The kind of directive that caused the barrier.

  /// \param ForceSimpleCall Flag to force a simple (=non-cancellation) barrier.

  /// \param CheckCancelFlag Flag to indicate a cancel barrier return value

  ///                        should be checked and acted upon.

  ///

  /// \returns The insertion point after the barrier.

  InsertPointTy createBarrier(const LocationDescription &Loc, omp::Directive DK,

                              bool ForceSimpleCall = false,

                              bool CheckCancelFlag = true);

  /// Generator for '#omp cancel'

  ///

  /// \param Loc The location where the directive was encountered.

  /// \param IfCondition The evaluated 'if' clause expression, if any.

  /// \param CanceledDirective The kind of directive that is cancled.

  ///

  /// \returns The insertion point after the barrier.

  InsertPointTy createCancel(const LocationDescription &Loc, Value *IfCondition,

                             omp::Directive CanceledDirective);

  /// Generator for '#omp parallel'

  ///

  /// \param Loc The insert and source location description.

  /// \param AllocaIP The insertion points to be used for alloca instructions.

  /// \param BodyGenCB Callback that will generate the region code.

  /// \param PrivCB Callback to copy a given variable (think copy constructor).

  /// \param FiniCB Callback to finalize variable copies.

  /// \param IfCondition The evaluated 'if' clause expression, if any.

  /// \param NumThreads The evaluated 'num_threads' clause expression, if any.

  /// \param ProcBind The value of the 'proc_bind' clause (see ProcBindKind).

  /// \param IsCancellable Flag to indicate a cancellable parallel region.

  ///

  /// \returns The insertion position *after* the parallel.

  IRBuilder<>::InsertPoint

  createParallel(const LocationDescription &Loc, InsertPointTy AllocaIP,

                 BodyGenCallbackTy BodyGenCB, PrivatizeCallbackTy PrivCB,

                 FinalizeCallbackTy FiniCB, Value *IfCondition,

                 Value *NumThreads, omp::ProcBindKind ProcBind,

                 bool IsCancellable);

  /// Generator for the control flow structure of an OpenMP canonical loop.

  ///

  /// This generator operates on the logical iteration space of the loop, i.e.

  /// the caller only has to provide a loop trip count of the loop as defined by

  /// base language semantics. The trip count is interpreted as an unsigned

  /// integer. The induction variable passed to \p BodyGenCB will be of the same

  /// type and run from 0 to \p TripCount - 1. It is up to the callback to

  /// convert the logical iteration variable to the loop counter variable in the

  /// loop body.

  ///

  /// \param Loc       The insert and source location description. The insert

  ///                  location can be between two instructions or the end of a

  ///                  degenerate block (e.g. a BB under construction).

  /// \param BodyGenCB Callback that will generate the loop body code.

  /// \param TripCount Number of iterations the loop body is executed.

  /// \param Name      Base name used to derive BB and instruction names.

  ///

  /// \returns An object representing the created control flow structure which

  ///          can be used for loop-associated directives.

  CanonicalLoopInfo *createCanonicalLoop(const LocationDescription &Loc,

                                         LoopBodyGenCallbackTy BodyGenCB,

                                         Value *TripCount,

                                         const Twine &Name = "loop");

  /// Generator for the control flow structure of an OpenMP canonical loop.

  ///

  /// Instead of a logical iteration space, this allows specifying user-defined

  /// loop counter values using increment, upper- and lower bounds. To

  /// disambiguate the terminology when counting downwards, instead of lower

  /// bounds we use \p Start for the loop counter value in the first body

  /// iteration.

  ///

  /// Consider the following limitations:

  ///

  ///  * A loop counter space over all integer values of its bit-width cannot be

  ///    represented. E.g using uint8_t, its loop trip count of 256 cannot be

  ///    stored into an 8 bit integer):

  ///

  ///      DO I = 0, 255, 1

  ///

  ///  * Unsigned wrapping is only supported when wrapping only "once"; E.g.

  ///    effectively counting downwards:

  ///

  ///      for (uint8_t i = 100u; i > 0; i += 127u)

  ///

  ///

  /// TODO: May need to add additional parameters to represent:

  ///

  ///  * Allow representing downcounting with unsigned integers.

  ///

  ///  * Sign of the step and the comparison operator might disagree:

  ///

  ///      for (int i = 0; i < 42; i -= 1u)

  ///

  //

  /// \param Loc       The insert and source location description.

  /// \param BodyGenCB Callback that will generate the loop body code.

  /// \param Start     Value of the loop counter for the first iterations.

  /// \param Stop      Loop counter values past this will stop the loop.

  /// \param Step      Loop counter increment after each iteration; negative

  ///                  means counting down.

  /// \param IsSigned  Whether Start, Stop and Step are signed integers.

  /// \param InclusiveStop Whether \p Stop itself is a valid value for the loop

  ///                      counter.

  /// \param ComputeIP Insertion point for instructions computing the trip

  ///                  count. Can be used to ensure the trip count is available

  ///                  at the outermost loop of a loop nest. If not set,

  ///                  defaults to the preheader of the generated loop.

  /// \param Name      Base name used to derive BB and instruction names.

  ///

  /// \returns An object representing the created control flow structure which

  ///          can be used for loop-associated directives.

  CanonicalLoopInfo *createCanonicalLoop(const LocationDescription &Loc,

                                         LoopBodyGenCallbackTy BodyGenCB,

                                         Value *Start, Value *Stop, Value *Step,

                                         bool IsSigned, bool InclusiveStop,

                                         InsertPointTy ComputeIP = {},

                                         const Twine &Name = "loop");

  /// Collapse a loop nest into a single loop.

  ///

  /// Merges loops of a loop nest into a single CanonicalLoopNest representation

  /// that has the same number of innermost loop iterations as the origin loop

  /// nest. The induction variables of the input loops are derived from the

  /// collapsed loop's induction variable. This is intended to be used to

  /// implement OpenMP's collapse clause. Before applying a directive,

  /// collapseLoops normalizes a loop nest to contain only a single loop and the

  /// directive's implementation does not need to handle multiple loops itself.

  /// This does not remove the need to handle all loop nest handling by

  /// directives, such as the ordered(<n>) clause or the simd schedule-clause

  /// modifier of the worksharing-loop directive.

  ///

  /// Example:

  /// \code

  ///   for (int i = 0; i < 7; ++i) // Canonical loop "i"

  ///     for (int j = 0; j < 9; ++j) // Canonical loop "j"

  ///       body(i, j);

  /// \endcode

  ///

  /// After collapsing with Loops={i,j}, the loop is changed to

  /// \code

  ///   for (int ij = 0; ij < 63; ++ij) {

  ///     int i = ij / 9;

  ///     int j = ij % 9;

  ///     body(i, j);

  ///   }

  /// \endcode

  ///

  /// In the current implementation, the following limitations apply:

  ///

  ///  * All input loops have an induction variable of the same type.

  ///

  ///  * The collapsed loop will have the same trip count integer type as the

  ///    input loops. Therefore it is possible that the collapsed loop cannot

  ///    represent all iterations of the input loops. For instance, assuming a

  ///    32 bit integer type, and two input loops both iterating 2^16 times, the

  ///    theoretical trip count of the collapsed loop would be 2^32 iteration,

  ///    which cannot be represented in an 32-bit integer. Behavior is undefined

  ///    in this case.

  ///

  ///  * The trip counts of every input loop must be available at \p ComputeIP.

  ///    Non-rectangular loops are not yet supported.

  ///

  ///  * At each nest level, code between a surrounding loop and its nested loop

  ///    is hoisted into the loop body, and such code will be executed more

  ///    often than before collapsing (or not at all if any inner loop iteration

  ///    has a trip count of 0). This is permitted by the OpenMP specification.

  ///

  /// \param DL        Debug location for instructions added for collapsing,

  ///                  such as instructions to compute/derive the input loop's

  ///                  induction variables.

  /// \param Loops     Loops in the loop nest to collapse. Loops are specified

  ///                  from outermost-to-innermost and every control flow of a

  ///                  loop's body must pass through its directly nested loop.

  /// \param ComputeIP Where additional instruction that compute the collapsed

  ///                  trip count. If not set, defaults to before the generated

  ///                  loop.

  ///

  /// \returns The CanonicalLoopInfo object representing the collapsed loop.

  CanonicalLoopInfo *collapseLoops(DebugLoc DL,

                                   ArrayRef<CanonicalLoopInfo *> Loops,

                                   InsertPointTy ComputeIP);

private:

  /// Modifies the canonical loop to be a statically-scheduled workshare loop.

  ///

  /// This takes a \p LoopInfo representing a canonical loop, such as the one

  /// created by \p createCanonicalLoop and emits additional instructions to

  /// turn it into a workshare loop. In particular, it calls to an OpenMP

  /// runtime function in the preheader to obtain the loop bounds to be used in

  /// the current thread, updates the relevant instructions in the canonical

  /// loop and calls to an OpenMP runtime finalization function after the loop.

  ///

  /// \param DL       Debug location for instructions added for the

  ///                 workshare-loop construct itself.

  /// \param CLI      A descriptor of the canonical loop to workshare.

  /// \param AllocaIP An insertion point for Alloca instructions usable in the

  ///                 preheader of the loop.

  /// \param NeedsBarrier Indicates whether a barrier must be inserted after

  ///                     the loop.

  ///

  /// \returns Point where to insert code after the workshare construct.

  InsertPointTy applyStaticWorkshareLoop(DebugLoc DL, CanonicalLoopInfo *CLI,

                                         InsertPointTy AllocaIP,

                                         bool NeedsBarrier);

  /// Modifies the canonical loop a statically-scheduled workshare loop with a

  /// user-specified chunk size.

  ///

  /// \param DL           Debug location for instructions added for the

  ///                     workshare-loop construct itself.

  /// \param CLI          A descriptor of the canonical loop to workshare.

  /// \param AllocaIP     An insertion point for Alloca instructions usable in

  ///                     the preheader of the loop.

  /// \param NeedsBarrier Indicates whether a barrier must be inserted after the

  ///                     loop.

  /// \param ChunkSize    The user-specified chunk size.

  ///

  /// \returns Point where to insert code after the workshare construct.

  InsertPointTy applyStaticChunkedWorkshareLoop(DebugLoc DL,

                                                CanonicalLoopInfo *CLI,

                                                InsertPointTy AllocaIP,

                                                bool NeedsBarrier,

                                                Value *ChunkSize);

  /// Modifies the canonical loop to be a dynamically-scheduled workshare loop.

  ///

  /// This takes a \p LoopInfo representing a canonical loop, such as the one

  /// created by \p createCanonicalLoop and emits additional instructions to

  /// turn it into a workshare loop. In particular, it calls to an OpenMP

  /// runtime function in the preheader to obtain, and then in each iteration

  /// to update the loop counter.

  ///

  /// \param DL       Debug location for instructions added for the

  ///                 workshare-loop construct itself.

  /// \param CLI      A descriptor of the canonical loop to workshare.

  /// \param AllocaIP An insertion point for Alloca instructions usable in the

  ///                 preheader of the loop.

  /// \param SchedType Type of scheduling to be passed to the init function.

  /// \param NeedsBarrier Indicates whether a barrier must be insterted after

  ///                     the loop.

  /// \param Chunk    The size of loop chunk considered as a unit when

  ///                 scheduling. If \p nullptr, defaults to 1.

  ///

  /// \returns Point where to insert code after the workshare construct.

  InsertPointTy applyDynamicWorkshareLoop(DebugLoc DL, CanonicalLoopInfo *CLI,

                                          InsertPointTy AllocaIP,

                                          omp::OMPScheduleType SchedType,

                                          bool NeedsBarrier,

                                          Value *Chunk = nullptr);

  /// Create alternative version of the loop to support if clause

  ///

  /// OpenMP if clause can require to generate second loop. This loop

  /// will be executed when if clause condition is not met. createIfVersion

  /// adds branch instruction to the copied loop if \p  ifCond is not met.

  ///

  /// \param Loop       Original loop which should be versioned.

  /// \param IfCond     Value which corresponds to if clause condition

  /// \param VMap       Value to value map to define relation between

  ///                   original and copied loop values and loop blocks.

  /// \param NamePrefix Optional name prefix for if.then if.else blocks.

  void createIfVersion(CanonicalLoopInfo *Loop, Value *IfCond,

                       ValueToValueMapTy &VMap, const Twine &NamePrefix = "");

public:

  /// Modifies the canonical loop to be a workshare loop.

  ///

  /// This takes a \p LoopInfo representing a canonical loop, such as the one

  /// created by \p createCanonicalLoop and emits additional instructions to

  /// turn it into a workshare loop. In particular, it calls to an OpenMP

  /// runtime function in the preheader to obtain the loop bounds to be used in

  /// the current thread, updates the relevant instructions in the canonical

  /// loop and calls to an OpenMP runtime finalization function after the loop.

  ///

  /// The concrete transformation is done by applyStaticWorkshareLoop,

  /// applyStaticChunkedWorkshareLoop, or applyDynamicWorkshareLoop, depending

  /// on the value of \p SchedKind and \p ChunkSize.

  ///

  /// \param DL       Debug location for instructions added for the

  ///                 workshare-loop construct itself.

  /// \param CLI      A descriptor of the canonical loop to workshare.

  /// \param AllocaIP An insertion point for Alloca instructions usable in the

  ///                 preheader of the loop.

  /// \param NeedsBarrier Indicates whether a barrier must be insterted after

  ///                     the loop.

  /// \param SchedKind Scheduling algorithm to use.

  /// \param ChunkSize The chunk size for the inner loop.

  /// \param HasSimdModifier Whether the simd modifier is present in the

  ///                        schedule clause.

  /// \param HasMonotonicModifier Whether the monotonic modifier is present in

  ///                             the schedule clause.

  /// \param HasNonmonotonicModifier Whether the nonmonotonic modifier is

  ///                                present in the schedule clause.

  /// \param HasOrderedClause Whether the (parameterless) ordered clause is

  ///                         present.

  ///

  /// \returns Point where to insert code after the workshare construct.

  InsertPointTy applyWorkshareLoop(

      DebugLoc DL, CanonicalLoopInfo *CLI, InsertPointTy AllocaIP,

      bool NeedsBarrier,

      llvm::omp::ScheduleKind SchedKind = llvm::omp::OMP_SCHEDULE_Default,

      Value *ChunkSize = nullptr, bool HasSimdModifier = false,

      bool HasMonotonicModifier = false, bool HasNonmonotonicModifier = false,

      bool HasOrderedClause = false);

  /// Tile a loop nest.

  ///

  /// Tiles the loops of \p Loops by the tile sizes in \p TileSizes. Loops in

  /// \p/ Loops must be perfectly nested, from outermost to innermost loop

  /// (i.e. Loops.front() is the outermost loop). The trip count llvm::Value

  /// of every loop and every tile sizes must be usable in the outermost

  /// loop's preheader. This implies that the loop nest is rectangular.

  ///

  /// Example:

  /// \code

  ///   for (int i = 0; i < 15; ++i) // Canonical loop "i"

  ///     for (int j = 0; j < 14; ++j) // Canonical loop "j"

  ///         body(i, j);

  /// \endcode

  ///

  /// After tiling with Loops={i,j} and TileSizes={5,7}, the loop is changed to

  /// \code

  ///   for (int i1 = 0; i1 < 3; ++i1)

  ///     for (int j1 = 0; j1 < 2; ++j1)

  ///       for (int i2 = 0; i2 < 5; ++i2)

  ///         for (int j2 = 0; j2 < 7; ++j2)

  ///           body(i1*3+i2, j1*3+j2);

  /// \endcode

  ///

  /// The returned vector are the loops {i1,j1,i2,j2}. The loops i1 and j1 are

  /// referred to the floor, and the loops i2 and j2 are the tiles. Tiling also

  /// handles non-constant trip counts, non-constant tile sizes and trip counts

  /// that are not multiples of the tile size. In the latter case the tile loop

  /// of the last floor-loop iteration will have fewer iterations than specified

  /// as its tile size.

  ///

  ///

  /// @param DL        Debug location for instructions added by tiling, for

  ///                  instance the floor- and tile trip count computation.

  /// @param Loops     Loops to tile. The CanonicalLoopInfo objects are

  ///                  invalidated by this method, i.e. should not used after

  ///                  tiling.

  /// @param TileSizes For each loop in \p Loops, the tile size for that

  ///                  dimensions.

  ///

  /// \returns A list of generated loops. Contains twice as many loops as the

  ///          input loop nest; the first half are the floor loops and the

  ///          second half are the tile loops.

  std::vector<CanonicalLoopInfo *>

  tileLoops(DebugLoc DL, ArrayRef<CanonicalLoopInfo *> Loops,

            ArrayRef<Value *> TileSizes);

  /// Fully unroll a loop.

  ///

  /// Instead of unrolling the loop immediately (and duplicating its body

  /// instructions), it is deferred to LLVM's LoopUnrollPass by adding loop

  /// metadata.

  ///

  /// \param DL   Debug location for instructions added by unrolling.

  /// \param Loop The loop to unroll. The loop will be invalidated.

  void unrollLoopFull(DebugLoc DL, CanonicalLoopInfo *Loop);

  /// Fully or partially unroll a loop. How the loop is unrolled is determined

  /// using LLVM's LoopUnrollPass.

  ///

  /// \param DL   Debug location for instructions added by unrolling.

  /// \param Loop The loop to unroll. The loop will be invalidated.

  void unrollLoopHeuristic(DebugLoc DL, CanonicalLoopInfo *Loop);

  /// Partially unroll a loop.

  ///

  /// The CanonicalLoopInfo of the unrolled loop for use with chained

  /// loop-associated directive can be requested using \p UnrolledCLI. Not

  /// needing the CanonicalLoopInfo allows more efficient code generation by

  /// deferring the actual unrolling to the LoopUnrollPass using loop metadata.

  /// A loop-associated directive applied to the unrolled loop needs to know the

  /// new trip count which means that if using a heuristically determined unroll

  /// factor (\p Factor == 0), that factor must be computed immediately. We are

  /// using the same logic as the LoopUnrollPass to derived the unroll factor,

  /// but which assumes that some canonicalization has taken place (e.g.

  /// Mem2Reg, LICM, GVN, Inlining, etc.). That is, the heuristic will perform

  /// better when the unrolled loop's CanonicalLoopInfo is not needed.

  ///

  /// \param DL          Debug location for instructions added by unrolling.

  /// \param Loop        The loop to unroll. The loop will be invalidated.

  /// \param Factor      The factor to unroll the loop by. A factor of 0

  ///                    indicates that a heuristic should be used to determine

  ///                    the unroll-factor.

  /// \param UnrolledCLI If non-null, receives the CanonicalLoopInfo of the

  ///                    partially unrolled loop. Otherwise, uses loop metadata

  ///                    to defer unrolling to the LoopUnrollPass.

  void unrollLoopPartial(DebugLoc DL, CanonicalLoopInfo *Loop, int32_t Factor,

                         CanonicalLoopInfo **UnrolledCLI);

  /// Add metadata to simd-ize a loop. If IfCond is not nullptr, the loop

  /// is cloned. The metadata which prevents vectorization is added to

  /// to the cloned loop. The cloned loop is executed when ifCond is evaluated

  /// to false.

  ///

  /// \param Loop        The loop to simd-ize.

  /// \param AlignedVars The map which containts pairs of the pointer

  ///                    and its corresponding alignment.

  /// \param IfCond      The value which corresponds to the if clause

  ///                    condition.

  /// \param Order       The enum to map order clause.

  /// \param Simdlen     The Simdlen length to apply to the simd loop.

  /// \param Safelen     The Safelen length to apply to the simd loop.

  void applySimd(CanonicalLoopInfo *Loop,

                 MapVector<Value *, Value *> AlignedVars, Value *IfCond,

                 omp::OrderKind Order, ConstantInt *Simdlen,

                 ConstantInt *Safelen);

  /// Generator for '#omp flush'

  ///

  /// \param Loc The location where the flush directive was encountered

  void createFlush(const LocationDescription &Loc);

  /// Generator for '#omp taskwait'

  ///

  /// \param Loc The location where the taskwait directive was encountered.

  void createTaskwait(const LocationDescription &Loc);

  /// Generator for '#omp taskyield'

  ///

  /// \param Loc The location where the taskyield directive was encountered.

  void createTaskyield(const LocationDescription &Loc);

  /// A struct to pack the relevant information for an OpenMP depend clause.

  struct DependData {

    omp::RTLDependenceKindTy DepKind = omp::RTLDependenceKindTy::DepUnknown;

    Type *DepValueType;

    Value *DepVal;

    explicit DependData() = default;

    DependData(omp::RTLDependenceKindTy DepKind, Type *DepValueType,

               Value *DepVal)

        : DepKind(DepKind), DepValueType(DepValueType), DepVal(DepVal) {}

  };

  /// Generator for `#omp task`

  ///

  /// \param Loc The location where the task construct was encountered.

  /// \param AllocaIP The insertion point to be used for alloca instructions.

  /// \param BodyGenCB Callback that will generate the region code.

  /// \param Tied True if the task is tied, false if the task is untied.

  /// \param Final i1 value which is `true` if the task is final, `false` if the

  ///              task is not final.

  /// \param IfCondition i1 value. If it evaluates to `false`, an undeferred

  ///                    task is generated, and the encountering thread must

  ///                    suspend the current task region, for which execution

  ///                    cannot be resumed until execution of the structured

  ///                    block that is associated with the generated task is

  ///                    completed.

  InsertPointTy createTask(const LocationDescription &Loc,

                           InsertPointTy AllocaIP, BodyGenCallbackTy BodyGenCB,

                           bool Tied = true, Value *Final = nullptr,

                           Value *IfCondition = nullptr,

                           SmallVector<DependData> Dependencies = {});

  /// Generator for the taskgroup construct

  ///

  /// \param Loc The location where the taskgroup construct was encountered.

  /// \param AllocaIP The insertion point to be used for alloca instructions.

  /// \param BodyGenCB Callback that will generate the region code.

  InsertPointTy createTaskgroup(const LocationDescription &Loc,

                                InsertPointTy AllocaIP,

                                BodyGenCallbackTy BodyGenCB);

  /// Functions used to generate reductions. Such functions take two Values

  /// representing LHS and RHS of the reduction, respectively, and a reference

  /// to the value that is updated to refer to the reduction result.

  using ReductionGenTy =

      function_ref<InsertPointTy(InsertPointTy, Value *, Value *, Value *&)>;

  /// Functions used to generate atomic reductions. Such functions take two

  /// Values representing pointers to LHS and RHS of the reduction, as well as

  /// the element type of these pointers. They are expected to atomically

  /// update the LHS to the reduced value.

  using AtomicReductionGenTy =

      function_ref<InsertPointTy(InsertPointTy, Type *, Value *, Value *)>;

  /// Information about an OpenMP reduction.

  struct ReductionInfo {

    ReductionInfo(Type *ElementType, Value *Variable, Value *PrivateVariable,

                  ReductionGenTy ReductionGen,

                  AtomicReductionGenTy AtomicReductionGen)

        : ElementType(ElementType), Variable(Variable),

          PrivateVariable(PrivateVariable), ReductionGen(ReductionGen),

          AtomicReductionGen(AtomicReductionGen) {

      assert(cast<PointerType>(Variable->getType())

          ->isOpaqueOrPointeeTypeMatches(ElementType) && "Invalid elem type");

    }

    /// Reduction element type, must match pointee type of variable.

    Type *ElementType;

    /// Reduction variable of pointer type.

    Value *Variable;

    /// Thread-private partial reduction variable.

    Value *PrivateVariable;

    /// Callback for generating the reduction body. The IR produced by this will

    /// be used to combine two values in a thread-safe context, e.g., under

    /// lock or within the same thread, and therefore need not be atomic.

    ReductionGenTy ReductionGen;

    /// Callback for generating the atomic reduction body, may be null. The IR

    /// produced by this will be used to atomically combine two values during

    /// reduction. If null, the implementation will use the non-atomic version

    /// along with the appropriate synchronization mechanisms.

    AtomicReductionGenTy AtomicReductionGen;

  };

  // TODO: provide atomic and non-atomic reduction generators for reduction

  // operators defined by the OpenMP specification.

  /// Generator for '#omp reduction'.

  ///

  /// Emits the IR instructing the runtime to perform the specific kind of

  /// reductions. Expects reduction variables to have been privatized and

  /// initialized to reduction-neutral values separately. Emits the calls to

  /// runtime functions as well as the reduction function and the basic blocks

  /// performing the reduction atomically and non-atomically.

  ///

  /// The code emitted for the following:

  ///

  /// \code

  ///   type var_1;

  ///   type var_2;

  ///   #pragma omp <directive> reduction(reduction-op:var_1,var_2)

  ///   /* body */;

  /// \endcode

  ///

  /// corresponds to the following sketch.

  ///

  /// \code

  /// void _outlined_par() {

  ///   // N is the number of different reductions.

  ///   void *red_array[] = {privatized_var_1, privatized_var_2, ...};

  ///   switch(__kmpc_reduce(..., N, /*size of data in red array*/, red_array,

  ///                        _omp_reduction_func,

  ///                        _gomp_critical_user.reduction.var)) {

  ///   case 1: {

  ///     var_1 = var_1 <reduction-op> privatized_var_1;

  ///     var_2 = var_2 <reduction-op> privatized_var_2;

  ///     // ...

  ///    __kmpc_end_reduce(...);

  ///     break;

  ///   }

  ///   case 2: {

  ///     _Atomic<ReductionOp>(var_1, privatized_var_1);

  ///     _Atomic<ReductionOp>(var_2, privatized_var_2);

  ///     // ...

  ///     break;

  ///   }

  ///   default: break;

  ///   }

  /// }

  ///

  /// void _omp_reduction_func(void **lhs, void **rhs) {

  ///   *(type *)lhs[0] = *(type *)lhs[0] <reduction-op> *(type *)rhs[0];

  ///   *(type *)lhs[1] = *(type *)lhs[1] <reduction-op> *(type *)rhs[1];

  ///   // ...

  /// }

  /// \endcode

  ///

  /// \param Loc                The location where the reduction was

  ///                           encountered. Must be within the associate

  ///                           directive and after the last local access to the

  ///                           reduction variables.

  /// \param AllocaIP           An insertion point suitable for allocas usable

  ///                           in reductions.

  /// \param ReductionInfos     A list of info on each reduction variable.

  /// \param IsNoWait           A flag set if the reduction is marked as nowait.

  InsertPointTy createReductions(const LocationDescription &Loc,

                                 InsertPointTy AllocaIP,

                                 ArrayRef<ReductionInfo> ReductionInfos,

                                 bool IsNoWait = false);

  ///}

  /// Return the insertion point used by the underlying IRBuilder.

  InsertPointTy getInsertionPoint() { return Builder.saveIP(); }

  /// Update the internal location to \p Loc.

  bool updateToLocation(const LocationDescription &Loc) {

    Builder.restoreIP(Loc.IP);

    Builder.SetCurrentDebugLocation(Loc.DL);

    return Loc.IP.getBlock() != nullptr;

  }

  /// Return the function declaration for the runtime function with \p FnID.

  FunctionCallee getOrCreateRuntimeFunction(Module &M,

                                            omp::RuntimeFunction FnID);

  Function *getOrCreateRuntimeFunctionPtr(omp::RuntimeFunction FnID);

  /// Return the (LLVM-IR) string describing the source location \p LocStr.