blob: d3aba3d8f9c6632edc55eb982861895ec14eb808 [file] [log] [blame]
//===------ 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/ADT/MapVector.h"
#include "llvm/Analysis/RegionPass.h"
#include "isl/ctx.h"
#include <forward_list>
#include <deque>
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_ast_build;
struct isl_constraint;
struct isl_pw_multi_aff;
struct isl_schedule;
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 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.
ScopArrayInfo(Value *BasePtr, Type *ElementType, 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 Get the type of the elements stored in this array.
Type *getElementType() const { return ElementType; }
/// @brief Get element size in bytes.
int getElemSizeInBytes() const;
/// @brief Get the name of this memory reference.
std::string getName() const;
/// @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 of the elements stored in this array.
Type *ElementType;
/// @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 &) = delete;
const MemoryAccess &operator=(const MemoryAccess &) = delete;
isl_map *AccessRelation;
enum AccessType AccType;
/// @brief The base address (e.g., A for A[i+j]).
Value *BaseAddr;
std::string BaseName;
__isl_give 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;
/// @brief A unique identifier for this memory access.
///
/// The identifier is unique between all memory accesses belonging to the same
/// scop statement.
isl_id *Id;
void assumeNoOutOfBound(const IRAccess &Access);
/// @brief Compute bounds on an over approximated access relation.
///
/// @param ElementSize The size of one element accessed.
void computeBoundsOnAccessRelation(unsigned ElementSize);
/// @brief Get the original access function as read from IR.
__isl_give 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_give isl_map *getNewAccessRelation() const;
/// @brief Fold the memory access to consider parameteric 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 preferrable. 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.
__isl_give isl_map *foldAccess(const IRAccess &Access,
__isl_take isl_map *AccessRelation,
ScopStmt *Statement);
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.
/// @param Identifier An identifier that is unique for all memory accesses
/// belonging to the same scop statement.
MemoryAccess(const IRAccess &Access, Instruction *AccInst,
ScopStmt *Statement, const ScopArrayInfo *SAI, int Identifier);
~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_take 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_give 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 Get identifier for the memory access.
///
/// This identifier is unique for all accesses that belong to the same scop
/// statement.
__isl_give isl_id *getId() const;
/// @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 {
public:
/// @brief List to hold all (scalar) memory accesses mapped to an instruction.
using MemoryAccessList = std::forward_list<MemoryAccess>;
ScopStmt(const ScopStmt &) = delete;
const ScopStmt &operator=(const ScopStmt &) = delete;
/// Create the ScopStmt from a BasicBlock.
ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion,
BasicBlock &bb, SmallVectorImpl<Loop *> &NestLoops);
/// Create an overapproximating ScopStmt for the region @p R.
ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion, Region &R,
SmallVectorImpl<Loop *> &NestLoops);
private:
/// 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 memory accesses of this statement.
///
/// The only side effects of a statement are its memory accesses.
typedef SmallVector<MemoryAccess *, 8> MemoryAccessVec;
MemoryAccessVec MemAccs;
/// @brief Mapping from instructions to (scalar) memory accesses.
DenseMap<const Instruction *, MemoryAccessList *> InstructionToAccess;
//@}
/// @brief 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.
///
///{
/// @brief The BasicBlock represented by this statement (in the affine case).
BasicBlock *BB;
/// @brief The region represented by this statement (in the non-affine case).
Region *R;
///}
/// @brief The isl AST build for the new generated AST.
isl_ast_build *Build;
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);
/// @brief Create the accesses for instructions in @p Block.
///
/// @param tempScop The template SCoP.
/// @param Block The basic block for which accesses should be
/// created.
/// @param isApproximated Flag to indicate blocks that might not be executed,
/// hence for which write accesses need to be modeled as
/// may-write accesses.
void buildAccesses(TempScop &tempScop, BasicBlock *Block,
bool isApproximated = false);
/// @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 @p Block and derive assumptions about parameter values.
void deriveAssumptions(BasicBlock *Block);
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_give isl_id *getDomainId() const;
/// @brief Get an isl string representing this domain.
std::string getDomainStr() const;
/// @brief Get the schedule function of this ScopStmt.
///
/// @return The schedule function of this ScopStmt.
__isl_give isl_map *getSchedule() const;
/// @brief Get an isl string representing this schedule.
std::string getScheduleStr() const;
/// @brief 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; }
/// @brief Return true if this statement represents a single basic block.
bool isBlockStmt() const { return BB != nullptr; }
/// @brief 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; }
/// @brief Return true if this statement represents a whole region.
bool isRegionStmt() const { return R != nullptr; }
/// @brief Return the (scalar) memory accesses for @p Inst.
const MemoryAccessList &getAccessesFor(const Instruction *Inst) const {
MemoryAccessList *MAL = lookupAccessesFor(Inst);
assert(MAL && "Cannot get memory accesses because they do not exist!");
return *MAL;
}
/// @brief Return the (scalar) memory accesses for @p Inst if any.
MemoryAccessList *lookupAccessesFor(const Instruction *Inst) const {
auto It = InstructionToAccess.find(Inst);
return It == InstructionToAccess.end() ? nullptr : It->getSecond();
}
/// @brief Return the __first__ (scalar) memory access for @p Inst.
const MemoryAccess &getAccessFor(const Instruction *Inst) const {
MemoryAccess *MA = lookupAccessFor(Inst);
assert(MA && "Cannot get memory access because it does not exist!");
return *MA;
}
/// @brief Return the __first__ (scalar) memory access for @p Inst if any.
MemoryAccess *lookupAccessFor(const Instruction *Inst) const {
auto It = InstructionToAccess.find(Inst);
return It == InstructionToAccess.end() ? nullptr
: &It->getSecond()->front();
}
void setBasicBlock(BasicBlock *Block) {
// TODO: Handle the case where the statement is a region statement, thus
// the entry block was split and needs to be changed in the region R.
assert(BB && "Cannot set a block for a region statement");
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;
Scop *getParent() { return &Parent; }
const Scop *getParent() const { return &Parent; }
const char *getBaseName() const;
/// @brief Set the isl AST build.
void setAstBuild(__isl_keep isl_ast_build *B) { Build = B; }
/// @brief Get the isl AST build.
__isl_keep isl_ast_build *getAstBuild() const { return Build; }
/// @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 &) = delete;
const Scop &operator=(const Scop &) = delete;
ScalarEvolution *SE;
/// The underlying Region.
Region &R;
/// Flag to indicate that the scheduler actually optimized the SCoP.
bool IsOptimized;
/// Max loop depth.
unsigned MaxLoopDepth;
typedef std::deque<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;
typedef MapVector<const Value *, std::unique_ptr<ScopArrayInfo>>
ArrayInfoMapTy;
/// @brief A map to remember ScopArrayInfo objects for all base pointers.
ArrayInfoMapTy 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 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;
/// @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, ScopDetection &SD,
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();
/// @brief Create a new SCoP statement for either @p BB or @p R.
///
/// Either @p BB or @p R should be non-null. A new statement for the non-null
/// argument will be created and added to the statement vector and map.
///
/// @param BB The basic block we build the statement for (or null)
/// @param R The region we build the statement for (or null).
/// @param tempScop The temp SCoP we use as model.
/// @param CurRegion The SCoP region.
/// @param NestLoops A vector of all surrounding loops.
ScopStmt *addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop,
const Region &CurRegion,
SmallVectorImpl<Loop *> &NestLoops);
/// @brief Build Scop and ScopStmts from a given TempScop.
///
/// @param TempScop The temporary scop that is translated into an actual
/// scop.
/// @param CurRegion The subregion of the current scop that we are currently
/// translating.
/// @param NestLoop The set of loops that surround the current subregion.
/// @param LI The LoopInfo object.
/// @param SD The ScopDetection object.
__isl_give isl_schedule *buildScop(TempScop &TempScop,
const Region &CurRegion,
SmallVectorImpl<Loop *> &NestLoops,
LoopInfo &LI, ScopDetection &SD);
/// @name Helper function for printing the Scop.
///
///{
void printContext(raw_ostream &OS) const;
void printArrayInfo(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);
int getNumArrays() { return ScopArrayInfoMap.size(); }
typedef iterator_range<ArrayInfoMapTy::iterator> array_range;
typedef iterator_range<ArrayInfoMapTy::const_iterator> const_array_range;
inline array_range arrays() {
return array_range(ScopArrayInfoMap.begin(), ScopArrayInfoMap.end());
}
inline const_array_range arrays() const {
return const_array_range(ScopArrayInfoMap.begin(), ScopArrayInfoMap.end());
}
/// @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 Mark the SCoP as optimized by the scheduler.
void markAsOptimized() { IsOptimized = true; }
/// @brief Check if the SCoP has been optimized by the scheduler.
bool isOptimized() const { return IsOptimized; }
/// @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 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;
/// @brief Return the number of statements in the SCoP.
size_t getSize() const { return Stmts.size(); }
/// @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.
///
/// @param ElementType The type of the elements stored in this array.
const ScopArrayInfo *
getOrCreateScopArrayInfo(Value *BasePtr, Type *ElementType,
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() const;
/// @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() const;
/// @brief Get a schedule tree describing the schedule of all statements.
__isl_give isl_schedule *getScheduleTree() const;
/// @brief Update the current schedule
///
/// @brief NewSchedule The new schedule (given as a flat union-map).
void setSchedule(__isl_take isl_union_map *NewSchedule);
/// @brief Update the current schedule
///
/// @brief NewSchedule The new schedule (given as schedule tree).
void setScheduleTree(__isl_take isl_schedule *NewSchedule);
/// @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 &) = delete;
const ScopInfo &operator=(const ScopInfo &) = delete;
// 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