Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- polly/ScopInfo.h -----------------------------------------*- 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

//

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

//

// Store the polyhedral model representation of a static control flow region,

// also called SCoP (Static Control Part).

//

// This representation is shared among several tools in the polyhedral

// community, which are e.g. CLooG, Pluto, Loopo, Graphite.

//

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

#ifndef POLLY_SCOPINFO_H

#define POLLY_SCOPINFO_H

#include "polly/ScopDetection.h"

#include "polly/Support/SCEVAffinator.h"

#include "polly/Support/ScopHelper.h"

#include "llvm/ADT/ArrayRef.h"

#include "llvm/ADT/MapVector.h"

#include "llvm/ADT/SetVector.h"

#include "llvm/Analysis/RegionPass.h"

#include "llvm/IR/DebugLoc.h"

#include "llvm/IR/Instruction.h"

#include "llvm/IR/Instructions.h"

#include "llvm/IR/PassManager.h"

#include "llvm/IR/ValueHandle.h"

#include "llvm/Pass.h"

#include "isl/isl-noexceptions.h"

#include <cassert>

#include <cstddef>

#include <forward_list>

#include <optional>

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;

// The maximal number of basic sets we allow during domain construction to

// be created. More complex scops will result in very high compile time and

// are also unlikely to result in good code.

extern unsigned const MaxDisjunctsInDomain;

/// The different memory kinds used in Polly.

///

/// We distinguish between arrays and various scalar memory objects. We use

/// the term ``array'' to describe memory objects that consist of a set of

/// individual data elements arranged in a multi-dimensional grid. A scalar

/// memory object describes an individual data element and is used to model

/// the definition and uses of llvm::Values.

///

/// The polyhedral model does traditionally not reason about SSA values. To

/// reason about llvm::Values we model them "as if" they were zero-dimensional

/// memory objects, even though they were not actually allocated in (main)

/// memory.  Memory for such objects is only alloca[ed] at CodeGeneration

/// time. To relate the memory slots used during code generation with the

/// llvm::Values they belong to the new names for these corresponding stack

/// slots are derived by appending suffixes (currently ".s2a" and ".phiops")

/// to the name of the original llvm::Value. To describe how def/uses are

/// modeled exactly we use these suffixes here as well.

///

/// There are currently four different kinds of memory objects:

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

};

/// Maps from a loop to the affine function expressing its backedge taken count.

/// The backedge taken count already enough to express iteration domain as we

/// only allow loops with canonical induction variable.

/// A canonical induction variable is:

/// an integer recurrence that starts at 0 and increments by one each time

/// through the loop.

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

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

/// A class to store information about arrays in the SCoP.

///

/// Objects are accessible via the ScoP, MemoryAccess or the id associated with

/// the MemoryAccess access function.

///

class ScopArrayInfo final {

public:

  /// 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; }

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

  /// Dump a readable representation to stderr.

  void dump() const;

#endif

  /// 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;

private:

  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;

};

/// Represent memory accesses in statements.

class MemoryAccess final {

  friend class Scop;

  friend class ScopStmt;

  friend class ScopBuilder;

public:

  /// 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>;

private:

  /// 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();

public:

  /// 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);