final/include/polly/ScopInfo.h

//===------ polly/ScopInfo.h - Create Scops from LLVM IR --------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Create a polyhedral description for a static control flow region.
//
// The pass creates a polyhedral description of the Scops detected by the Scop
// detection derived from their LLVM-IR code.
//
// This representation is shared among several tools in the polyhedral
// community, which are e.g. CLooG, Pluto, Loopo, Graphite.
//
//===----------------------------------------------------------------------===//

#ifndef POLLY_SCOP_INFO_H
#define POLLY_SCOP_INFO_H

#include "polly/ScopDetection.h"

#include "llvm/Analysis/RegionPass.h"

#include "isl/ctx.h"

using namespace llvm;

namespace llvm {
class Loop;
class LoopInfo;
class PHINode;
class ScalarEvolution;
class SCEV;
class SCEVAddRecExpr;
class Type;
}

struct isl_ctx;
struct isl_map;
struct isl_basic_map;
struct isl_id;
struct isl_set;
struct isl_union_set;
struct isl_union_map;
struct isl_space;
struct isl_constraint;
struct isl_pw_multi_aff;

namespace polly {

class IRAccess;
class Scop;
class ScopStmt;
class ScopInfo;
class TempScop;
class SCEVAffFunc;
class Comparison;

/// @brief 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 {
public:
  /// @brief Construct a ScopArrayInfo object.
  ///
  /// @param BasePtr        The array base pointer.
  /// @param AccessType     The type used to access this array.
  /// @param IslCtx         The isl context used to create the base pointer id.
  /// @param DimensionSizes A vector containing the size of each dimension.
  ScopArrayInfo(Value *BasePtr, Type *AccessType, isl_ctx *IslCtx,
                const SmallVector<const SCEV *, 4> &DimensionSizes);

  /// @brief Destructor to free the isl id of the base pointer.
  ~ScopArrayInfo();

  /// @brief Return the base pointer.
  Value *getBasePtr() const { return BasePtr; }

  /// @brief Return the number of dimensions.
  unsigned getNumberOfDimensions() const { return DimensionSizes.size(); }

  /// @brief Return the size of dimension @p dim.
  const SCEV *getDimensionSize(unsigned dim) const {
    assert(dim < getNumberOfDimensions() && "Invalid dimension");
    return DimensionSizes[dim];
  }

  /// @brief Return the type used to access this array in the SCoP.
  Type *getType() const { return AccessType; }

  /// @brief Return the isl id for the base pointer.
  __isl_give isl_id *getBasePtrId() const;

  /// @brief Dump a readable representation to stderr.
  void dump() const;

  /// @brief Print a readable representation to @p OS.
  void print(raw_ostream &OS) const;

  /// @brief Access the ScopArrayInfo associated with an access function.
  static const ScopArrayInfo *
  getFromAccessFunction(__isl_keep isl_pw_multi_aff *PMA);

  /// @brief Access the ScopArrayInfo associated with an isl Id.
  static const ScopArrayInfo *getFromId(__isl_take isl_id *Id);

private:
  /// @brief The base pointer.
  Value *BasePtr;

  /// @brief The type used to access this array.
  Type *AccessType;

  /// @brief The isl id for the base pointer.
  isl_id *Id;

  /// @brief The sizes of each dimension.
  SmallVector<const SCEV *, 4> DimensionSizes;
};

/// @brief Represent memory accesses in statements.
class MemoryAccess {
public:
  /// @brief 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, MUST_WRITE, MAY_WRITE };

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

private:
  MemoryAccess(const MemoryAccess &) LLVM_DELETED_FUNCTION;
  const MemoryAccess &operator=(const MemoryAccess &) LLVM_DELETED_FUNCTION;

  isl_map *AccessRelation;
  enum AccessType AccType;

  /// @brief The base address (e.g., A for A[i+j]).
  Value *BaseAddr;

  std::string BaseName;
  isl_basic_map *createBasicAccessMap(ScopStmt *Statement);
  ScopStmt *Statement;

  /// @brief 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 lifing the equality check in ScopInfo,
  /// 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;

  /// @brief The access instruction of this memory access.
  Instruction *Inst;

  /// Updated access relation read from JSCOP file.
  isl_map *newAccessRelation;

  void assumeNoOutOfBound(const IRAccess &Access);

  /// @brief Get the original access function as read from IR.
  isl_map *getOriginalAccessRelation() const;

  /// @brief Return the space in which the access relation lives in.
  __isl_give isl_space *getOriginalAccessRelationSpace() const;

  /// @brief Get the new access function imported or set by a pass
  isl_map *getNewAccessRelation() const;

public:
  /// @brief Create a memory access from an access in LLVM-IR.
  ///
  /// @param Access    The memory access.
  /// @param AccInst   The access instruction.
  /// @param Statement The statement that contains the access.
  /// @param SAI       The ScopArrayInfo object for this base pointer.
  MemoryAccess(const IRAccess &Access, Instruction *AccInst,
               ScopStmt *Statement, const ScopArrayInfo *SAI);

  ~MemoryAccess();

  /// @brief Get the type of a memory access.
  enum AccessType getType() { return AccType; }

  /// @brief Is this a reduction like access?
  bool isReductionLike() const { return RedType != RT_NONE; }

  /// @brief Is this a read memory access?
  bool isRead() const { return AccType == MemoryAccess::READ; }

  /// @brief Is this a must-write memory access?
  bool isMustWrite() const { return AccType == MemoryAccess::MUST_WRITE; }

  /// @brief Is this a may-write memory access?
  bool isMayWrite() const { return AccType == MemoryAccess::MAY_WRITE; }

  /// @brief Is this a write memory access?
  bool isWrite() const { return isMustWrite() || isMayWrite(); }

  /// @brief Check if a new access relation was imported or set by a pass.
  bool hasNewAccessRelation() const { return newAccessRelation; }

  /// @brief 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 *getAccessRelation() const {
    return hasNewAccessRelation() ? getNewAccessRelation()
                                  : getOriginalAccessRelation();
  }

  /// @brief Return the access relation after the schedule was applied.
  __isl_give isl_pw_multi_aff *
  applyScheduleToAccessRelation(__isl_keep isl_union_map *Schedule) const;

  /// @brief Get an isl string representing the access function read from IR.
  std::string getOriginalAccessRelationStr() const;

  /// @brief Get the base address of this access (e.g. A for A[i+j]).
  Value *getBaseAddr() const { return BaseAddr; }

  /// @brief Get the base array isl_id for this access.
  __isl_give isl_id *getArrayId() const;

  /// @brief Get the ScopArrayInfo object for the base address.
  const ScopArrayInfo *getScopArrayInfo() const;

  /// @brief Return a string representation of the accesse's reduction type.
  const std::string getReductionOperatorStr() const;

  /// @brief Return a string representation of the reduction type @p RT.
  static const std::string getReductionOperatorStr(ReductionType RT);

  const std::string &getBaseName() const { return BaseName; }

  /// @brief Return the access instruction of this memory access.
  Instruction *getAccessInstruction() const { return Inst; }

  /// 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_take const 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_take const 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_take const 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_take const isl_map *Schedule) const;

  /// @brief Check if this is a scalar memory access.
  bool isScalar() const;

  /// @brief Get the statement that contains this memory access.
  ScopStmt *getStatement() const { return Statement; }

  /// @brief Get the reduction type of this access
  ReductionType getReductionType() const { return RedType; }

  /// @brief Set the updated access relation read from JSCOP file.
  void setNewAccessRelation(__isl_take isl_map *newAccessRelation);

  /// @brief Mark this a reduction like access
  void markAsReductionLike(ReductionType RT) { RedType = RT; }

  /// @brief Align the parameters in the access relation to the scop context
  void realignParams();

  /// @brief Print the MemoryAccess.
  ///
  /// @param OS The output stream the MemoryAccess is printed to.
  void print(raw_ostream &OS) const;

  /// @brief Print the MemoryAccess to stderr.
  void dump() const;
};

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

///===----------------------------------------------------------------------===//
/// @brief Statement of the Scop
///
/// A Scop statement represents an instruction in the Scop.
///
/// It is further described by its iteration domain, its schedule and its data
/// accesses.
/// At the moment every statement represents a single basic block of LLVM-IR.
class ScopStmt {
  //===-------------------------------------------------------------------===//
  ScopStmt(const ScopStmt &) LLVM_DELETED_FUNCTION;
  const ScopStmt &operator=(const ScopStmt &) LLVM_DELETED_FUNCTION;

  /// Polyhedral description
  //@{

  /// The Scop containing this ScopStmt
  Scop &Parent;

  /// 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 scattering map describes the execution order of the statement
  /// instances.
  ///
  /// A statement and its iteration domain do not give any information about the
  /// order in time in which the different statement instances are executed.
  /// This information is provided by the scattering.
  ///
  /// The scattering maps every instance of each statement into a multi
  /// dimensional scattering space. This space can be seen as a multi
  /// dimensional clock.
  ///
  /// Example:
  ///
  /// <S,(5,4)>  may be mapped to (5,4) by this scattering:
  ///
  /// s0 = i (Year of execution)
  /// s1 = j (Day of execution)
  ///
  /// or to (9, 20) by this scattering:
  ///
  /// s0 = i + j (Year of execution)
  /// s1 = 20 (Day of execution)
  ///
  /// The order statement instances are executed is defined by the
  /// scattering vectors they are mapped to. A statement instance
  /// <A, (i, j, ..)> is executed before a statement instance <B, (i', ..)>, if
  /// the scattering vector of A is lexicographic smaller than the scattering
  /// vector of B.
  isl_map *Scattering;

  /// The memory accesses of this statement.
  ///
  /// The only side effects of a statement are its memory accesses.
  typedef SmallVector<MemoryAccess *, 8> MemoryAccessVec;
  MemoryAccessVec MemAccs;
  std::map<const Instruction *, MemoryAccess *> InstructionToAccess;

  //@}

  /// The BasicBlock represented by this statement.
  BasicBlock *BB;

  std::vector<Loop *> NestLoops;

  std::string BaseName;

  /// Build the statement.
  //@{
  __isl_give isl_set *buildConditionSet(const Comparison &Cmp);
  __isl_give isl_set *addConditionsToDomain(__isl_take isl_set *Domain,
                                            TempScop &tempScop,
                                            const Region &CurRegion);
  __isl_give isl_set *addLoopBoundsToDomain(__isl_take isl_set *Domain,
                                            TempScop &tempScop);
  __isl_give isl_set *buildDomain(TempScop &tempScop, const Region &CurRegion);
  void buildScattering(SmallVectorImpl<unsigned> &Scatter);
  void buildAccesses(TempScop &tempScop);

  /// @brief Detect and mark reductions in the ScopStmt
  void checkForReductions();

  /// @brief Collect loads which might form a reduction chain with @p StoreMA
  void
  collectCandiateReductionLoads(MemoryAccess *StoreMA,
                                llvm::SmallVectorImpl<MemoryAccess *> &Loads);
  //@}

  /// @brief Derive assumptions about parameter values from GetElementPtrInst
  ///
  /// In case a GEP instruction references into a fixed size array e.g., an
  /// access A[i][j] into an array A[100x100], LLVM-IR does not guarantee that
  /// the subscripts always compute values that are within array bounds. In this
  /// function we derive the set of parameter values for which all accesses are
  /// within bounds and add the assumption that the scop is only every executed
  /// with this set of parameter values.
  ///
  /// Example:
  ///
  ///   void foo(float A[][20], long n, long m {
  ///     for (long i = 0; i < n; i++)
  ///       for (long j = 0; j < m; j++)
  ///         A[i][j] = ...
  ///
  /// This loop yields out-of-bound accesses if m is at least 20 and at the same
  /// time at least one iteration of the outer loop is executed. Hence, we
  /// assume:
  ///
  ///   n <= 0 or m <= 20.
  ///
  /// TODO: The location where the GEP instruction is executed is not
  /// necessarily the location where the memory is actually accessed. As a
  /// result scanning for GEP[s] is imprecise. Even though this is not a
  /// correctness problem, this imprecision may result in missed optimizations
  /// or non-optimal run-time checks.
  void deriveAssumptionsFromGEP(GetElementPtrInst *Inst);

  /// @brief Scan the scop and derive assumptions about parameter values.
  void deriveAssumptions();

  /// Create the ScopStmt from a BasicBlock.
  ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion,
           BasicBlock &bb, SmallVectorImpl<Loop *> &NestLoops,
           SmallVectorImpl<unsigned> &Scatter);

  friend class Scop;

public:
  ~ScopStmt();

  /// @brief Get an isl_ctx pointer.
  isl_ctx *getIslCtx() const;

  /// @brief Get the iteration domain of this ScopStmt.
  ///
  /// @return The iteration domain of this ScopStmt.
  __isl_give isl_set *getDomain() const;

  /// @brief Get the space of the iteration domain
  ///
  /// @return The space of the iteration domain
  __isl_give isl_space *getDomainSpace() const;

  /// @brief Get the id of the iteration domain space
  ///
  /// @return The id of the iteration domain space
  isl_id *getDomainId() const;

  /// @brief Get an isl string representing this domain.
  std::string getDomainStr() const;

  /// @brief Get the scattering function of this ScopStmt.
  ///
  /// @return The scattering function of this ScopStmt.
  __isl_give isl_map *getScattering() const;
  void setScattering(isl_map *scattering);

  /// @brief Get an isl string representing this scattering.
  std::string getScatteringStr() const;

  /// @brief Get the BasicBlock represented by this ScopStmt.
  ///
  /// @return The BasicBlock represented by this ScopStmt.
  BasicBlock *getBasicBlock() const { return BB; }

  const MemoryAccess &getAccessFor(const Instruction *Inst) const {
    MemoryAccess *A = lookupAccessFor(Inst);
    assert(A && "Cannot get memory access because it does not exist!");
    return *A;
  }

  MemoryAccess *lookupAccessFor(const Instruction *Inst) const {
    std::map<const Instruction *, MemoryAccess *>::const_iterator at =
        InstructionToAccess.find(Inst);
    return at == InstructionToAccess.end() ? NULL : at->second;
  }

  void setBasicBlock(BasicBlock *Block) { BB = Block; }

  typedef MemoryAccessVec::iterator iterator;
  typedef MemoryAccessVec::const_iterator 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(); }

  unsigned getNumParams() const;
  unsigned getNumIterators() const;
  unsigned getNumScattering() const;

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

  const char *getBaseName() const;

  /// @brief Restrict the domain of the statement.
  ///
  /// @param NewDomain The new statement domain.
  void restrictDomain(__isl_take isl_set *NewDomain);

  /// @brief Get the loop for a dimension.
  ///
  /// @param Dimension The dimension of the induction variable
  /// @return The loop at a certain dimension.
  const Loop *getLoopForDimension(unsigned Dimension) const;

  /// @brief Align the parameters in the statement to the scop context
  void realignParams();

  /// @brief Print the ScopStmt.
  ///
  /// @param OS The output stream the ScopStmt is printed to.
  void print(raw_ostream &OS) const;

  /// @brief Print the ScopStmt to stderr.
  void dump() const;
};

/// @brief Print ScopStmt S to raw_ostream O.
static inline raw_ostream &operator<<(raw_ostream &O, const ScopStmt &S) {
  S.print(O);
  return O;
}

///===----------------------------------------------------------------------===//
/// @brief Static Control Part
///
/// A Scop is the polyhedral representation of a control flow region detected
/// by the Scop detection. It is generated by translating the LLVM-IR and
/// abstracting its effects.
///
/// A Scop consists of a set of:
///
///   * A set of statements executed in the Scop.
///
///   * A set of global parameters
///   Those parameters are scalar integer values, which are constant during
///   execution.
///
///   * A context
///   This context contains information about the values the parameters
///   can take and relations between different parameters.
class Scop {
public:
  /// @brief Type to represent a pair of minimal/maximal access to an array.
  using MinMaxAccessTy = std::pair<isl_pw_multi_aff *, isl_pw_multi_aff *>;

  /// @brief Vector of minimal/maximal accesses to different arrays.
  using MinMaxVectorTy = SmallVector<MinMaxAccessTy, 4>;

  /// @brief Vector of minimal/maximal access vectors one for each alias group.
  using MinMaxVectorVectorTy = SmallVector<MinMaxVectorTy *, 4>;

private:
  Scop(const Scop &) LLVM_DELETED_FUNCTION;
  const Scop &operator=(const Scop &) LLVM_DELETED_FUNCTION;

  ScalarEvolution *SE;

  /// The underlying Region.
  Region &R;

  /// Max loop depth.
  unsigned MaxLoopDepth;

  typedef std::vector<ScopStmt *> StmtSet;
  /// The statements in this Scop.
  StmtSet Stmts;

  /// Parameters of this Scop
  typedef SmallVector<const SCEV *, 8> ParamVecType;
  ParamVecType Parameters;

  /// The isl_ids that are used to represent the parameters
  typedef std::map<const SCEV *, int> ParamIdType;
  ParamIdType ParameterIds;

  /// Isl context.
  isl_ctx *IslCtx;

  /// @brief A map from basic blocks to SCoP statements.
  DenseMap<BasicBlock *, ScopStmt *> StmtMap;

  /// Constraints on parameters.
  isl_set *Context;

  /// @brief A map to remember ScopArrayInfo objects for all base pointers.
  DenseMap<const Value *, const ScopArrayInfo *> ScopArrayInfoMap;

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

  /// @brief 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.
  MinMaxVectorVectorTy MinMaxAliasGroups;

  /// Create the static control part with a region, max loop depth of this
  /// region and parameters used in this region.
  Scop(TempScop &TempScop, LoopInfo &LI, ScalarEvolution &SE, isl_ctx *ctx);

  /// @brief Check if a basic block is trivial.
  ///
  /// A trivial basic block does not contain any useful calculation. Therefore,
  /// it does not need to be represented as a polyhedral statement.
  ///
  /// @param BB The basic block to check
  /// @param tempScop TempScop returning further information regarding the Scop.
  ///
  /// @return True if the basic block is trivial, otherwise false.
  static bool isTrivialBB(BasicBlock *BB, TempScop &tempScop);

  /// @brief Build the Context of the Scop.
  void buildContext();

  /// @brief Add the bounds of the parameters to the context.
  void addParameterBounds();

  /// @brief Simplify the assumed context.
  void simplifyAssumedContext();

  /// Build the Scop and Statement with precalculated scop information.
  void buildScop(TempScop &TempScop, const Region &CurRegion,
                 // Loops in Scop containing CurRegion
                 SmallVectorImpl<Loop *> &NestLoops,
                 // The scattering numbers
                 SmallVectorImpl<unsigned> &Scatter, LoopInfo &LI);

  /// @name Helper function for printing the Scop.
  ///
  ///{
  void printContext(raw_ostream &OS) const;
  void printStatements(raw_ostream &OS) const;
  void printAliasAssumptions(raw_ostream &OS) const;
  ///}

  friend class ScopInfo;

public:
  ~Scop();

  ScalarEvolution *getSE() const;

  /// @brief Get the count of parameters used in this Scop.
  ///
  /// @return The count of parameters used in this Scop.
  inline ParamVecType::size_type getNumParams() const {
    return Parameters.size();
  }

  /// @brief Get a set containing the parameters used in this Scop
  ///
  /// @return The set containing the parameters used in this Scop.
  inline const ParamVecType &getParams() const { return Parameters; }

  /// @brief Take a list of parameters and add the new ones to the scop.
  void addParams(std::vector<const SCEV *> NewParameters);

  /// @brief Return the isl_id that represents a certain parameter.
  ///
  /// @param Parameter A SCEV that was recognized as a Parameter.
  ///
  /// @return The corresponding isl_id or NULL otherwise.
  isl_id *getIdForParam(const SCEV *Parameter) const;

  /// @name Parameter Iterators
  ///
  /// These iterators iterate over all parameters of this Scop.
  //@{
  typedef ParamVecType::iterator param_iterator;
  typedef ParamVecType::const_iterator const_param_iterator;

  param_iterator param_begin() { return Parameters.begin(); }
  param_iterator param_end() { return Parameters.end(); }
  const_param_iterator param_begin() const { return Parameters.begin(); }
  const_param_iterator param_end() const { return Parameters.end(); }
  //@}

  /// @brief Get the maximum region of this static control part.
  ///
  /// @return The maximum region of this static control part.
  inline const Region &getRegion() const { return R; }
  inline Region &getRegion() { return R; }

  /// @brief Get the maximum depth of the loop.
  ///
  /// @return The maximum depth of the loop.
  inline unsigned getMaxLoopDepth() const { return MaxLoopDepth; }

  /// @brief Get the scattering dimension number of this Scop.
  ///
  /// @return The scattering dimension number of this Scop.
  inline unsigned getScatterDim() const {
    unsigned maxScatterDim = 0;

    for (const_iterator SI = begin(), SE = end(); SI != SE; ++SI)
      maxScatterDim = std::max(maxScatterDim, (*SI)->getNumScattering());

    return maxScatterDim;
  }

  /// @brief Get the name of this Scop.
  std::string getNameStr() const;

  /// @brief Get the constraint on parameter of this Scop.
  ///
  /// @return The constraint on parameter of this Scop.
  __isl_give isl_set *getContext() const;
  __isl_give isl_space *getParamSpace() const;

  /// @brief Get the assumed context for this Scop.
  ///
  /// @return The assumed context of this Scop.
  __isl_give isl_set *getAssumedContext() const;

  /// @brief Add assumptions to assumed context.
  ///
  /// The assumptions added will be assumed to hold during the execution of the
  /// scop. However, as they are generally not statically provable, at code
  /// generation time run-time checks will be generated that ensure the
  /// assumptions hold.
  ///
  /// WARNING: We currently exploit in simplifyAssumedContext the knowledge
  ///          that assumptions do not change the set of statement instances
  ///          executed.
  ///
  /// @param Set A set describing relations between parameters that are assumed
  ///            to hold.
  void addAssumption(__isl_take isl_set *Set);

  /// @brief Build all alias groups for this SCoP.
  ///
  /// @returns True if __no__ error occurred, false otherwise.
  bool buildAliasGroups(AliasAnalysis &AA);

  //// @brief Drop all constant dimensions from statment schedules.
  ///
  ///  Schedule dimensions that are constant accross the scop do not carry
  ///  any information, but would cost compile time due to the increased number
  ///  of scheduling dimensions. To not pay this cost, we remove them.
  void dropConstantScheduleDims();

  /// @brief Return all alias groups for this SCoP.
  const MinMaxVectorVectorTy &getAliasGroups() const {
    return MinMaxAliasGroups;
  }

  /// @brief Get an isl string representing the context.
  std::string getContextStr() const;

  /// @brief Get an isl string representing the assumed context.
  std::string getAssumedContextStr() const;

  /// @brief Return the stmt for the given @p BB or nullptr if none.
  ScopStmt *getStmtForBasicBlock(BasicBlock *BB) const;

  /// @name Statements Iterators
  ///
  /// These iterators iterate over all statements of this Scop.
  //@{
  typedef StmtSet::iterator iterator;
  typedef StmtSet::const_iterator const_iterator;

  iterator begin() { return Stmts.begin(); }
  iterator end() { return Stmts.end(); }
  const_iterator begin() const { return Stmts.begin(); }
  const_iterator end() const { return Stmts.end(); }

  typedef StmtSet::reverse_iterator reverse_iterator;
  typedef StmtSet::const_reverse_iterator const_reverse_iterator;

  reverse_iterator rbegin() { return Stmts.rbegin(); }
  reverse_iterator rend() { return Stmts.rend(); }
  const_reverse_iterator rbegin() const { return Stmts.rbegin(); }
  const_reverse_iterator rend() const { return Stmts.rend(); }
  //@}

  /// @brief Return the (possibly new) ScopArrayInfo object for @p Access.
  const ScopArrayInfo *
  getOrCreateScopArrayInfo(Value *BasePtr, Type *AccessType,
                           const SmallVector<const SCEV *, 4> &Sizes);

  /// @brief Return the cached ScopArrayInfo object for @p BasePtr.
  const ScopArrayInfo *getScopArrayInfo(Value *BasePtr);

  void setContext(isl_set *NewContext);

  /// @brief Align the parameters in the statement to the scop context
  void realignParams();

  /// @brief Print the static control part.
  ///
  /// @param OS The output stream the static control part is printed to.
  void print(raw_ostream &OS) const;

  /// @brief Print the ScopStmt to stderr.
  void dump() const;

  /// @brief Get the isl context of this static control part.
  ///
  /// @return The isl context of this static control part.
  isl_ctx *getIslCtx() const;

  /// @brief Get a union set containing the iteration domains of all statements.
  __isl_give isl_union_set *getDomains();

  /// @brief Get a union map of all may-writes performed in the SCoP.
  __isl_give isl_union_map *getMayWrites();

  /// @brief Get a union map of all must-writes performed in the SCoP.
  __isl_give isl_union_map *getMustWrites();

  /// @brief Get a union map of all writes performed in the SCoP.
  __isl_give isl_union_map *getWrites();

  /// @brief Get a union map of all reads performed in the SCoP.
  __isl_give isl_union_map *getReads();

  /// @brief Get the schedule of all the statements in the SCoP.
  __isl_give isl_union_map *getSchedule();

  /// @brief Intersects the domains of all statements in the SCoP.
  ///
  /// @return true if a change was made
  bool restrictDomains(__isl_take isl_union_set *Domain);
};

/// @brief Print Scop scop to raw_ostream O.
static inline raw_ostream &operator<<(raw_ostream &O, const Scop &scop) {
  scop.print(O);
  return O;
}

///===---------------------------------------------------------------------===//
/// @brief Build the Polly IR (Scop and ScopStmt) on a Region.
///
class ScopInfo : public RegionPass {
  //===-------------------------------------------------------------------===//
  ScopInfo(const ScopInfo &) LLVM_DELETED_FUNCTION;
  const ScopInfo &operator=(const ScopInfo &) LLVM_DELETED_FUNCTION;

  // The Scop
  Scop *scop;
  isl_ctx *ctx;

  void clear() {
    if (scop) {
      delete scop;
      scop = 0;
    }
  }

public:
  static char ID;
  explicit ScopInfo();
  ~ScopInfo();

  /// @brief Try to build the Polly IR of static control part on the current
  ///        SESE-Region.
  ///
  /// @return If the current region is a valid for a static control part,
  ///         return the Polly IR representing this static control part,
  ///         return null otherwise.
  Scop *getScop() { return scop; }
  const Scop *getScop() const { return scop; }

  /// @name RegionPass interface
  //@{
  virtual bool runOnRegion(Region *R, RGPassManager &RGM);
  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
  virtual void releaseMemory() { clear(); }
  virtual void print(raw_ostream &OS, const Module *) const {
    if (scop)
      scop->print(OS);
    else
      OS << "Invalid Scop!\n";
  }
  //@}
};

} // end namespace polly

namespace llvm {
class PassRegistry;
void initializeScopInfoPass(llvm::PassRegistry &);
}

#endif