From ffa73bd44c44d17e0a33297c98c8c4d1f319cf0a Mon Sep 17 00:00:00 2001 From: Johannes Doerfert Date: Fri, 20 Jun 2014 16:58:12 +0000 Subject: [PATCH] Reduction like is now a memory access property - Remove the statement reduction like property + Add the reduction like property to memory accesses llvm-svn: 211372 --- polly/include/polly/ScopInfo.h | 60 ++++++++++++++++++++------------------ polly/lib/Analysis/Dependences.cpp | 17 ++++++----- polly/lib/Analysis/ScopInfo.cpp | 8 ++--- 3 files changed, 46 insertions(+), 39 deletions(-) diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h index f7f9ff9..24b92ae 100644 --- a/polly/include/polly/ScopInfo.h +++ b/polly/include/polly/ScopInfo.h @@ -97,6 +97,32 @@ private: void setBaseName(); ScopStmt *Statement; + /// @brief Flag to indicate reduction like accesses + /// + /// 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. + bool IsReductionLike = false; + const Instruction *Inst; /// Updated access relation read from JSCOP file. @@ -122,6 +148,9 @@ public: /// @brief Get the type of a memory access. enum AccessType getType() { return Type; } + /// @brief Is this a reduction like access? + bool isReductionLike() const { return IsReductionLike; } + /// @brief Is this a read memory access? bool isRead() const { return Type == MemoryAccess::READ; } @@ -181,6 +210,9 @@ public: /// @brief Set the updated access relation read from JSCOP file. void setNewAccessRelation(isl_map *newAccessRelation); + /// @brief Mark this a reduction like access + void markReductionLike() { IsReductionLike = true; } + /// @brief Align the parameters in the access relation to the scop context void realignParams(); @@ -270,31 +302,6 @@ class ScopStmt { MemoryAccessVec MemAccs; std::map InstructionToAccess; - /// @brief Flag to indicate reduction like statements. - /// - /// A statement is reduction like if it contains exactly one load and one - /// store both accessing 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. - bool IsReductionLike = false; //@} /// The BasicBlock represented by this statement. @@ -332,9 +339,6 @@ class ScopStmt { public: ~ScopStmt(); - /// @brief Return true iff this statement is a reduction like statement - bool isReductionLike() const { return IsReductionLike; } - /// @brief Get an isl_ctx pointer. isl_ctx *getIslCtx() const; diff --git a/polly/lib/Analysis/Dependences.cpp b/polly/lib/Analysis/Dependences.cpp index 95c344a..59a166a 100644 --- a/polly/lib/Analysis/Dependences.cpp +++ b/polly/lib/Analysis/Dependences.cpp @@ -251,13 +251,16 @@ void Dependences::calculateDependences(Scop &S) { // Step 1) RED = isl_union_map_empty(isl_union_map_get_space(RAW)); - for (auto *Stmt : S) { - if (!Stmt->isReductionLike()) - continue; - isl_set *Domain = Stmt->getDomain(); - isl_map *Identity = - isl_map_from_domain_and_range(isl_set_copy(Domain), Domain); - RED = isl_union_map_add_map(RED, Identity); + for (ScopStmt *Stmt : S) { + for (MemoryAccess *MA : *Stmt) { + if (!MA->isReductionLike()) + continue; + isl_set *AccDom = isl_map_domain(MA->getAccessRelation()); + isl_map *Identity = + isl_map_from_domain_and_range(isl_set_copy(AccDom), AccDom); + RED = isl_union_map_add_map(RED, Identity); + break; + } } // Step 2) diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp index 766543d..4a6818a 100644 --- a/polly/lib/Analysis/ScopInfo.cpp +++ b/polly/lib/Analysis/ScopInfo.cpp @@ -397,6 +397,7 @@ MemoryAccess::MemoryAccess(const Value *BaseAddress, ScopStmt *Statement) } void MemoryAccess::print(raw_ostream &OS) const { + OS.indent(8) << "Reduction like: " << isReductionLike() << "\n"; switch (Type) { case READ: OS.indent(12) << "ReadAccess := \n"; @@ -741,8 +742,9 @@ void ScopStmt::checkForReduction() { BinOp->getOpcode() == Instruction::FMul)) return; - // Valid reduction like statement - IsReductionLike = true; + // Valid reduction like access + MemAccs[0]->markReductionLike(); + MemAccs[1]->markReductionLike(); } std::string ScopStmt::getDomainStr() const { return stringFromIslObj(Domain); } @@ -798,8 +800,6 @@ ScopStmt::~ScopStmt() { void ScopStmt::print(raw_ostream &OS) const { OS << "\t" << getBaseName() << "\n"; - OS.indent(8) << "Reduction like: " << isReductionLike() << "\n"; - OS.indent(12) << "Domain :=\n"; if (Domain) { -- 2.7.4