Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

 

 

 

namespace polly {

using llvm::AnalysisInfoMixin;

using llvm::ArrayRef;

using llvm::AssertingVH;

using llvm::AssumptionCache;

using llvm::cast;

using llvm::DataLayout;

using llvm::DenseMap;

using llvm::DenseSet;

using llvm::function_ref;

using llvm::isa;

using llvm::iterator_range;

using llvm::LoadInst;

using llvm::make_range;

using llvm::MapVector;

using llvm::MemIntrinsic;

using llvm::PassInfoMixin;

using llvm::PHINode;

using llvm::RegionNode;

using llvm::RegionPass;

using llvm::RGPassManager;

using llvm::SetVector;

using llvm::SmallPtrSetImpl;

using llvm::SmallVector;

using llvm::SmallVectorImpl;

using llvm::StringMap;

using llvm::Type;

using llvm::Use;

using llvm::Value;

using llvm::ValueToValueMap;

 

class MemoryAccess;

 

 

extern bool UseInstructionNames;

 

extern unsigned const MaxDisjunctsInDomain;

 

enum class MemoryKind {

  /// MemoryKind::Array: Models a one or multi-dimensional array

  ///

  /// A memory object that can be described by a multi-dimensional array.

  /// Memory objects of this type are used to model actual multi-dimensional

  /// arrays as they exist in LLVM-IR, but they are also used to describe

  /// other objects:

  ///   - A single data element allocated on the stack using 'alloca' is

  ///     modeled as a one-dimensional, single-element array.

  ///   - A single data element allocated as a global variable is modeled as

  ///     one-dimensional, single-element array.

  ///   - Certain multi-dimensional arrays with variable size, which in

  ///     LLVM-IR are commonly expressed as a single-dimensional access with a

  ///     complicated access function, are modeled as multi-dimensional

  ///     memory objects (grep for "delinearization").

  Array,

 

  /// MemoryKind::Value: Models an llvm::Value

  ///

  /// Memory objects of type MemoryKind::Value are used to model the data flow

  /// induced by llvm::Values. For each llvm::Value that is used across

  /// BasicBlocks, one ScopArrayInfo object is created. A single memory WRITE

  /// stores the llvm::Value at its definition into the memory object and at

  /// each use of the llvm::Value (ignoring trivial intra-block uses) a

  /// corresponding READ is added. For instance, the use/def chain of a

  /// llvm::Value %V depicted below

  ///              ______________________

  ///              |DefBB:              |

  ///              |  %V = float op ... |

  ///              ----------------------

  ///               |                  |

  /// _________________               _________________

  /// |UseBB1:        |               |UseBB2:        |

  /// |  use float %V |               |  use float %V |

  /// -----------------               -----------------

  ///

  /// is modeled as if the following memory accesses occurred:

  ///

  ///                        __________________________

  ///                        |entry:                  |

  ///                        |  %V.s2a = alloca float |

  ///                        --------------------------

  ///                                     |

  ///                    ___________________________________

  ///                    |DefBB:                           |

  ///                    |  store %float %V, float* %V.s2a |

  ///                    -----------------------------------

  ///                           |                   |

  /// ____________________________________ ___________________________________

  /// |UseBB1:                           | |UseBB2:                          |

  /// |  %V.reload1 = load float* %V.s2a | |  %V.reload2 = load float* %V.s2a|

  /// |  use float %V.reload1            | |  use float %V.reload2           |

  /// ------------------------------------ -----------------------------------

  ///

  Value,

 

  /// MemoryKind::PHI: Models PHI nodes within the SCoP

  ///

  /// Besides the MemoryKind::Value memory object used to model the normal

  /// llvm::Value dependences described above, PHI nodes require an additional

  /// memory object of type MemoryKind::PHI to describe the forwarding of values

  /// to

  /// the PHI node.

  ///

  /// As an example, a PHIInst instructions

  ///

  /// %PHI = phi float [ %Val1, %IncomingBlock1 ], [ %Val2, %IncomingBlock2 ]

  ///

  /// is modeled as if the accesses occurred this way:

  ///

  ///                    _______________________________

  ///                    |entry:                       |

  ///                    |  %PHI.phiops = alloca float |

  ///                    -------------------------------

  ///                           |              |

  /// __________________________________  __________________________________

  /// |IncomingBlock1:                 |  |IncomingBlock2:                 |

  /// |  ...                           |  |  ...                           |

  /// |  store float %Val1 %PHI.phiops |  |  store float %Val2 %PHI.phiops |

  /// |  br label % JoinBlock          |  |  br label %JoinBlock           |

  /// ----------------------------------  ----------------------------------

  ///                             \            /

  ///                              \          /

  ///               _________________________________________

  ///               |JoinBlock:                             |

  ///               |  %PHI = load float, float* PHI.phiops |

  ///               -----------------------------------------

  ///

  /// Note that there can also be a scalar write access for %PHI if used in a

  /// different BasicBlock, i.e. there can be a memory object %PHI.phiops as

  /// well as a memory object %PHI.s2a.

  PHI,

 

  /// MemoryKind::ExitPHI: Models PHI nodes in the SCoP's exit block

  ///

  /// For PHI nodes in the Scop's exit block a special memory object kind is

  /// used. The modeling used is identical to MemoryKind::PHI, with the

  /// exception

  /// that there are no READs from these memory objects. The PHINode's

  /// llvm::Value is treated as a value escaping the SCoP. WRITE accesses

  /// write directly to the escaping value's ".s2a" alloca.

  ExitPHI

 

using LoopBoundMapType = std::map<const Loop *, const SCEV *>;

 

using AccFuncVector = std::vector<std::unique_ptr<MemoryAccess>>;

 

class ScopArrayInfo final {

  /// Construct a ScopArrayInfo object.

  ///

  /// @param BasePtr        The array base pointer.

  /// @param ElementType    The type of the elements stored in the array.

  /// @param IslCtx         The isl context used to create the base pointer id.

  /// @param DimensionSizes A vector containing the size of each dimension.

  /// @param Kind           The kind of the array object.

  /// @param DL             The data layout of the module.

  /// @param S              The scop this array object belongs to.

  /// @param BaseName       The optional name of this memory reference.

  ScopArrayInfo(Value *BasePtr, Type *ElementType, isl::ctx IslCtx,

                ArrayRef<const SCEV *> DimensionSizes, MemoryKind Kind,

                const DataLayout &DL, Scop *S, const char *BaseName = nullptr);

 

  /// Destructor to free the isl id of the base pointer.

  ~ScopArrayInfo();

 

  ///  Update the element type of the ScopArrayInfo object.

  ///

  ///  Memory accesses referencing this ScopArrayInfo object may use

  ///  different element sizes. This function ensures the canonical element type

  ///  stored is small enough to model accesses to the current element type as

  ///  well as to @p NewElementType.

  ///

  ///  @param NewElementType An element type that is used to access this array.

  void updateElementType(Type *NewElementType);

 

  ///  Update the sizes of the ScopArrayInfo object.

  ///

  ///  A ScopArrayInfo object may be created without all outer dimensions being

  ///  available. This function is called when new memory accesses are added for

  ///  this ScopArrayInfo object. It verifies that sizes are compatible and adds

  ///  additional outer array dimensions, if needed.

  ///

  ///  @param Sizes       A vector of array sizes where the rightmost array

  ///                     sizes need to match the innermost array sizes already

  ///                     defined in SAI.

  ///  @param CheckConsistency Update sizes, even if new sizes are inconsistent

  ///                          with old sizes

  bool updateSizes(ArrayRef<const SCEV *> Sizes, bool CheckConsistency = true);

 

  /// Set the base pointer to @p BP.

  void setBasePtr(Value *BP) { BasePtr = BP; }

 

  /// Return the base pointer.

  Value *getBasePtr() const { return BasePtr; }

 

  // Set IsOnHeap to the value in parameter.

  void setIsOnHeap(bool value) { IsOnHeap = value; }

 

  /// For indirect accesses return the origin SAI of the BP, else null.

  const ScopArrayInfo *getBasePtrOriginSAI() const { return BasePtrOriginSAI; }

 

  /// The set of derived indirect SAIs for this origin SAI.

  const SmallSetVector<ScopArrayInfo *, 2> &getDerivedSAIs() const {

    return DerivedSAIs;

  }

 

  /// Return the number of dimensions.

  unsigned getNumberOfDimensions() const {

    if (Kind == MemoryKind::PHI || Kind == MemoryKind::ExitPHI ||

        Kind == MemoryKind::Value)

      return 0;

    return DimensionSizes.size();

  }

 

  /// Return the size of dimension @p dim as SCEV*.

  //

  //  Scalars do not have array dimensions and the first dimension of

  //  a (possibly multi-dimensional) array also does not carry any size

  //  information, in case the array is not newly created.

  const SCEV *getDimensionSize(unsigned Dim) const {

    assert(Dim < getNumberOfDimensions() && "Invalid dimension");

    return DimensionSizes[Dim];

  }

 

  /// Return the size of dimension @p dim as isl::pw_aff.

  //

  //  Scalars do not have array dimensions and the first dimension of

  //  a (possibly multi-dimensional) array also does not carry any size

  //  information, in case the array is not newly created.

  isl::pw_aff getDimensionSizePw(unsigned Dim) const {

    assert(Dim < getNumberOfDimensions() && "Invalid dimension");

    return DimensionSizesPw[Dim];

  }

 

  /// Get the canonical element type of this array.

  ///

  /// @returns The canonical element type of this array.

  Type *getElementType() const { return ElementType; }

 

  /// Get element size in bytes.

  int getElemSizeInBytes() const;

 

  /// Get the name of this memory reference.

  std::string getName() const;

 

  /// Return the isl id for the base pointer.

  isl::id getBasePtrId() const;

 

  /// Return what kind of memory this represents.

  MemoryKind getKind() const { return Kind; }

 

  /// Is this array info modeling an llvm::Value?

  bool isValueKind() const { return Kind == MemoryKind::Value; }

 

  /// Is this array info modeling special PHI node memory?

  ///

  /// During code generation of PHI nodes, there is a need for two kinds of

  /// virtual storage. The normal one as it is used for all scalar dependences,

  /// where the result of the PHI node is stored and later loaded from as well

  /// as a second one where the incoming values of the PHI nodes are stored

  /// into and reloaded when the PHI is executed. As both memories use the

  /// original PHI node as virtual base pointer, we have this additional

  /// attribute to distinguish the PHI node specific array modeling from the

  /// normal scalar array modeling.

  bool isPHIKind() const { return Kind == MemoryKind::PHI; }

 

  /// Is this array info modeling an MemoryKind::ExitPHI?

  bool isExitPHIKind() const { return Kind == MemoryKind::ExitPHI; }

 

  /// Is this array info modeling an array?

  bool isArrayKind() const { return Kind == MemoryKind::Array; }

 

  /// Is this array allocated on heap

  ///

  /// This property is only relevant if the array is allocated by Polly instead

  /// of pre-existing. If false, it is allocated using alloca instead malloca.

  bool isOnHeap() const { return IsOnHeap; }

 

  /// Dump a readable representation to stderr.

  void dump() const;

 

  /// Print a readable representation to @p OS.

  ///

  /// @param SizeAsPwAff Print the size as isl::pw_aff

  void print(raw_ostream &OS, bool SizeAsPwAff = false) const;

 

  /// Access the ScopArrayInfo associated with an access function.

  static const ScopArrayInfo *getFromAccessFunction(isl::pw_multi_aff PMA);

 

  /// Access the ScopArrayInfo associated with an isl Id.

  static const ScopArrayInfo *getFromId(isl::id Id);

 

  /// Get the space of this array access.

  isl::space getSpace() const;

 

  /// If the array is read only

  bool isReadOnly();

 

  /// Verify that @p Array is compatible to this ScopArrayInfo.

  ///

  /// Two arrays are compatible if their dimensionality, the sizes of their

  /// dimensions, and their element sizes match.

  ///

  /// @param Array The array to compare against.

  ///

  /// @returns True, if the arrays are compatible, False otherwise.

  bool isCompatibleWith(const ScopArrayInfo *Array) const;

 

  void addDerivedSAI(ScopArrayInfo *DerivedSAI) {

    DerivedSAIs.insert(DerivedSAI);

  }

 

  /// For indirect accesses this is the SAI of the BP origin.

  const ScopArrayInfo *BasePtrOriginSAI;

 

  /// For origin SAIs the set of derived indirect SAIs.

  SmallSetVector<ScopArrayInfo *, 2> DerivedSAIs;

 

  /// The base pointer.

  AssertingVH<Value> BasePtr;

 

  /// The canonical element type of this array.

  ///

  /// The canonical element type describes the minimal accessible element in

  /// this array. Not all elements accessed, need to be of the very same type,

  /// but the allocation size of the type of the elements loaded/stored from/to

  /// this array needs to be a multiple of the allocation size of the canonical

  /// type.

  Type *ElementType;

 

  /// The isl id for the base pointer.

  isl::id Id;

 

  /// True if the newly allocated array is on heap.

  bool IsOnHeap = false;

 

  /// The sizes of each dimension as SCEV*.

  SmallVector<const SCEV *, 4> DimensionSizes;

 

  /// The sizes of each dimension as isl::pw_aff.

  SmallVector<isl::pw_aff, 4> DimensionSizesPw;

 

  /// The type of this scop array info object.

  ///

  /// We distinguish between SCALAR, PHI and ARRAY objects.

  MemoryKind Kind;

 

  /// The data layout of the module.

  const DataLayout &DL;

 

  /// The scop this SAI object belongs to.

  Scop &S;

 

class MemoryAccess final {

  friend class Scop;

  friend class ScopStmt;

  friend class ScopBuilder;

 

  /// The access type of a memory access

  ///

  /// There are three kind of access types:

  ///

  /// * A read access

  ///

  /// A certain set of memory locations are read and may be used for internal

  /// calculations.

  ///

  /// * A must-write access

  ///

  /// A certain set of memory locations is definitely written. The old value is

  /// replaced by a newly calculated value. The old value is not read or used at

  /// all.

  ///

  /// * A may-write access

  ///

  /// A certain set of memory locations may be written. The memory location may

  /// contain a new value if there is actually a write or the old value may

  /// remain, if no write happens.

  enum AccessType {

    READ = 0x1,

    MUST_WRITE = 0x2,

    MAY_WRITE = 0x3,

  };

 

  /// Reduction access type

  ///

  /// Commutative and associative binary operations suitable for reductions

  enum ReductionType {

    RT_NONE, ///< Indicate no reduction at all

    RT_ADD,  ///< Addition

    RT_MUL,  ///< Multiplication

    RT_BOR,  ///< Bitwise Or

    RT_BXOR, ///< Bitwise XOr

    RT_BAND, ///< Bitwise And

  };

 

  using SubscriptsTy = SmallVector<const SCEV *, 4>;

 

  /// A unique identifier for this memory access.

  ///

  /// The identifier is unique between all memory accesses belonging to the same

  /// scop statement.

  isl::id Id;

 

  /// What is modeled by this MemoryAccess.

  /// @see MemoryKind

  MemoryKind Kind;

 

  /// Whether it a reading or writing access, and if writing, whether it

  /// is conditional (MAY_WRITE).

  enum AccessType AccType;

 

  /// Reduction type for reduction like accesses, RT_NONE otherwise

  ///

  /// An access is reduction like if it is part of a load-store chain in which

  /// both access the same memory location (use the same LLVM-IR value

  /// as pointer reference). Furthermore, between the load and the store there

  /// is exactly one binary operator which is known to be associative and

  /// commutative.

  ///

  /// TODO:

  ///

  /// We can later lift the constraint that the same LLVM-IR value defines the

  /// memory location to handle scops such as the following:

  ///

  ///    for i

  ///      for j

  ///        sum[i+j] = sum[i] + 3;

  ///

  /// Here not all iterations access the same memory location, but iterations

  /// for which j = 0 holds do. After lifting the equality check in ScopBuilder,

  /// subsequent transformations do not only need check if a statement is

  /// reduction like, but they also need to verify that that the reduction

  /// property is only exploited for statement instances that load from and

  /// store to the same data location. Doing so at dependence analysis time

  /// could allow us to handle the above example.

  ReductionType RedType = RT_NONE;

 

  /// Parent ScopStmt of this access.

  ScopStmt *Statement;

 

  /// The domain under which this access is not modeled precisely.

  ///

  /// The invalid domain for an access describes all parameter combinations

  /// under which the statement looks to be executed but is in fact not because

  /// some assumption/restriction makes the access invalid.

  isl::set InvalidDomain;

 

  // Properties describing the accessed array.

  // TODO: It might be possible to move them to ScopArrayInfo.

  // @{

 

  /// The base address (e.g., A for A[i+j]).

  ///

  /// The #BaseAddr of a memory access of kind MemoryKind::Array is the base

  /// pointer of the memory access.

  /// The #BaseAddr of a memory access of kind MemoryKind::PHI or

  /// MemoryKind::ExitPHI is the PHI node itself.

  /// The #BaseAddr of a memory access of kind MemoryKind::Value is the

  /// instruction defining the value.

  AssertingVH<Value> BaseAddr;

 

  /// Type a single array element wrt. this access.

  Type *ElementType;

 

  /// Size of each dimension of the accessed array.

  SmallVector<const SCEV *, 4> Sizes;

  // @}

 

  // Properties describing the accessed element.

  // @{

 

  /// The access instruction of this memory access.

  ///

  /// For memory accesses of kind MemoryKind::Array the access instruction is

  /// the Load or Store instruction performing the access.

  ///

  /// For memory accesses of kind MemoryKind::PHI or MemoryKind::ExitPHI the

  /// access instruction of a load access is the PHI instruction. The access

  /// instruction of a PHI-store is the incoming's block's terminator

  /// instruction.

  ///

  /// For memory accesses of kind MemoryKind::Value the access instruction of a

  /// load access is nullptr because generally there can be multiple

  /// instructions in the statement using the same llvm::Value. The access

  /// instruction of a write access is the instruction that defines the

  /// llvm::Value.

  Instruction *AccessInstruction = nullptr;

 

  /// Incoming block and value of a PHINode.

  SmallVector<std::pair<BasicBlock *, Value *>, 4> Incoming;

 

  /// The value associated with this memory access.

  ///

  ///  - For array memory accesses (MemoryKind::Array) it is the loaded result

  ///    or the stored value. If the access instruction is a memory intrinsic it

  ///    the access value is also the memory intrinsic.

  ///  - For accesses of kind MemoryKind::Value it is the access instruction

  ///    itself.

  ///  - For accesses of kind MemoryKind::PHI or MemoryKind::ExitPHI it is the

  ///    PHI node itself (for both, READ and WRITE accesses).

  ///

  AssertingVH<Value> AccessValue;

 

  /// Are all the subscripts affine expression?

  bool IsAffine = true;

 

  /// Subscript expression for each dimension.

  SubscriptsTy Subscripts;

 

  /// Relation from statement instances to the accessed array elements.

  ///

  /// In the common case this relation is a function that maps a set of loop

  /// indices to the memory address from which a value is loaded/stored:

  ///

  ///      for i

  ///        for j

  ///    S:     A[i + 3 j] = ...

  ///

  ///    => { S[i,j] -> A[i + 3j] }

  ///

  /// In case the exact access function is not known, the access relation may

  /// also be a one to all mapping { S[i,j] -> A[o] } describing that any

  /// element accessible through A might be accessed.

  ///

  /// In case of an access to a larger element belonging to an array that also

  /// contains smaller elements, the access relation models the larger access

  /// with multiple smaller accesses of the size of the minimal array element

  /// type:

  ///

  ///      short *A;

  ///

  ///      for i

  ///    S:     A[i] = *((double*)&A[4 * i]);

  ///

  ///    => { S[i] -> A[i]; S[i] -> A[o] : 4i <= o <= 4i + 3 }

  isl::map AccessRelation;

 

  /// Updated access relation read from JSCOP file.

  isl::map NewAccessRelation;

  // @}

 

  isl::basic_map createBasicAccessMap(ScopStmt *Statement);

 

  isl::set assumeNoOutOfBound();

 

  /// Compute bounds on an over approximated  access relation.

  ///

  /// @param ElementSize The size of one element accessed.

  void computeBoundsOnAccessRelation(unsigned ElementSize);

 

  /// Get the original access function as read from IR.

  isl::map getOriginalAccessRelation() const;

 

  /// Return the space in which the access relation lives in.

  isl::space getOriginalAccessRelationSpace() const;

 

  /// Get the new access function imported or set by a pass

  isl::map getNewAccessRelation() const;

 

  /// Fold the memory access to consider parametric offsets

  ///

  /// To recover memory accesses with array size parameters in the subscript

  /// expression we post-process the delinearization results.

  ///

  /// We would normally recover from an access A[exp0(i) * N + exp1(i)] into an

  /// array A[][N] the 2D access A[exp0(i)][exp1(i)]. However, another valid

  /// delinearization is A[exp0(i) - 1][exp1(i) + N] which - depending on the

  /// range of exp1(i) - may be preferable. Specifically, for cases where we

  /// know exp1(i) is negative, we want to choose the latter expression.

  ///

  /// As we commonly do not have any information about the range of exp1(i),

  /// we do not choose one of the two options, but instead create a piecewise

  /// access function that adds the (-1, N) offsets as soon as exp1(i) becomes

  /// negative. For a 2D array such an access function is created by applying

  /// the piecewise map:

  ///

  /// [i,j] -> [i, j] :      j >= 0

  /// [i,j] -> [i-1, j+N] :  j <  0

  ///

  /// We can generalize this mapping to arbitrary dimensions by applying this

  /// piecewise mapping pairwise from the rightmost to the leftmost access

  /// dimension. It would also be possible to cover a wider range by introducing

  /// more cases and adding multiple of Ns to these cases. However, this has

  /// not yet been necessary.

  /// The introduction of different cases necessarily complicates the memory

  /// access function, but cases that can be statically proven to not happen

  /// will be eliminated later on.

  void foldAccessRelation();

 

  /// Create the access relation for the underlying memory intrinsic.

  void buildMemIntrinsicAccessRelation();

 

  /// Assemble the access relation from all available information.

  ///

  /// In particular, used the information passes in the constructor and the

  /// parent ScopStmt set by setStatment().

  ///

  /// @param SAI Info object for the accessed array.

  void buildAccessRelation(const ScopArrayInfo *SAI);

 

  /// Carry index overflows of dimensions with constant size to the next higher

  /// dimension.

  ///

  /// For dimensions that have constant size, modulo the index by the size and

  /// add up the carry (floored division) to the next higher dimension. This is

  /// how overflow is defined in row-major order.

  /// It happens e.g. when ScalarEvolution computes the offset to the base

  /// pointer and would algebraically sum up all lower dimensions' indices of

  /// constant size.

  ///

  /// Example:

  ///   float (*A)[4];

  ///   A[1][6] -> A[2][2]

  void wrapConstantDimensions();

 

  /// Create a new MemoryAccess.

  ///

  /// @param Stmt       The parent statement.

  /// @param AccessInst The instruction doing the access.

  /// @param BaseAddr   The accessed array's address.

  /// @param ElemType   The type of the accessed array elements.

  /// @param AccType    Whether read or write access.

  /// @param IsAffine   Whether the subscripts are affine expressions.

  /// @param Kind       The kind of memory accessed.

  /// @param Subscripts Subscript expressions

  /// @param Sizes      Dimension lengths of the accessed array.

  MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst, AccessType AccType,

               Value *BaseAddress, Type *ElemType, bool Affine,

               ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,

               Value *AccessValue, MemoryKind Kind);

 

  /// Create a new MemoryAccess that corresponds to @p AccRel.

  ///

  /// Along with @p Stmt and @p AccType it uses information about dimension

  /// lengths of the accessed array, the type of the accessed array elements,

  /// the name of the accessed array that is derived from the object accessible

  /// via @p AccRel.

  ///

  /// @param Stmt       The parent statement.

  /// @param AccType    Whether read or write access.

  /// @param AccRel     The access relation that describes the memory access.

  MemoryAccess(ScopStmt *Stmt, AccessType AccType, isl::map AccRel);

 

  MemoryAccess(const MemoryAccess &) = delete;

  MemoryAccess &operator=(const MemoryAccess &) = delete;

  ~MemoryAccess();

 

  /// Add a new incoming block/value pairs for this PHI/ExitPHI access.

  ///

  /// @param IncomingBlock The PHI's incoming block.

  /// @param IncomingValue The value when reaching the PHI from the @p

  ///                      IncomingBlock.

  void addIncoming(BasicBlock *IncomingBlock, Value *IncomingValue) {

    assert(!isRead());

    assert(isAnyPHIKind());

    Incoming.emplace_back(std::make_pair(IncomingBlock, IncomingValue));

  }

 

  /// Return the list of possible PHI/ExitPHI values.

  ///

  /// After code generation moves some PHIs around during region simplification,

  /// we cannot reliably locate the original PHI node and its incoming values

  /// anymore. For this reason we remember these explicitly for all PHI-kind

  /// accesses.

  ArrayRef<std::pair<BasicBlock *, Value *>> getIncoming() const {

    assert(isAnyPHIKind());

    return Incoming;

  }

 

  /// Get the type of a memory access.

  enum AccessType getType() { return AccType; }

 

  /// Is this a reduction like access?

  bool isReductionLike() const { return RedType != RT_NONE; }

 

  /// Is this a read memory access?

  bool isRead() const { return AccType == MemoryAccess::READ; }

 

  /// Is this a must-write memory access?

  bool isMustWrite() const { return AccType == MemoryAccess::MUST_WRITE; }

 

  /// Is this a may-write memory access?

  bool isMayWrite() const { return AccType == MemoryAccess::MAY_WRITE; }

 

  /// Is this a write memory access?

  bool isWrite() const { return isMustWrite() || isMayWrite(); }

 

  /// Is this a memory intrinsic access (memcpy, memset, memmove)?

  bool isMemoryIntrinsic() const {

    return isa<MemIntrinsic>(getAccessInstruction());

  }

 

  /// Check if a new access relation was imported or set by a pass.

  bool hasNewAccessRelation() const { return !NewAccessRelation.is_null(); }

 

  /// Return the newest access relation of this access.

  ///

  /// There are two possibilities:

  ///   1) The original access relation read from the LLVM-IR.

  ///   2) A new access relation imported from a json file or set by another

  ///      pass (e.g., for privatization).

  ///

  /// As 2) is by construction "newer" than 1) we return the new access

  /// relation if present.

  ///

  isl::map getLatestAccessRelation() const {

    return hasNewAccessRelation() ? getNewAccessRelation()

                                  : getOriginalAccessRelation();

  }

 

  /// Old name of getLatestAccessRelation().

  isl::map getAccessRelation() const { return getLatestAccessRelation(); }

 

  /// Get an isl map describing the memory address accessed.

  ///

  /// In most cases the memory address accessed is well described by the access

  /// relation obtained with getAccessRelation. However, in case of arrays

  /// accessed with types of different size the access relation maps one access

  /// to multiple smaller address locations. This method returns an isl map that

  /// relates each dynamic statement instance to the unique memory location

  /// that is loaded from / stored to.

  ///

  /// For an access relation { S[i] -> A[o] : 4i <= o <= 4i + 3 } this method

  /// will return the address function { S[i] -> A[4i] }.

  ///

  /// @returns The address function for this memory access.

  isl::map getAddressFunction() const;

 

  /// Return the access relation after the schedule was applied.

  isl::pw_multi_aff

  applyScheduleToAccessRelation(isl::union_map Schedule) const;

 

  /// Get an isl string representing the access function read from IR.

  std::string getOriginalAccessRelationStr() const;

 

  /// Get an isl string representing a new access function, if available.

  std::string getNewAccessRelationStr() const;

 

  /// Get an isl string representing the latest access relation.

  std::string getAccessRelationStr() const;

 

  /// Get the original base address of this access (e.g. A for A[i+j]) when

  /// detected.

  ///

  /// This address may differ from the base address referenced by the original

  /// ScopArrayInfo to which this array belongs, as this memory access may

  /// have been canonicalized to a ScopArrayInfo which has a different but

  /// identically-valued base pointer in case invariant load hoisting is

  /// enabled.

  Value *getOriginalBaseAddr() const { return BaseAddr; }

 

  /// Get the detection-time base array isl::id for this access.

  isl::id getOriginalArrayId() const;

 

  /// Get the base array isl::id for this access, modifiable through

  /// setNewAccessRelation().

  isl::id getLatestArrayId() const;

 

  /// Old name of getOriginalArrayId().

  isl::id getArrayId() const { return getOriginalArrayId(); }

 

  /// Get the detection-time ScopArrayInfo object for the base address.

  const ScopArrayInfo *getOriginalScopArrayInfo() const;

 

  /// Get the ScopArrayInfo object for the base address, or the one set

  /// by setNewAccessRelation().

  const ScopArrayInfo *getLatestScopArrayInfo() const;

 

  /// Legacy name of getOriginalScopArrayInfo().

  const ScopArrayInfo *getScopArrayInfo() const {

    return getOriginalScopArrayInfo();

  }

 

  /// Return a string representation of the access's reduction type.

  const std::string getReductionOperatorStr() const;

 

  /// Return a string representation of the reduction type @p RT.

  static const std::string getReductionOperatorStr(ReductionType RT);

 

  /// Return the element type of the accessed array wrt. this access.

  Type *getElementType() const { return ElementType; }

 

  /// Return the access value of this memory access.

  Value *getAccessValue() const { return AccessValue; }

 

  /// Return llvm::Value that is stored by this access, if available.

  ///

  /// PHI nodes may not have a unique value available that is stored, as in

  /// case of region statements one out of possibly several llvm::Values

  /// might be stored. In this case nullptr is returned.

  Value *tryGetValueStored() {

    assert(isWrite() && "Only write statement store values");

    if (isAnyPHIKind()) {

      if (Incoming.size() == 1)

        return Incoming[0].second;

      return nullptr;

    }

    return AccessValue;

  }

 

  /// Return the access instruction of this memory access.

  Instruction *getAccessInstruction() const { return AccessInstruction; }

 

  ///  Return an iterator range containing the subscripts.

  iterator_range<SubscriptsTy::const_iterator> subscripts() const {

    return make_range(Subscripts.begin(), Subscripts.end());

  }

 

  /// Return the number of access function subscript.

  unsigned getNumSubscripts() const { return Subscripts.size(); }

 

  /// Return the access function subscript in the dimension @p Dim.

  const SCEV *getSubscript(unsigned Dim) const { return Subscripts[Dim]; }

 

  /// Compute the isl representation for the SCEV @p E wrt. this access.

  ///

  /// Note that this function will also adjust the invalid context accordingly.

  isl::pw_aff getPwAff(const SCEV *E);

 

  /// Get the invalid domain for this access.

  isl::set getInvalidDomain() const { return InvalidDomain; }

 

  /// Get the invalid context for this access.

  isl::set getInvalidContext() const { return getInvalidDomain().params(); }

 

  /// Get the stride of this memory access in the specified Schedule. Schedule

  /// is a map from the statement to a schedule where the innermost dimension is

  /// the dimension of the innermost loop containing the statement.

  isl::set getStride(isl::map Schedule) const;

 

  /// Is the stride of the access equal to a certain width? Schedule is a map

  /// from the statement to a schedule where the innermost dimension is the

  /// dimension of the innermost loop containing the statement.

  bool isStrideX(isl::map Schedule, int StrideWidth) const;

 

  /// Is consecutive memory accessed for a given statement instance set?

  /// Schedule is a map from the statement to a schedule where the innermost

  /// dimension is the dimension of the innermost loop containing the

  /// statement.

  bool isStrideOne(isl::map Schedule) const;

 

  /// Is always the same memory accessed for a given statement instance set?

  /// Schedule is a map from the statement to a schedule where the innermost

  /// dimension is the dimension of the innermost loop containing the

  /// statement.

  bool isStrideZero(isl::map Schedule) const;

 

  /// Return the kind when this access was first detected.

  MemoryKind getOriginalKind() const {

    assert(!getOriginalScopArrayInfo() /* not yet initialized */ ||

           getOriginalScopArrayInfo()->getKind() == Kind);

    return Kind;

  }

 

  /// Return the kind considering a potential setNewAccessRelation.

  MemoryKind getLatestKind() const {

    return getLatestScopArrayInfo()->getKind();

  }

 

  /// Whether this is an access of an explicit load or store in the IR.

  bool isOriginalArrayKind() const {

    return getOriginalKind() == MemoryKind::Array;

  }

 

  /// Whether storage memory is either an custom .s2a/.phiops alloca

  /// (false) or an existing pointer into an array (true).

  bool isLatestArrayKind() const {

    return getLatestKind() == MemoryKind::Array;

  }

 

  /// Old name of isOriginalArrayKind.

  bool isArrayKind() const { return isOriginalArrayKind(); }

 

  /// Whether this access is an array to a scalar memory object, without

  /// considering changes by setNewAccessRelation.

  ///

  /// Scalar accesses are accesses to MemoryKind::Value, MemoryKind::PHI or

  /// MemoryKind::ExitPHI.

  bool isOriginalScalarKind() const {

    return getOriginalKind() != MemoryKind::Array;

  }

 

  /// Whether this access is an array to a scalar memory object, also

  /// considering changes by setNewAccessRelation.

  bool isLatestScalarKind() const {

    return getLatestKind() != MemoryKind::Array;

  }

 

  /// Old name of isOriginalScalarKind.

  bool isScalarKind() const { return isOriginalScalarKind(); }

 

  /// Was this MemoryAccess detected as a scalar dependences?

  bool isOriginalValueKind() const {

    return getOriginalKind() == MemoryKind::Value;

  }

 

  /// Is this MemoryAccess currently modeling scalar dependences?

  bool isLatestValueKind() const {

    return getLatestKind() == MemoryKind::Value;

  }

 

  /// Old name of isOriginalValueKind().

  bool isValueKind() const { return isOriginalValueKind(); }

 

  /// Was this MemoryAccess detected as a special PHI node access?

  bool isOriginalPHIKind() const {

    return getOriginalKind() == MemoryKind::PHI;

  }

 

  /// Is this MemoryAccess modeling special PHI node accesses, also

  /// considering a potential change by setNewAccessRelation?

  bool isLatestPHIKind() const { return getLatestKind() == MemoryKind::PHI; }

 

  /// Old name of isOriginalPHIKind.

  bool isPHIKind() const { return isOriginalPHIKind(); }

 

  /// Was this MemoryAccess detected as the accesses of a PHI node in the

  /// SCoP's exit block?

  bool isOriginalExitPHIKind() const {

    return getOriginalKind() == MemoryKind::ExitPHI;

  }

 

  /// Is this MemoryAccess modeling the accesses of a PHI node in the

  /// SCoP's exit block? Can be changed to an array access using

  /// setNewAccessRelation().

  bool isLatestExitPHIKind() const {

    return getLatestKind() == MemoryKind::ExitPHI;

  }

 

  /// Old name of isOriginalExitPHIKind().

  bool isExitPHIKind() const { return isOriginalExitPHIKind(); }

 

  /// Was this access detected as one of the two PHI types?

  bool isOriginalAnyPHIKind() const {

    return isOriginalPHIKind() || isOriginalExitPHIKind();

  }

 

  /// Does this access originate from one of the two PHI types? Can be

  /// changed to an array access using setNewAccessRelation().

  bool isLatestAnyPHIKind() const {

    return isLatestPHIKind() || isLatestExitPHIKind();

  }

 

  /// Old name of isOriginalAnyPHIKind().

  bool isAnyPHIKind() const { return isOriginalAnyPHIKind(); }

 

  /// Get the statement that contains this memory access.

  ScopStmt *getStatement() const { return Statement; }

 

  /// Get the reduction type of this access

  ReductionType getReductionType() const { return RedType; }

 

  /// Update the original access relation.

  ///

  /// We need to update the original access relation during scop construction,

  /// when unifying the memory accesses that access the same scop array info

  /// object. After the scop has been constructed, the original access relation

  /// should not be changed any more. Instead setNewAccessRelation should

  /// be called.

  void setAccessRelation(isl::map AccessRelation);

 

  /// Set the updated access relation read from JSCOP file.

  void setNewAccessRelation(isl::map NewAccessRelation);

 

  /// Return whether the MemoryyAccess is a partial access. That is, the access

  /// is not executed in some instances of the parent statement's domain.

  bool isLatestPartialAccess() const;

 

  /// Mark this a reduction like access

  void markAsReductionLike(ReductionType RT) { RedType = RT; }

 

  /// Align the parameters in the access relation to the scop context

  void realignParams();

 

  /// Update the dimensionality of the memory access.

  ///

  /// During scop construction some memory accesses may not be constructed with

  /// their full dimensionality, but outer dimensions may have been omitted if

  /// they took the value 'zero'. By updating the dimensionality of the

  /// statement we add additional zero-valued dimensions to match the

  /// dimensionality of the ScopArrayInfo object that belongs to this memory

  /// access.

  void updateDimensionality();

 

  /// Get identifier for the memory access.

  ///

  /// This identifier is unique for all accesses that belong to the same scop

  /// statement.

  isl::id getId() const;

 

  /// Print the MemoryAccess.

  ///

  /// @param OS The output stream the MemoryAccess is printed to.

  void print(raw_ostream &OS) const;

 

  /// Print the MemoryAccess to stderr.

  void dump() const;

 

  /// Is the memory access affine?

  bool isAffine() const { return IsAffine; }

 

raw_ostream &operator<<(raw_ostream &OS, MemoryAccess::ReductionType RT);

 

using MemoryAccessList = std::forward_list<MemoryAccess *>;

 

struct InvariantAccess {

  /// The memory access that is (partially) invariant.

  MemoryAccess *MA;

 

  /// The context under which the access is not invariant.

  isl::set NonHoistableCtx;

 

using InvariantAccessesTy = SmallVector<InvariantAccess, 8>;

 

struct InvariantEquivClassTy {

  /// The pointer that identifies this equivalence class

  const SCEV *IdentifyingPointer;

 

  /// Memory accesses now treated invariant

  ///

  /// These memory accesses access the pointer location that identifies

  /// this equivalence class. They are treated as invariant and hoisted during

  /// code generation.

  MemoryAccessList InvariantAccesses;

 

  /// The execution context under which the memory location is accessed

  ///

  /// It is the union of the execution domains of the memory accesses in the

  /// InvariantAccesses list.

  isl::set ExecutionContext;

 

  /// The type of the invariant access

  ///

  /// It is used to differentiate between differently typed invariant loads from

  /// the same location.

  Type *AccessType;

 

using InvariantEquivClassesTy = SmallVector<InvariantEquivClassTy, 8>;

 

class ScopStmt final {

  friend class ScopBuilder;

 

  /// Create the ScopStmt from a BasicBlock.

  ScopStmt(Scop &parent, BasicBlock &bb, StringRef Name, Loop *SurroundingLoop,

           std::vector<Instruction *> Instructions);

 

  /// Create an overapproximating ScopStmt for the region @p R.

  ///

  /// @param EntryBlockInstructions The list of instructions that belong to the

  ///                               entry block of the region statement.

  ///                               Instructions are only tracked for entry

  ///                               blocks for now. We currently do not allow

  ///                               to modify the instructions of blocks later

  ///                               in the region statement.

  ScopStmt(Scop &parent, Region &R, StringRef Name, Loop *SurroundingLoop,

           std::vector<Instruction *> EntryBlockInstructions);

 

  /// Create a copy statement.

  ///

  /// @param Stmt       The parent statement.

  /// @param SourceRel  The source location.

  /// @param TargetRel  The target location.

  /// @param Domain     The original domain under which the copy statement would

  ///                   be executed.

  ScopStmt(Scop &parent, isl::map SourceRel, isl::map TargetRel,

           isl::set Domain);

 

  ScopStmt(const ScopStmt &) = delete;

  const ScopStmt &operator=(const ScopStmt &) = delete;

  ~ScopStmt();

 

  /// Polyhedral description

  //@{

 

  /// The Scop containing this ScopStmt.

  Scop &Parent;

 

  /// The domain under which this statement is not modeled precisely.

  ///

  /// The invalid domain for a statement describes all parameter combinations

  /// under which the statement looks to be executed but is in fact not because

  /// some assumption/restriction makes the statement/scop invalid.

  isl::set InvalidDomain;

 

  /// The iteration domain describes the set of iterations for which this

  /// statement is executed.

  ///

  /// Example:

  ///     for (i = 0; i < 100 + b; ++i)

  ///       for (j = 0; j < i; ++j)

  ///         S(i,j);

  ///

  /// 'S' is executed for different values of i and j. A vector of all

  /// induction variables around S (i, j) is called iteration vector.

  /// The domain describes the set of possible iteration vectors.

  ///

  /// In this case it is:

  ///

  ///     Domain: 0 <= i <= 100 + b

  ///             0 <= j <= i

  ///

  /// A pair of statement and iteration vector (S, (5,3)) is called statement

  /// instance.

  isl::set Domain;

 

  /// The memory accesses of this statement.

  ///

  /// The only side effects of a statement are its memory accesses.

  using MemoryAccessVec = llvm::SmallVector<MemoryAccess *, 8>;

  MemoryAccessVec MemAccs;

 

  /// Mapping from instructions to (scalar) memory accesses.

  DenseMap<const Instruction *, MemoryAccessList> InstructionToAccess;

 

  /// The set of values defined elsewhere required in this ScopStmt and

  ///        their MemoryKind::Value READ MemoryAccesses.

  DenseMap<Value *, MemoryAccess *> ValueReads;

 

  /// The set of values defined in this ScopStmt that are required

  ///        elsewhere, mapped to their MemoryKind::Value WRITE MemoryAccesses.

  DenseMap<Instruction *, MemoryAccess *> ValueWrites;

 

  /// Map from PHI nodes to its incoming value when coming from this

  ///        statement.

  ///

  /// Non-affine subregions can have multiple exiting blocks that are incoming

  /// blocks of the PHI nodes. This map ensures that there is only one write

  /// operation for the complete subregion. A PHI selecting the relevant value

  /// will be inserted.

  DenseMap<PHINode *, MemoryAccess *> PHIWrites;

 

  /// Map from PHI nodes to its read access in this statement.

  DenseMap<PHINode *, MemoryAccess *> PHIReads;

 

  //@}

 

  /// A SCoP statement represents either a basic block (affine/precise case) or

  /// a whole region (non-affine case).

  ///

  /// Only one of the following two members will therefore be set and indicate

  /// which kind of statement this is.

  ///

  ///{

 

  /// The BasicBlock represented by this statement (in the affine case).

  BasicBlock *BB = nullptr;

 

  /// The region represented by this statement (in the non-affine case).

  Region *R = nullptr;

 

  ///}

 

  /// The isl AST build for the new generated AST.

  isl::ast_build Build;

 

  SmallVector<Loop *, 4> NestLoops;

 

  std::string BaseName;

 

  /// The closest loop that contains this statement.

  Loop *SurroundingLoop;

 

  /// Vector for Instructions in this statement.

  std::vector<Instruction *> Instructions;

 

  /// Remove @p MA from dictionaries pointing to them.

  void removeAccessData(MemoryAccess *MA);

 

  /// Get an isl_ctx pointer.

  isl::ctx getIslCtx() const;

 

  /// Get the iteration domain of this ScopStmt.

  ///

  /// @return The iteration domain of this ScopStmt.

  isl::set getDomain() const;

 

  /// Get the space of the iteration domain

  ///

  /// @return The space of the iteration domain

  isl::space getDomainSpace() const;

 

  /// Get the id of the iteration domain space

  ///

  /// @return The id of the iteration domain space

  isl::id getDomainId() const;

 

  /// Get an isl string representing this domain.

  std::string getDomainStr() const;

 

  /// Get the schedule function of this ScopStmt.

  ///

  /// @return The schedule function of this ScopStmt, if it does not contain

  /// extension nodes, and nullptr, otherwise.

  isl::map getSchedule() const;

 

  /// Get an isl string representing this schedule.

  ///

  /// @return An isl string representing this schedule, if it does not contain

  /// extension nodes, and an empty string, otherwise.

  std::string getScheduleStr() const;

 

  /// Get the invalid domain for this statement.

  isl::set getInvalidDomain() const { return InvalidDomain; }

 

  /// Get the invalid context for this statement.

  isl::set getInvalidContext() const { return getInvalidDomain().params(); }

 

  /// Set the invalid context for this statement to @p ID.

  void setInvalidDomain(isl::set ID);

 

  /// Get the BasicBlock represented by this ScopStmt (if any).

  ///

  /// @return The BasicBlock represented by this ScopStmt, or null if the

  ///         statement represents a region.

  BasicBlock *getBasicBlock() const { return BB; }

 

  /// Return true if this statement represents a single basic block.

  bool isBlockStmt() const { return BB != nullptr; }

 

  /// Return true if this is a copy statement.

  bool isCopyStmt() const { return BB == nullptr && R == nullptr; }

 

  /// Get the region represented by this ScopStmt (if any).

  ///

  /// @return The region represented by this ScopStmt, or null if the statement

  ///         represents a basic block.

  Region *getRegion() const { return R; }

 

  /// Return true if this statement represents a whole region.

  bool isRegionStmt() const { return R != nullptr; }

 

  /// Return a BasicBlock from this statement.

  ///

  /// For block statements, it returns the BasicBlock itself. For subregion

  /// statements, return its entry block.

  BasicBlock *getEntryBlock() const;

 

  /// Return whether @p L is boxed within this statement.

  bool contains(const Loop *L) const {

    // Block statements never contain loops.

    if (isBlockStmt())

      return false;

 

    return getRegion()->contains(L);

  }

 

  /// Return whether this statement represents @p BB.

  bool represents(BasicBlock *BB) const {

    if (isCopyStmt())

      return false;

    if (isBlockStmt())

      return BB == getBasicBlock();

    return getRegion()->contains(BB);

  }

 

  /// Return whether this statement contains @p Inst.

  bool contains(Instruction *Inst) const {

    if (!Inst)

      return false;

    if (isBlockStmt())

      return llvm::is_contained(Instructions, Inst);

    return represents(Inst->getParent());

  }

 

  /// Return the closest innermost loop that contains this statement, but is not

  /// contained in it.

  ///

  /// For block statement, this is just the loop that contains the block. Region

  /// statements can contain boxed loops, so getting the loop of one of the

  /// region's BBs might return such an inner loop. For instance, the region's

  /// entry could be a header of a loop, but the region might extend to BBs

  /// after the loop exit. Similarly, the region might only contain parts of the

  /// loop body and still include the loop header.

  ///

  /// Most of the time the surrounding loop is the top element of #NestLoops,

  /// except when it is empty. In that case it return the loop that the whole

  /// SCoP is contained in. That can be nullptr if there is no such loop.

  Loop *getSurroundingLoop() const {

    assert(!isCopyStmt() &&

           "No surrounding loop for artificially created statements");

    return SurroundingLoop;

  }

 

  /// Return true if this statement does not contain any accesses.

  bool isEmpty() const { return MemAccs.empty(); }

 

  /// Find all array accesses for @p Inst.

  ///

  /// @param Inst The instruction accessing an array.

  ///

  /// @return A list of array accesses (MemoryKind::Array) accessed by @p Inst.

  ///         If there is no such access, it returns nullptr.

  const MemoryAccessList *

  lookupArrayAccessesFor(const Instruction *Inst) const {

    auto It = InstructionToAccess.find(Inst);

    if (It == InstructionToAccess.end())

      return nullptr;

    if (It->second.empty())

      return nullptr;

    return &It->second;

  }

 

  /// Return the only array access for @p Inst, if existing.

  ///

  /// @param Inst The instruction for which to look up the access.

  /// @returns The unique array memory access related to Inst or nullptr if

  ///          no array access exists

  MemoryAccess *getArrayAccessOrNULLFor(const Instruction *Inst) const {

    auto It = InstructionToAccess.find(Inst);

    if (It == InstructionToAccess.end())

      return nullptr;

 

    MemoryAccess *ArrayAccess = nullptr;

 

    for (auto Access : It->getSecond()) {

      if (!Access->isArrayKind())

        continue;

 

      assert(!ArrayAccess && "More then one array access for instruction");

 

      ArrayAccess = Access;

    }

 

    return ArrayAccess;

  }

 

  /// Return the only array access for @p Inst.

  ///

  /// @param Inst The instruction for which to look up the access.

  /// @returns The unique array memory access related to Inst.

  MemoryAccess &getArrayAccessFor(const Instruction *Inst) const {

    MemoryAccess *ArrayAccess = getArrayAccessOrNULLFor(Inst);

 

    assert(ArrayAccess && "No array access found for instruction!");

    return *ArrayAccess;

  }

 

  /// Return the MemoryAccess that writes the value of an instruction

  ///        defined in this statement, or nullptr if not existing, respectively

  ///        not yet added.

  MemoryAccess *lookupValueWriteOf(Instruction *Inst) const {

    assert((isRegionStmt() && R->contains(Inst)) ||

           (!isRegionStmt() && Inst->getParent() == BB));

    return ValueWrites.lookup(Inst);

  }

 

  /// Return the MemoryAccess that reloads a value, or nullptr if not

  ///        existing, respectively not yet added.

  MemoryAccess *lookupValueReadOf(Value *Inst) const {

    return ValueReads.lookup(Inst);

  }

 

  /// Return the MemoryAccess that loads a PHINode value, or nullptr if not

  /// existing, respectively not yet added.

  MemoryAccess *lookupPHIReadOf(PHINode *PHI) const {

    return PHIReads.lookup(PHI);

  }

 

  /// Return the PHI write MemoryAccess for the incoming values from any

  ///        basic block in this ScopStmt, or nullptr if not existing,

  ///        respectively not yet added.

  MemoryAccess *lookupPHIWriteOf(PHINode *PHI) const {

    assert(isBlockStmt() || R->getExit() == PHI->getParent());

    return PHIWrites.lookup(PHI);

  }

 

  /// Return the input access of the value, or null if no such MemoryAccess

  /// exists.

  ///

  /// The input access is the MemoryAccess that makes an inter-statement value

  /// available in this statement by reading it at the start of this statement.

  /// This can be a MemoryKind::Value if defined in another statement or a

  /// MemoryKind::PHI if the value is a PHINode in this statement.

  MemoryAccess *lookupInputAccessOf(Value *Val) const {

    if (isa<PHINode>(Val))

      if (auto InputMA = lookupPHIReadOf(cast<PHINode>(Val))) {

        assert(!lookupValueReadOf(Val) && "input accesses must be unique; a "

                                          "statement cannot read a .s2a and "

                                          ".phiops simultaneously");

        return InputMA;

      }

 

    if (auto *InputMA = lookupValueReadOf(Val))

      return InputMA;

 

    return nullptr;

  }

 

  /// Add @p Access to this statement's list of accesses.

  ///

  /// @param Access  The access to add.

  /// @param Prepend If true, will add @p Access before all other instructions

  ///                (instead of appending it).

  void addAccess(MemoryAccess *Access, bool Preprend = false);

 

  /// Remove a MemoryAccess from this statement.

  ///

  /// Note that scalar accesses that are caused by MA will

  /// be eliminated too.

  void removeMemoryAccess(MemoryAccess *MA);

 

  /// Remove @p MA from this statement.

  ///

  /// In contrast to removeMemoryAccess(), no other access will be eliminated.

  ///

  /// @param MA            The MemoryAccess to be removed.

  /// @param AfterHoisting If true, also remove from data access lists.

  ///                      These lists are filled during

  ///                      ScopBuilder::buildAccessRelations. Therefore, if this

  ///                      method is called before buildAccessRelations, false

  ///                      must be passed.

  void removeSingleMemoryAccess(MemoryAccess *MA, bool AfterHoisting = true);

 

  using iterator = MemoryAccessVec::iterator;

  using const_iterator = MemoryAccessVec::const_iterator;

 

  iterator begin() { return MemAccs.begin(); }

  iterator end() { return MemAccs.end(); }

  const_iterator begin() const { return MemAccs.begin(); }

  const_iterator end() const { return MemAccs.end(); }

  size_t size() const { return MemAccs.size(); }

 

  unsigned getNumIterators() const;

 

  Scop *getParent() { return &Parent; }

  const Scop *getParent() const { return &Parent; }

 

  const std::vector<Instruction *> &getInstructions() const {

    return Instructions;

  }

 

  /// Set the list of instructions for this statement. It replaces the current

  /// list.

  void setInstructions(ArrayRef<Instruction *> Range) {

    Instructions.assign(Range.begin(), Range.end());

  }

 

  std::vector<Instruction *>::const_iterator insts_begin() const {

    return Instructions.begin();

  }

 

  std::vector<Instruction *>::const_iterator insts_end() const {

    return Instructions.end();

  }

 

  /// The range of instructions in this statement.

  iterator_range<std::vector<Instruction *>::const_iterator> insts() const {

    return {insts_begin(), insts_end()};

  }

 

  /// Insert an instruction before all other instructions in this statement.

  void prependInstruction(Instruction *Inst) {

    Instructions.insert(Instructions.begin(), Inst);

  }

 

  const char *getBaseName() const;

 

  /// Set the isl AST build.

  void setAstBuild(isl::ast_build B) { Build = B; }

 

  /// Get the isl AST build.

  isl::ast_build getAstBuild() const { return Build; }

 

  /// Restrict the domain of the statement.

  ///

  /// @param NewDomain The new statement domain.

  void restrictDomain(isl::set NewDomain);

 

  /// Get the loop for a dimension.

  ///

  /// @param Dimension The dimension of the induction variable

  /// @return The loop at a certain dimension.

  Loop *getLoopForDimension(unsigned Dimension) const;

 

  /// Align the parameters in the statement to the scop context

  void realignParams();

 

  /// Print the ScopStmt.

  ///

  /// @param OS                The output stream the ScopStmt is printed to.

  /// @param PrintInstructions Whether to print the statement's instructions as

  ///                          well.

  void print(raw_ostream &OS, bool PrintInstructions) const;

 

  /// Print the instructions in ScopStmt.

  ///

  void printInstructions(raw_ostream &OS) const;

 

  /// Check whether there is a value read access for @p V in this statement, and

  /// if not, create one.

  ///

  /// This allows to add MemoryAccesses after the initial creation of the Scop

  /// by ScopBuilder.

  ///

  /// @return The already existing or newly created MemoryKind::Value READ

  /// MemoryAccess.

  ///

  /// @see ScopBuilder::ensureValueRead(Value*,ScopStmt*)

  MemoryAccess *ensureValueRead(Value *V);

 

  /// Print the ScopStmt to stderr.

  void dump() const;

 

raw_ostream &operator<<(raw_ostream &OS, const ScopStmt &S);

 

class Scop final {

  /// Type to represent a pair of minimal/maximal access to an array.

  using MinMaxAccessTy = std::pair<isl::pw_multi_aff, isl::pw_multi_aff>;

 

  /// Vector of minimal/maximal accesses to different arrays.

  using MinMaxVectorTy = SmallVector<MinMaxAccessTy, 4>;

 

  /// Pair of minimal/maximal access vectors representing

  /// read write and read only accesses

  using MinMaxVectorPairTy = std::pair<MinMaxVectorTy, MinMaxVectorTy>;

 

  /// Vector of pair of minimal/maximal access vectors representing

  /// non read only and read only accesses for each alias group.

  using MinMaxVectorPairVectorTy = SmallVector<MinMaxVectorPairTy, 4>;

 

  friend class ScopBuilder;

 

  /// Isl context.

  ///

  /// We need a shared_ptr with reference counter to delete the context when all

  /// isl objects are deleted. We will distribute the shared_ptr to all objects

  /// that use the context to create isl objects, and increase the reference

  /// counter. By doing this, we guarantee that the context is deleted when we

  /// delete the last object that creates isl objects with the context. This

  /// declaration needs to be the first in class to gracefully destroy all isl

  /// objects before the context.

  std::shared_ptr<isl_ctx> IslCtx;

 

  ScalarEvolution *SE;

  DominatorTree *DT;

 

  /// The underlying Region.

  Region &R;

 

  /// The name of the SCoP (identical to the regions name)

  std::optional<std::string> name;

 

  // Access functions of the SCoP.

  //

  // This owns all the MemoryAccess objects of the Scop created in this pass.

  AccFuncVector AccessFunctions;

 

  /// Flag to indicate that the scheduler actually optimized the SCoP.

  bool IsOptimized = false;

 

  /// True if the underlying region has a single exiting block.

  bool HasSingleExitEdge;

 

  /// Flag to remember if the SCoP contained an error block or not.

  bool HasErrorBlock = false;

 

  /// Max loop depth.

  unsigned MaxLoopDepth = 0;

 

  /// Number of copy statements.

  unsigned CopyStmtsNum = 0;

 

  /// Flag to indicate if the Scop is to be skipped.

  bool SkipScop = false;

 

  using StmtSet = std::list<ScopStmt>;

 

  /// The statements in this Scop.

  StmtSet Stmts;

 

  /// Parameters of this Scop

  ParameterSetTy Parameters;

 

  /// Mapping from parameters to their ids.

  DenseMap<const SCEV *, isl::id> ParameterIds;

 

  /// The context of the SCoP created during SCoP detection.

  ScopDetection::DetectionContext &DC;

 

  /// OptimizationRemarkEmitter object for displaying diagnostic remarks

  OptimizationRemarkEmitter &ORE;

 

  /// A map from basic blocks to vector of SCoP statements. Currently this

  /// vector comprises only of a single statement.

  DenseMap<BasicBlock *, std::vector<ScopStmt *>> StmtMap;

 

  /// A map from instructions to SCoP statements.

  DenseMap<Instruction *, ScopStmt *> InstStmtMap;

 

  /// A map from basic blocks to their domains.

  DenseMap<BasicBlock *, isl::set> DomainMap;

 

  /// Constraints on parameters.

  isl::set Context;

 

  /// The affinator used to translate SCEVs to isl expressions.

  SCEVAffinator Affinator;

 

  using ArrayInfoMapTy =

      std::map<std::pair<AssertingVH<const Value>, MemoryKind>,

               std::unique_ptr<ScopArrayInfo>>;

 

  using ArrayNameMapTy = StringMap<std::unique_ptr<ScopArrayInfo>>;

 

  using ArrayInfoSetTy = SetVector<ScopArrayInfo *>;

 

  /// A map to remember ScopArrayInfo objects for all base pointers.

  ///

  /// As PHI nodes may have two array info objects associated, we add a flag

  /// that distinguishes between the PHI node specific ArrayInfo object

  /// and the normal one.

  ArrayInfoMapTy ScopArrayInfoMap;

 

  /// A map to remember ScopArrayInfo objects for all names of memory

  ///        references.

  ArrayNameMapTy ScopArrayNameMap;

 

  /// A set to remember ScopArrayInfo objects.

  /// @see Scop::ScopArrayInfoMap

  ArrayInfoSetTy ScopArrayInfoSet;

 

  /// The assumptions under which this scop was built.

  ///

  /// When constructing a scop sometimes the exact representation of a statement

  /// or condition would be very complex, but there is a common case which is a

  /// lot simpler, but which is only valid under certain assumptions. The

  /// assumed context records the assumptions taken during the construction of

  /// this scop and that need to be code generated as a run-time test.

  isl::set AssumedContext;

 

  /// The restrictions under which this SCoP was built.

  ///

  /// The invalid context is similar to the assumed context as it contains

  /// constraints over the parameters. However, while we need the constraints

  /// in the assumed context to be "true" the constraints in the invalid context

  /// need to be "false". Otherwise they behave the same.

  isl::set InvalidContext;

 

  /// The context under which the SCoP must have defined behavior. Optimizer and

  /// code generator can assume that the SCoP will only be executed with

  /// parameter values within this context. This might be either because we can

  /// prove that other values are impossible or explicitly have undefined

  /// behavior, such as due to no-wrap flags. If this becomes too complex, can

  /// also be nullptr.

  ///

  /// In contrast to Scop::AssumedContext and Scop::InvalidContext, these do not

  /// need to be checked at runtime.

  ///

  /// Scop::Context on the other side is an overapproximation and does not

  /// include all requirements, but is always defined. However, there is still

  /// no guarantee that there is no undefined behavior in

  /// DefinedBehaviorContext.

  isl::set DefinedBehaviorContext;

 

  /// The schedule of the SCoP

  ///

  /// The schedule of the SCoP describes the execution order of the statements

  /// in the scop by assigning each statement instance a possibly

  /// multi-dimensional execution time. The schedule is stored as a tree of

  /// schedule nodes.

  ///

  /// The most common nodes in a schedule tree are so-called band nodes. Band

  /// nodes map statement instances into a multi dimensional schedule space.

  /// This space can be seen as a multi-dimensional clock.

  ///

  /// Example:

  ///

  /// <S,(5,4)>  may be mapped to (5,4) by this schedule:

  ///

  /// s0 = i (Year of execution)

  /// s1 = j (Day of execution)

  ///

  /// or to (9, 20) by this schedule:

  ///

  /// s0 = i + j (Year of execution)

  /// s1 = 20 (Day of execution)

  ///

  /// The order statement instances are executed is defined by the

  /// schedule vectors they are mapped to. A statement instance

  /// <A, (i, j, ..)> is executed before a statement instance <B, (i', ..)>, if

  /// the schedule vector of A is lexicographic smaller than the schedule

  /// vector of B.

  ///

  /// Besides band nodes, schedule trees contain additional nodes that specify

  /// a textual ordering between two subtrees or filter nodes that filter the

  /// set of statement instances that will be scheduled in a subtree. There

  /// are also several other nodes. A full description of the different nodes

  /// in a schedule tree is given in the isl manual.

  isl::schedule Schedule;

 

  /// Is this Scop marked as not to be transformed by an optimization heuristic?

  bool HasDisableHeuristicsHint = false;

 

  /// Whether the schedule has been modified after derived from the CFG by

  /// ScopBuilder.

  bool ScheduleModified = false;

 

  /// The set of minimal/maximal accesses for each alias group.

  ///

  /// When building runtime alias checks we look at all memory instructions and

  /// build so called alias groups. Each group contains a set of accesses to

  /// different base arrays which might alias with each other. However, between

  /// alias groups there is no aliasing possible.

  ///

  /// In a program with int and float pointers annotated with tbaa information

  /// we would probably generate two alias groups, one for the int pointers and

  /// one for the float pointers.

  ///

  /// During code generation we will create a runtime alias check for each alias

  /// group to ensure the SCoP is executed in an alias free environment.

  MinMaxVectorPairVectorTy MinMaxAliasGroups;

 

  /// Mapping from invariant loads to the representing invariant load of

  ///        their equivalence class.

  ValueToValueMap InvEquivClassVMap;

 

  /// List of invariant accesses.

  InvariantEquivClassesTy InvariantEquivClasses;

 

  /// The smallest array index not yet assigned.

  long ArrayIdx = 0;

 

  /// The smallest statement index not yet assigned.

  long StmtIdx = 0;

 

  /// A number that uniquely represents a Scop within its function

  const int ID;

 

  /// Map of values to the MemoryAccess that writes its definition.

  ///

  /// There must be at most one definition per llvm::Instruction in a SCoP.

  DenseMap<Value *, MemoryAccess *> ValueDefAccs;

 

  /// Map of values to the MemoryAccess that reads a PHI.

  DenseMap<PHINode *, MemoryAccess *> PHIReadAccs;

 

  /// List of all uses (i.e. read MemoryAccesses) for a MemoryKind::Value

  /// scalar.

  DenseMap<const ScopArrayInfo *, SmallVector<MemoryAccess *, 4>> ValueUseAccs;

 

  /// List of all incoming values (write MemoryAccess) of a MemoryKind::PHI or

  /// MemoryKind::ExitPHI scalar.

  DenseMap<const ScopArrayInfo *, SmallVector<MemoryAccess *, 4>>

      PHIIncomingAccs;

 

  /// Scop constructor; invoked from ScopBuilder::buildScop.

  Scop(Region &R, ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT,

       ScopDetection::DetectionContext &DC, OptimizationRemarkEmitter &ORE,

       int ID);

 

  //@}

 

  /// Return the access for the base ptr of @p MA if any.

  MemoryAccess *lookupBasePtrAccess(MemoryAccess *MA);

 

  /// Create an id for @p Param and store it in the ParameterIds map.

  void createParameterId(const SCEV *Param);

 

  /// Build the Context of the Scop.

  void buildContext();

 

  /// Add the bounds of the parameters to the context.

  void addParameterBounds();

 

  /// Simplify the assumed and invalid context.

  void simplifyContexts();

 

  /// Create a new SCoP statement for @p BB.

  ///

  /// A new statement for @p BB will be created and added to the statement

  /// vector

  /// and map.

  ///

  /// @param BB              The basic block we build the statement for.

  /// @param Name            The name of the new statement.

  /// @param SurroundingLoop The loop the created statement is contained in.

  /// @param Instructions    The instructions in the statement.

  void addScopStmt(BasicBlock *BB, StringRef Name, Loop *SurroundingLoop,

                   std::vector<Instruction *> Instructions);

 

  /// Create a new SCoP statement for @p R.

  ///

  /// A new statement for @p R will be created and added to the statement vector

  /// and map.

  ///

  /// @param R                      The region we build the statement for.

  /// @param Name                   The name of the new statement.

  /// @param SurroundingLoop        The loop the created statement is contained

  ///                               in.

  /// @param EntryBlockInstructions The (interesting) instructions in the

  ///                               entry block of the region statement.

  void addScopStmt(Region *R, StringRef Name, Loop *SurroundingLoop,

                   std::vector<Instruction *> EntryBlockInstructions);

 

  /// Removes @p Stmt from the StmtMap.

  void removeFromStmtMap(ScopStmt &Stmt);

 

  /// Removes all statements where the entry block of the statement does not

  /// have a corresponding domain in the domain map (or it is empty).

  void removeStmtNotInDomainMap();

 

  /// Collect all memory access relations of a given type.

  ///

  /// @param Predicate A predicate function that returns true if an access is

  ///                  of a given type.

  ///

  /// @returns The set of memory accesses in the scop that match the predicate.

  isl::union_map

  getAccessesOfType(std::function<bool(MemoryAccess &)> Predicate);

 

  /// @name Helper functions for printing the Scop.

  ///

  //@{

  void printContext(raw_ostream &OS) const;

  void printArrayInfo(raw_ostream &OS) const;

  void printStatements(raw_ostream &OS, bool PrintInstructions) const;

  void printAliasAssumptions(raw_ostream &OS) const;

  //@}

 

  Scop(const Scop &) = delete;

  Scop &operator=(const Scop &) = delete;

  ~Scop();

 

  /// Increment actual number of aliasing assumptions taken

  ///

  /// @param Step    Number of new aliasing assumptions which should be added to

  /// the number of already taken assumptions.

  static void incrementNumberOfAliasingAssumptions(unsigned Step);

 

  /// Get the count of copy statements added to this Scop.

  ///

  /// @return The count of copy statements added to this Scop.

  unsigned getCopyStmtsNum() { return CopyStmtsNum; }

 

  /// Create a new copy statement.

  ///

  /// A new statement will be created and added to the statement vector.

  ///

  /// @param SourceRel  The source location.

  /// @param TargetRel  The target location.

  /// @param Domain     The original domain under which the copy statement would

  ///                   be executed.

  ScopStmt *addScopStmt(isl::map SourceRel, isl::map TargetRel,

                        isl::set Domain);

 

  /// Add the access function to all MemoryAccess objects of the Scop

  ///        created in this pass.

  void addAccessFunction(MemoryAccess *Access) {

    AccessFunctions.emplace_back(Access);

 

    // Register value definitions.

    if (Access->isWrite() && Access->isOriginalValueKind()) {

      assert(!ValueDefAccs.count(Access->getAccessValue()) &&

             "there can be just one definition per value");

      ValueDefAccs[Access->getAccessValue()] = Access;

    } else if (Access->isRead() && Access->isOriginalPHIKind()) {

      PHINode *PHI = cast<PHINode>(Access->getAccessInstruction());