diff options
19 files changed, 141 insertions, 61 deletions
diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h index 31f08402e32..6315c43f25b 100644 --- a/polly/include/polly/ScopInfo.h +++ b/polly/include/polly/ScopInfo.h @@ -84,6 +84,18 @@ public: /// 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; @@ -97,7 +109,7 @@ private: void setBaseName(); ScopStmt *Statement; - /// @brief Flag to indicate reduction like accesses + /// @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 @@ -121,7 +133,7 @@ private: /// 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; + ReductionType RedType = RT_NONE; const Instruction *Inst; @@ -149,7 +161,7 @@ public: enum AccessType getType() { return Type; } /// @brief Is this a reduction like access? - bool isReductionLike() const { return IsReductionLike; } + bool isReductionLike() const { return RedType != RT_NONE; } /// @brief Is this a read memory access? bool isRead() const { return Type == MemoryAccess::READ; } @@ -205,11 +217,14 @@ public: /// @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_map *newAccessRelation); /// @brief Mark this a reduction like access - void markReductionLike() { IsReductionLike = true; } + void markAsReductionLike(ReductionType RT) { RedType = RT; } /// @brief Align the parameters in the access relation to the scop context void realignParams(); @@ -223,6 +238,9 @@ public: void dump() const; }; +llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, + MemoryAccess::ReductionType RT); + //===----------------------------------------------------------------------===// /// @brief Statement of the Scop /// diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp index 4cc1e80b73f..b2674de6d90 100644 --- a/polly/lib/Analysis/ScopInfo.cpp +++ b/polly/lib/Analysis/ScopInfo.cpp @@ -273,6 +273,36 @@ int SCEVAffinator::getLoopDepth(const Loop *L) { return L->getLoopDepth() - outerLoop->getLoopDepth(); } +/// @brief Return the reduction type for a given binary operator +static MemoryAccess::ReductionType getReductionType(const BinaryOperator *BinOp, + const Instruction *Load) { + if (!BinOp) + return MemoryAccess::RT_NONE; + switch (BinOp->getOpcode()) { + case Instruction::FAdd: + if (!BinOp->hasUnsafeAlgebra()) + return MemoryAccess::RT_NONE; + // Fall through + case Instruction::Add: + return MemoryAccess::RT_ADD; + case Instruction::Or: + return MemoryAccess::RT_BOR; + case Instruction::Xor: + return MemoryAccess::RT_BXOR; + case Instruction::And: + return MemoryAccess::RT_BAND; + case Instruction::FMul: + if (!BinOp->hasUnsafeAlgebra()) + return MemoryAccess::RT_NONE; + // Fall through + case Instruction::Mul: + if (DisableMultiplicativeReductions) + return MemoryAccess::RT_NONE; + return MemoryAccess::RT_MUL; + default: + return MemoryAccess::RT_NONE; + } +} //===----------------------------------------------------------------------===// MemoryAccess::~MemoryAccess() { @@ -396,6 +426,31 @@ MemoryAccess::MemoryAccess(const Value *BaseAddress, ScopStmt *Statement) AccessRelation = isl_map_align_params(AccessRelation, ParamSpace); } +raw_ostream &polly::operator<<(raw_ostream &OS, + MemoryAccess::ReductionType RT) { + switch (RT) { + case MemoryAccess::RT_NONE: + OS << "NONE"; + break; + case MemoryAccess::RT_ADD: + OS << "ADD"; + break; + case MemoryAccess::RT_MUL: + OS << "MUL"; + break; + case MemoryAccess::RT_BOR: + OS << "BOR"; + break; + case MemoryAccess::RT_BXOR: + OS << "BXOR"; + break; + case MemoryAccess::RT_BAND: + OS << "BAND"; + break; + } + return OS; +} + void MemoryAccess::print(raw_ostream &OS) const { switch (Type) { case READ: @@ -408,7 +463,7 @@ void MemoryAccess::print(raw_ostream &OS) const { OS.indent(12) << "MayWriteAccess :=\t"; break; } - OS << "[Reduction like: " << isReductionLike() << "]\n"; + OS << "[Reduction Type: " << getReductionType() << "]\n"; OS.indent(16) << getAccessRelationStr() << ";\n"; } @@ -820,10 +875,15 @@ void ScopStmt::checkForReductions() { if (!Valid) continue; + const LoadInst *Load = + dyn_cast<const LoadInst>(CandidatePair.first->getAccessInstruction()); + MemoryAccess::ReductionType RT = + getReductionType(dyn_cast<BinaryOperator>(Load->user_back()), Load); + // If no overlapping access was found we mark the load and store as // reduction like. - CandidatePair.first->markReductionLike(); - CandidatePair.second->markReductionLike(); + CandidatePair.first->markAsReductionLike(RT); + CandidatePair.second->markAsReductionLike(RT); } } diff --git a/polly/test/ScopInfo/loop_affine_bound_0.ll b/polly/test/ScopInfo/loop_affine_bound_0.ll index 58b3350e4d0..b950b2f189c 100644 --- a/polly/test/ScopInfo/loop_affine_bound_0.ll +++ b/polly/test/ScopInfo/loop_affine_bound_0.ll @@ -59,6 +59,6 @@ return: ; preds = %bb.nph8, %bb3, %ent ; CHECK: [N, M] -> { Stmt_bb1[i0, i1] : i0 >= 0 and i0 <= 2 + 4N + 7M and i1 >= 0 and i1 <= 1 + 5N and N >= 0 }; ; CHECK: Scattering := ; CHECK: [N, M] -> { Stmt_bb1[i0, i1] -> scattering[0, i0, 0, i1, 0] }; -; CHECK: MustWriteAccess := [Reduction like: 0] +; CHECK: MustWriteAccess := [Reduction Type: NONE] ; CHECK: [N, M] -> { Stmt_bb1[i0, i1] -> MemRef_a[i0 + 128i1] }; ; CHECK: } diff --git a/polly/test/ScopInfo/loop_affine_bound_1.ll b/polly/test/ScopInfo/loop_affine_bound_1.ll index 603aec65991..daa598a55dc 100644 --- a/polly/test/ScopInfo/loop_affine_bound_1.ll +++ b/polly/test/ScopInfo/loop_affine_bound_1.ll @@ -58,6 +58,6 @@ return: ; preds = %bb3, %entry ; CHECK: [N, M] -> { Stmt_bb1[i0, i1] : i0 >= 0 and i0 <= 2 + 4N + 7M and i1 >= 0 and i1 <= 1 + 5N - i0 and i0 <= 1 + 5N }; ; CHECK: Scattering := ; CHECK: [N, M] -> { Stmt_bb1[i0, i1] -> scattering[0, i0, 0, i1, 0] }; -; CHECK: MustWriteAccess := [Reduction like: 0] +; CHECK: MustWriteAccess := [Reduction Type: NONE] ; CHECK: [N, M] -> { Stmt_bb1[i0, i1] -> MemRef_a[129i0 + 128i1] }; ; CHECK: } diff --git a/polly/test/ScopInfo/loop_affine_bound_2.ll b/polly/test/ScopInfo/loop_affine_bound_2.ll index 8ccbfedc9fc..7392eaa644d 100644 --- a/polly/test/ScopInfo/loop_affine_bound_2.ll +++ b/polly/test/ScopInfo/loop_affine_bound_2.ll @@ -69,6 +69,6 @@ return: ; preds = %bb3, %entry ; CHECK: [N, M] -> { Stmt_bb1[i0, i1] : i0 >= 0 and i0 <= 2 + 4N + 7M and i1 >= 0 and i1 <= 10 + 5N - 6M - 4i0 and 4i0 <= 10 + 5N - 6M }; ; CHECK: Scattering := ; CHECK: [N, M] -> { Stmt_bb1[i0, i1] -> scattering[0, i0, 0, i1, 0] }; -; CHECK: MustWriteAccess := [Reduction like: 0] +; CHECK: MustWriteAccess := [Reduction Type: NONE] ; CHECK: [N, M] -> { Stmt_bb1[i0, i1] -> MemRef_a[-1152 + 768M + 897i0 + 128i1] }; ; CHECK: } diff --git a/polly/test/ScopInfo/reduction_disabled_multiplicative.ll b/polly/test/ScopInfo/reduction_disabled_multiplicative.ll index 159e7f53305..4a3ccfadee4 100644 --- a/polly/test/ScopInfo/reduction_disabled_multiplicative.ll +++ b/polly/test/ScopInfo/reduction_disabled_multiplicative.ll @@ -1,12 +1,12 @@ ; RUN: opt -basicaa %loadPolly -polly-scops -analyze -polly-disable-multiplicative-reductions < %s | FileCheck %s ; -; CHECK: ReadAccess := [Reduction like: 1] +; CHECK: ReadAccess := [Reduction Type: ADD ; CHECK: { Stmt_for_body[i0] -> MemRef_sum[0] }; -; CHECK: MustWriteAccess := [Reduction like: 1] +; CHECK: MustWriteAccess := [Reduction Type: ADD ; CHECK: { Stmt_for_body[i0] -> MemRef_sum[0] }; -; CHECK: ReadAccess := [Reduction like: 0] +; CHECK: ReadAccess := [Reduction Type: NONE ; CHECK: { Stmt_for_body[i0] -> MemRef_prod[0] }; -; CHECK: MustWriteAccess := [Reduction like: 0] +; CHECK: MustWriteAccess := [Reduction Type: NONE ; CHECK: { Stmt_for_body[i0] -> MemRef_prod[0] }; ; ; int sum, prod; diff --git a/polly/test/ScopInfo/reduction_escaping_intermediate.ll b/polly/test/ScopInfo/reduction_escaping_intermediate.ll index c5f5cc03928..2c4f74c2adf 100644 --- a/polly/test/ScopInfo/reduction_escaping_intermediate.ll +++ b/polly/test/ScopInfo/reduction_escaping_intermediate.ll @@ -10,11 +10,11 @@ ; } ; } ; -; CHECK: Reduction like: 0 +; CHECK: Reduction Type: NONE ; CHECK: sums -; CHECK: Reduction like: 0 +; CHECK: Reduction Type: NONE ; CHECK: sums -; CHECK: Reduction like: 0 +; CHECK: Reduction Type: NONE ; CHECK: escape target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64" diff --git a/polly/test/ScopInfo/reduction_escaping_intermediate_2.ll b/polly/test/ScopInfo/reduction_escaping_intermediate_2.ll index ccf87f17483..2d8c09e6a48 100644 --- a/polly/test/ScopInfo/reduction_escaping_intermediate_2.ll +++ b/polly/test/ScopInfo/reduction_escaping_intermediate_2.ll @@ -10,15 +10,15 @@ ; } ; } ; -; CHECK: Reduction like: 0 +; CHECK: Reduction Type: NONE ; CHECK: sums -; CHECK: Reduction like: 0 +; CHECK: Reduction Type: NONE ; CHECK: sums -; CHECK: Reduction like: 0 +; CHECK: Reduction Type: NONE ; CHECK: escape -; CHECK: Reduction like: 0 +; CHECK: Reduction Type: NONE ; CHECK: sums -; CHECK: Reduction like: 0 +; CHECK: Reduction Type: NONE ; CHECK: escape target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64" diff --git a/polly/test/ScopInfo/reduction_invalid_different_operators.ll b/polly/test/ScopInfo/reduction_invalid_different_operators.ll index 81c02bc6717..c519c5f5c76 100644 --- a/polly/test/ScopInfo/reduction_invalid_different_operators.ll +++ b/polly/test/ScopInfo/reduction_invalid_different_operators.ll @@ -10,7 +10,8 @@ ; return sum + sth; ; } ; -; CHECK-NOT: Reduction like: 1 +; CHECK-NOT: Reduction Type: ADD +; CHECK-NOT: Reduction Type: MUL target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64" define i32 @f() { diff --git a/polly/test/ScopInfo/reduction_invalid_overlapping_accesses.ll b/polly/test/ScopInfo/reduction_invalid_overlapping_accesses.ll index a75e9de9a85..2c0db4db2a8 100644 --- a/polly/test/ScopInfo/reduction_invalid_overlapping_accesses.ll +++ b/polly/test/ScopInfo/reduction_invalid_overlapping_accesses.ll @@ -10,7 +10,8 @@ ; } ; } ; -; CHECK-NOT: Reduction like: 1 +; CHECK-NOT: Reduction Type: ADD +; CHECK-NOT: Reduction Type: MUL target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-n32-S64" define void @f(i32* %sums) { diff --git a/polly/test/ScopInfo/reduction_multiple_loops_array_sum.ll b/polly/test/ScopInfo/reduction_multiple_loops_array_sum.ll index 1f7013dd6d5..7a956ac7f52 100644 --- a/polly/test/ScopInfo/reduction_multiple_loops_array_sum.ll +++ b/polly/test/ScopInfo/reduction_multiple_loops_array_sum.ll @@ -1,21 +1,21 @@ ; RUN: opt -basicaa %loadPolly -polly-scops -analyze < %s | FileCheck %s ; ; CHECK: Stmt_for_body -; CHECK: Reduction like: 1 +; CHECK: Reduction Type: MUL ; CHECK: MemRef_sum -; CHECK: Reduction like: 1 +; CHECK: Reduction Type: MUL ; CHECK: MemRef_sum ; CHECK: Stmt_for_body3 -; CHECK: Reduction like: 0 +; CHECK: Reduction Type: NONE ; CHECK: MemRef_A -; CHECK: Reduction like: 1 +; CHECK: Reduction Type: ADD ; CHECK: MemRef_sum -; CHECK: Reduction like: 1 +; CHECK: Reduction Type: ADD ; CHECK: MemRef_sum ; CHECK: Stmt_for_end -; CHECK: Reduction like: 1 +; CHECK: Reduction Type: MUL ; CHECK: MemRef_sum -; CHECK: Reduction like: 1 +; CHECK: Reduction Type: MUL ; CHECK: MemRef_sum ; ; void f(int *restrict A, int *restrict sum) { diff --git a/polly/test/ScopInfo/reduction_multiple_loops_array_sum_1.ll b/polly/test/ScopInfo/reduction_multiple_loops_array_sum_1.ll index 5148492e1e4..4104aabcea7 100644 --- a/polly/test/ScopInfo/reduction_multiple_loops_array_sum_1.ll +++ b/polly/test/ScopInfo/reduction_multiple_loops_array_sum_1.ll @@ -1,21 +1,21 @@ ; RUN: opt -basicaa %loadPolly -polly-scops -analyze < %s | FileCheck %s ; ; CHECK: Stmt_for_body -; CHECK: Reduction like: 0 +; CHECK: Reduction Type: NONE ; CHECK: MemRef_sum_04 -; CHECK: Reduction like: 0 +; CHECK: Reduction Type: NONE ; CHECK: MemRef_sum_12 ; CHECK: Stmt_for_inc -; CHECK: Reduction like: 1 +; CHECK: Reduction Type: ADD ; CHECK: MemRef_sum_12 -; CHECK: Reduction like: 0 +; CHECK: Reduction Type: NONE ; CHECK: MemRef_A -; CHECK: Reduction like: 1 +; CHECK: Reduction Type: ADD ; CHECK: MemRef_sum_12 ; CHECK: Stmt_for_inc5 -; CHECK: Reduction like: 0 +; CHECK: Reduction Type: NONE ; CHECK: MemRef_sum_12 -; CHECK: Reduction like: 0 +; CHECK: Reduction Type: NONE ; CHECK: MemRef_sum_04 ; ; int f(int * __restrict__ A) { diff --git a/polly/test/ScopInfo/reduction_multiple_simple_binary.ll b/polly/test/ScopInfo/reduction_multiple_simple_binary.ll index 52ddcd15a27..49e49188995 100644 --- a/polly/test/ScopInfo/reduction_multiple_simple_binary.ll +++ b/polly/test/ScopInfo/reduction_multiple_simple_binary.ll @@ -1,30 +1,30 @@ ; RUN: opt -basicaa %loadPolly -polly-scops -analyze < %s | FileCheck %s ; -; CHECK: ReadAccess := [Reduction like: 0] +; CHECK: ReadAccess := [Reduction Type: NONE ; CHECK: { Stmt_for_body[i0] -> MemRef_A[1 + i0] }; -; CHECK: ReadAccess := [Reduction like: 0] +; CHECK: ReadAccess := [Reduction Type: NONE ; CHECK: { Stmt_for_body[i0] -> MemRef_A[i0] }; -; CHECK: MustWriteAccess := [Reduction like: 0] +; CHECK: MustWriteAccess := [Reduction Type: NONE ; CHECK: { Stmt_for_body[i0] -> MemRef_first[0] }; -; CHECK: ReadAccess := [Reduction like: 1] +; CHECK: ReadAccess := [Reduction Type: ADD ; CHECK: { Stmt_for_body[i0] -> MemRef_sum[0] }; -; CHECK: MustWriteAccess := [Reduction like: 1] +; CHECK: MustWriteAccess := [Reduction Type: ADD ; CHECK: { Stmt_for_body[i0] -> MemRef_sum[0] }; -; CHECK: ReadAccess := [Reduction like: 0] +; CHECK: ReadAccess := [Reduction Type: NONE ; CHECK: { Stmt_for_body[i0] -> MemRef_A[-1 + i0] }; -; CHECK: ReadAccess := [Reduction like: 0] +; CHECK: ReadAccess := [Reduction Type: NONE ; CHECK: { Stmt_for_body[i0] -> MemRef_A[i0] }; -; CHECK: MustWriteAccess := [Reduction like: 0] +; CHECK: MustWriteAccess := [Reduction Type: NONE ; CHECK: { Stmt_for_body[i0] -> MemRef_middle[0] }; -; CHECK: ReadAccess := [Reduction like: 1] +; CHECK: ReadAccess := [Reduction Type: MUL ; CHECK: { Stmt_for_body[i0] -> MemRef_prod[0] }; -; CHECK: MustWriteAccess := [Reduction like: 1] +; CHECK: MustWriteAccess := [Reduction Type: MUL ; CHECK: { Stmt_for_body[i0] -> MemRef_prod[0] }; -; CHECK: ReadAccess := [Reduction like: 0] +; CHECK: ReadAccess := [Reduction Type: NONE ; CHECK: { Stmt_for_body[i0] -> MemRef_A[-1 + i0] }; -; CHECK: ReadAccess := [Reduction like: 0] +; CHECK: ReadAccess := [Reduction Type: NONE ; CHECK: { Stmt_for_body[i0] -> MemRef_A[1 + i0] }; -; CHECK: MustWriteAccess := [Reduction like: 0] +; CHECK: MustWriteAccess := [Reduction Type: NONE ; CHECK: { Stmt_for_body[i0] -> MemRef_last[0] }; ; ; int first, sum, middle, prod, last; diff --git a/polly/test/ScopInfo/reduction_non_overlapping_chains.ll b/polly/test/ScopInfo/reduction_non_overlapping_chains.ll index 7cd1ba7e97d..ef729552254 100644 --- a/polly/test/ScopInfo/reduction_non_overlapping_chains.ll +++ b/polly/test/ScopInfo/reduction_non_overlapping_chains.ll @@ -1,9 +1,9 @@ ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s ; -; CHECK: Reduction like: 1 -; CHECK: Reduction like: 1 -; CHECK: Reduction like: 1 -; CHECK: Reduction like: 1 +; CHECK: Reduction Type: ADD +; CHECK: Reduction Type: ADD +; CHECK: Reduction Type: MUL +; CHECK: Reduction Type: MUL ; ; void f(int *sums) { ; for (int i = 0; i < 1024; i++) { diff --git a/polly/test/ScopInfo/reduction_only_reduction_like_access.ll b/polly/test/ScopInfo/reduction_only_reduction_like_access.ll index 4eb428ff7e2..1cc98b05bfa 100644 --- a/polly/test/ScopInfo/reduction_only_reduction_like_access.ll +++ b/polly/test/ScopInfo/reduction_only_reduction_like_access.ll @@ -1,6 +1,6 @@ ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s ; -; CHECK: Reduction like: 1 +; CHECK: Reduction Type: ADD ; ; void f(int *sum) { ; for (int i = 0; i < 100; i++) diff --git a/polly/test/ScopInfo/reduction_simple_fp.ll b/polly/test/ScopInfo/reduction_simple_fp.ll index 83ae7c66a73..41af402be2a 100644 --- a/polly/test/ScopInfo/reduction_simple_fp.ll +++ b/polly/test/ScopInfo/reduction_simple_fp.ll @@ -1,9 +1,9 @@ ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s ; ; CHECK: Function: f_no_fast_math -; CHECK: Reduction like: 0 +; CHECK: Reduction Type: NONE ; CHECK: Function: f_fast_math -; CHECK: Reduction like: 1 +; CHECK: Reduction Type: ADD ; ; void f(float *sum) { ; for (int i = 0; i < 100; i++) diff --git a/polly/test/ScopInfo/reduction_simple_w_constant.ll b/polly/test/ScopInfo/reduction_simple_w_constant.ll index c01eabbdea6..ad5fdea1933 100644 --- a/polly/test/ScopInfo/reduction_simple_w_constant.ll +++ b/polly/test/ScopInfo/reduction_simple_w_constant.ll @@ -1,6 +1,6 @@ ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s ; -; CHECK: Reduction like: 1 +; CHECK: Reduction Type: ADD ; ; void f(int *sum) { ; for (int i = 0; i <= 100; i++) diff --git a/polly/test/ScopInfo/reduction_simple_w_iv.ll b/polly/test/ScopInfo/reduction_simple_w_iv.ll index 4e8750d04d8..c123c9b9028 100644 --- a/polly/test/ScopInfo/reduction_simple_w_iv.ll +++ b/polly/test/ScopInfo/reduction_simple_w_iv.ll @@ -1,6 +1,6 @@ ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s ; -; CHECK: Reduction like: 1 +; CHECK: Reduction Type: ADD ; ; void f(int* sum) { ; for (int i = 0; i <= 100; i++) diff --git a/polly/test/ScopInfo/simple_loop_1.ll b/polly/test/ScopInfo/simple_loop_1.ll index 9340810bf09..d1ed9109ff0 100644 --- a/polly/test/ScopInfo/simple_loop_1.ll +++ b/polly/test/ScopInfo/simple_loop_1.ll @@ -30,5 +30,5 @@ return: ; preds = %bb, %entry ; CHECK: [N] -> { Stmt_bb[i0] : i0 >= 0 and i0 <= -1 + N }; ; CHECK: Scattering := ; CHECK: [N] -> { Stmt_bb[i0] -> scattering[0, i0, 0] }; -; CHECK: MustWriteAccess := [Reduction like: 0] +; CHECK: MustWriteAccess := [Reduction Type: NONE] ; CHECK: [N] -> { Stmt_bb[i0] -> MemRef_a[i0] }; |
