From 0ee1f2147856789b4ae26c79c261bd99579b3387 Mon Sep 17 00:00:00 2001 From: Johannes Doerfert Date: Tue, 17 Jun 2014 17:31:36 +0000 Subject: [PATCH] Subject: [PATCH-v5] Detect and mark reduction like statements + Flag to indicate reduction like statements + Command line option to (dis)allow multiplicative reduction opcodes + Two simple positive test cases, one fp test case w and w/o fast math + One "negative" test case (only reduction like but no reduction) llvm-svn: 211114 --- polly/include/polly/ScopInfo.h | 30 +++++++++++++++++++++++++ polly/lib/Analysis/ScopInfo.cpp | 50 ++++++++++++++++++++++++++++++++++++++++- 2 files changed, 79 insertions(+), 1 deletion(-) diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h index e85ec13..f7f9ff9 100644 --- a/polly/include/polly/ScopInfo.h +++ b/polly/include/polly/ScopInfo.h @@ -270,6 +270,31 @@ 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. @@ -294,6 +319,7 @@ class ScopStmt { __isl_give isl_set *buildDomain(TempScop &tempScop, const Region &CurRegion); void buildScattering(SmallVectorImpl &Scatter); void buildAccesses(TempScop &tempScop, const Region &CurRegion); + void checkForReduction(); //@} /// Create the ScopStmt from a BasicBlock. @@ -305,6 +331,10 @@ 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/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp index c8d3e1d..766543d 100644 --- a/polly/lib/Analysis/ScopInfo.cpp +++ b/polly/lib/Analysis/ScopInfo.cpp @@ -20,6 +20,7 @@ #include "polly/CodeGen/BlockGenerators.h" #include "polly/LinkAllPasses.h" #include "polly/ScopInfo.h" +#include "polly/Options.h" #include "polly/Support/GICHelper.h" #include "polly/Support/SCEVValidator.h" #include "polly/Support/ScopHelper.h" @@ -30,7 +31,6 @@ #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/RegionIterator.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" -#include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "isl/constraint.h" @@ -55,6 +55,15 @@ using namespace polly; STATISTIC(ScopFound, "Number of valid Scops"); STATISTIC(RichScopFound, "Number of Scops containing a loop"); +// Multiplicative reductions can be disabled seperately as these kind of +// operations can overflow easily. Additive reductions and bit operations +// are in contrast pretty stable. +static cl::opt +DisableMultiplicativeReductions("polly-disable-multiplicative-reductions", + cl::desc("Disable multiplicative reductions"), + cl::Hidden, cl::ZeroOrMore, cl::init(false), + cl::cat(PollyCategory)); + /// Translate a 'const SCEV *' expression in an isl_pw_aff. struct SCEVAffinator : public SCEVVisitor { public: @@ -696,6 +705,44 @@ ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion, Domain = buildDomain(tempScop, CurRegion); buildScattering(Scatter); buildAccesses(tempScop, CurRegion); + checkForReduction(); +} + +void ScopStmt::checkForReduction() { + // Skip statements with more than one binary reduction + if (MemAccs.size() != 2) + return; + + // Skip if there is not exactly one load and one store + unsigned LoadIdx = MemAccs[0]->isRead() ? 0 : 1; + auto *Load = dyn_cast(MemAccs[LoadIdx]->getAccessInstruction()); + auto *Store = + dyn_cast(MemAccs[1 - LoadIdx]->getAccessInstruction()); + if (!Load || !Store || + Load->getPointerOperand() != Store->getPointerOperand()) + return; + + // Skip if there is not one binary operator between the load and the store + auto *BinOp = dyn_cast(Store->getValueOperand()); + if (!BinOp || (BinOp->getOperand(0) != Load && BinOp->getOperand(1) != Load)) + return; + + // Skip if the opcode of the binary operator is not commutative/associative + if (!BinOp->isCommutative() || !BinOp->isAssociative()) + return; + + // Skip if the load has multiple uses + if (Load->getNumUses() != 1) + return; + + // Skip if it is a multiplicative reduction and we disabled them + if (DisableMultiplicativeReductions && + (BinOp->getOpcode() == Instruction::Mul || + BinOp->getOpcode() == Instruction::FMul)) + return; + + // Valid reduction like statement + IsReductionLike = true; } std::string ScopStmt::getDomainStr() const { return stringFromIslObj(Domain); } @@ -751,6 +798,7 @@ 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"; -- 2.7.4