From 4c3abfa14ca4bfa9596a8e333d6c09a8fe7951a9 Mon Sep 17 00:00:00 2001 From: Michael Kruse Date: Wed, 30 Aug 2017 13:05:08 +0000 Subject: [PATCH] [ScopBuilder/ScopInfo] Move reduction detection to ScopBuilder. NFC. Reduction detection is only executed in the SCoP building phase. Hence it fits better into ScopBuilder to separate SCoP-construction from SCoP modeling. git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@312118 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/polly/ScopBuilder.h | 26 +++++++ include/polly/ScopInfo.h | 10 --- lib/Analysis/ScopBuilder.cpp | 148 ++++++++++++++++++++++++++++++++++++++- lib/Analysis/ScopInfo.cpp | 163 ------------------------------------------- 4 files changed, 173 insertions(+), 174 deletions(-) diff --git a/include/polly/ScopBuilder.h b/include/polly/ScopBuilder.h index f7d6685e..5926e5ef 100644 --- a/include/polly/ScopBuilder.h +++ b/include/polly/ScopBuilder.h @@ -341,6 +341,32 @@ class ScopBuilder { /// Fill NestLoops with loops surrounding @p Stmt. void collectSurroundingLoops(ScopStmt &Stmt); + /// Check for reductions in @p Stmt. + /// + /// Iterate over all store memory accesses and check for valid binary + /// reduction like chains. For all candidates we check if they have the same + /// base address and there are no other accesses which overlap with them. The + /// base address check rules out impossible reductions candidates early. The + /// overlap check, together with the "only one user" check in + /// collectCandiateReductionLoads, guarantees that none of the intermediate + /// results will escape during execution of the loop nest. We basically check + /// here that no other memory access can access the same memory as the + /// potential reduction. + void checkForReductions(ScopStmt &Stmt); + + /// Collect loads which might form a reduction chain with @p StoreMA. + /// + /// Check if the stored value for @p StoreMA is a binary operator with one or + /// two loads as operands. If the binary operand is commutative & associative, + /// used only once (by @p StoreMA) and its load operands are also used only + /// once, we have found a possible reduction chain. It starts at an operand + /// load and includes the binary operator and @p StoreMA. + /// + /// Note: We allow only one use to ensure the load and binary operator cannot + /// escape this block or into any other store except @p StoreMA. + void collectCandiateReductionLoads(MemoryAccess *StoreMA, + SmallVectorImpl &Loads); + /// Build the access relation of all memory accesses of @p Stmt. void buildAccessRelations(ScopStmt &Stmt); diff --git a/include/polly/ScopInfo.h b/include/polly/ScopInfo.h index a128c25a..f1cd86de 100644 --- a/include/polly/ScopInfo.h +++ b/include/polly/ScopInfo.h @@ -1309,16 +1309,6 @@ private: /// Vector for Instructions in this statement. std::vector Instructions; - //@{ - - /// Detect and mark reductions in the ScopStmt - void checkForReductions(); - - /// Collect loads which might form a reduction chain with @p StoreMA - void collectCandiateReductionLoads(MemoryAccess *StoreMA, - SmallVectorImpl &Loads); - //@} - /// Remove @p MA from dictionaries pointing to them. void removeAccessData(MemoryAccess *MA); diff --git a/lib/Analysis/ScopBuilder.cpp b/lib/Analysis/ScopBuilder.cpp index 4a27d7f5..feecc188 100644 --- a/lib/Analysis/ScopBuilder.cpp +++ b/lib/Analysis/ScopBuilder.cpp @@ -94,6 +94,14 @@ static cl::opt DetectReductions("polly-detect-reductions", cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory)); +// Multiplicative reductions can be disabled separately 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)); + void ScopBuilder::buildPHIAccesses(ScopStmt *PHIStmt, PHINode *PHI, Region *NonAffineSubRegion, bool IsExitBlock) { @@ -926,6 +934,144 @@ void ScopBuilder::collectSurroundingLoops(ScopStmt &Stmt) { } } +/// 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; + } +} + +void ScopBuilder::checkForReductions(ScopStmt &Stmt) { + SmallVector Loads; + SmallVector, 4> Candidates; + + // First collect candidate load-store reduction chains by iterating over all + // stores and collecting possible reduction loads. + for (MemoryAccess *StoreMA : Stmt) { + if (StoreMA->isRead()) + continue; + + Loads.clear(); + collectCandiateReductionLoads(StoreMA, Loads); + for (MemoryAccess *LoadMA : Loads) + Candidates.push_back(std::make_pair(LoadMA, StoreMA)); + } + + // Then check each possible candidate pair. + for (const auto &CandidatePair : Candidates) { + bool Valid = true; + isl::map LoadAccs = CandidatePair.first->getAccessRelation(); + isl::map StoreAccs = CandidatePair.second->getAccessRelation(); + + // Skip those with obviously unequal base addresses. + if (!LoadAccs.has_equal_space(StoreAccs)) { + continue; + } + + // And check if the remaining for overlap with other memory accesses. + isl::map AllAccsRel = LoadAccs.unite(StoreAccs); + AllAccsRel = AllAccsRel.intersect_domain(Stmt.getDomain()); + isl::set AllAccs = AllAccsRel.range(); + + for (MemoryAccess *MA : Stmt) { + if (MA == CandidatePair.first || MA == CandidatePair.second) + continue; + + isl::map AccRel = + MA->getAccessRelation().intersect_domain(Stmt.getDomain()); + isl::set Accs = AccRel.range(); + + if (AllAccs.has_equal_space(Accs)) { + isl::set OverlapAccs = Accs.intersect(AllAccs); + Valid = Valid && OverlapAccs.is_empty(); + } + } + + if (!Valid) + continue; + + const LoadInst *Load = + dyn_cast(CandidatePair.first->getAccessInstruction()); + MemoryAccess::ReductionType RT = + getReductionType(dyn_cast(Load->user_back()), Load); + + // If no overlapping access was found we mark the load and store as + // reduction like. + CandidatePair.first->markAsReductionLike(RT); + CandidatePair.second->markAsReductionLike(RT); + } +} + +void ScopBuilder::collectCandiateReductionLoads( + MemoryAccess *StoreMA, SmallVectorImpl &Loads) { + ScopStmt *Stmt = StoreMA->getStatement(); + + auto *Store = dyn_cast(StoreMA->getAccessInstruction()); + if (!Store) + return; + + // Skip if there is not one binary operator between the load and the store + auto *BinOp = dyn_cast(Store->getValueOperand()); + if (!BinOp) + return; + + // Skip if the binary operators has multiple uses + if (BinOp->getNumUses() != 1) + return; + + // Skip if the opcode of the binary operator is not commutative/associative + if (!BinOp->isCommutative() || !BinOp->isAssociative()) + return; + + // Skip if the binary operator is outside the current SCoP + if (BinOp->getParent() != Store->getParent()) + return; + + // Skip if it is a multiplicative reduction and we disabled them + if (DisableMultiplicativeReductions && + (BinOp->getOpcode() == Instruction::Mul || + BinOp->getOpcode() == Instruction::FMul)) + return; + + // Check the binary operator operands for a candidate load + auto *PossibleLoad0 = dyn_cast(BinOp->getOperand(0)); + auto *PossibleLoad1 = dyn_cast(BinOp->getOperand(1)); + if (!PossibleLoad0 && !PossibleLoad1) + return; + + // A load is only a candidate if it cannot escape (thus has only this use) + if (PossibleLoad0 && PossibleLoad0->getNumUses() == 1) + if (PossibleLoad0->getParent() == Store->getParent()) + Loads.push_back(&Stmt->getArrayAccessFor(PossibleLoad0)); + if (PossibleLoad1 && PossibleLoad1->getNumUses() == 1) + if (PossibleLoad1->getParent() == Store->getParent()) + Loads.push_back(&Stmt->getArrayAccessFor(PossibleLoad1)); +} + void ScopBuilder::buildAccessRelations(ScopStmt &Stmt) { for (MemoryAccess *Access : Stmt.MemAccs) { Type *ElementType = Access->getElementType(); @@ -1089,7 +1235,7 @@ void ScopBuilder::buildScop(Region &R, AssumptionCache &AC, buildAccessRelations(Stmt); if (DetectReductions) - Stmt.checkForReductions(); + checkForReductions(Stmt); } // Check early for a feasible runtime context. diff --git a/lib/Analysis/ScopInfo.cpp b/lib/Analysis/ScopInfo.cpp index 6d630be0..68e624a6 100644 --- a/lib/Analysis/ScopInfo.cpp +++ b/lib/Analysis/ScopInfo.cpp @@ -174,14 +174,6 @@ static cl::opt PollyRemarksMinimal( cl::desc("Do not emit remarks about assumptions that are known"), cl::Hidden, cl::ZeroOrMore, cl::init(false), cl::cat(PollyCategory)); -// Multiplicative reductions can be disabled separately 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)); - static cl::opt RunTimeChecksMaxAccessDisjuncts( "polly-rtc-max-array-disjuncts", cl::desc("The maximal number of disjunts allowed in memory accesses to " @@ -672,37 +664,6 @@ MemoryAccess::getReductionOperatorStr(MemoryAccess::ReductionType RT) { llvm_unreachable("Unknown reduction type"); } -/// 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; - } -} - const ScopArrayInfo *MemoryAccess::getOriginalScopArrayInfo() const { isl::id ArrayId = getArrayId(); void *User = ArrayId.get_user(); @@ -1755,130 +1716,6 @@ ScopStmt::ScopStmt(Scop &parent, isl::map SourceRel, isl::map TargetRel, ScopStmt::~ScopStmt() = default; -/// Collect loads which might form a reduction chain with @p StoreMA. -/// -/// Check if the stored value for @p StoreMA is a binary operator with one or -/// two loads as operands. If the binary operand is commutative & associative, -/// used only once (by @p StoreMA) and its load operands are also used only -/// once, we have found a possible reduction chain. It starts at an operand -/// load and includes the binary operator and @p StoreMA. -/// -/// Note: We allow only one use to ensure the load and binary operator cannot -/// escape this block or into any other store except @p StoreMA. -void ScopStmt::collectCandiateReductionLoads( - MemoryAccess *StoreMA, SmallVectorImpl &Loads) { - auto *Store = dyn_cast(StoreMA->getAccessInstruction()); - if (!Store) - return; - - // Skip if there is not one binary operator between the load and the store - auto *BinOp = dyn_cast(Store->getValueOperand()); - if (!BinOp) - return; - - // Skip if the binary operators has multiple uses - if (BinOp->getNumUses() != 1) - return; - - // Skip if the opcode of the binary operator is not commutative/associative - if (!BinOp->isCommutative() || !BinOp->isAssociative()) - return; - - // Skip if the binary operator is outside the current SCoP - if (BinOp->getParent() != Store->getParent()) - return; - - // Skip if it is a multiplicative reduction and we disabled them - if (DisableMultiplicativeReductions && - (BinOp->getOpcode() == Instruction::Mul || - BinOp->getOpcode() == Instruction::FMul)) - return; - - // Check the binary operator operands for a candidate load - auto *PossibleLoad0 = dyn_cast(BinOp->getOperand(0)); - auto *PossibleLoad1 = dyn_cast(BinOp->getOperand(1)); - if (!PossibleLoad0 && !PossibleLoad1) - return; - - // A load is only a candidate if it cannot escape (thus has only this use) - if (PossibleLoad0 && PossibleLoad0->getNumUses() == 1) - if (PossibleLoad0->getParent() == Store->getParent()) - Loads.push_back(&getArrayAccessFor(PossibleLoad0)); - if (PossibleLoad1 && PossibleLoad1->getNumUses() == 1) - if (PossibleLoad1->getParent() == Store->getParent()) - Loads.push_back(&getArrayAccessFor(PossibleLoad1)); -} - -/// Check for reductions in this ScopStmt. -/// -/// Iterate over all store memory accesses and check for valid binary reduction -/// like chains. For all candidates we check if they have the same base address -/// and there are no other accesses which overlap with them. The base address -/// check rules out impossible reductions candidates early. The overlap check, -/// together with the "only one user" check in collectCandiateReductionLoads, -/// guarantees that none of the intermediate results will escape during -/// execution of the loop nest. We basically check here that no other memory -/// access can access the same memory as the potential reduction. -void ScopStmt::checkForReductions() { - SmallVector Loads; - SmallVector, 4> Candidates; - - // First collect candidate load-store reduction chains by iterating over all - // stores and collecting possible reduction loads. - for (MemoryAccess *StoreMA : MemAccs) { - if (StoreMA->isRead()) - continue; - - Loads.clear(); - collectCandiateReductionLoads(StoreMA, Loads); - for (MemoryAccess *LoadMA : Loads) - Candidates.push_back(std::make_pair(LoadMA, StoreMA)); - } - - // Then check each possible candidate pair. - for (const auto &CandidatePair : Candidates) { - bool Valid = true; - isl::map LoadAccs = CandidatePair.first->getAccessRelation(); - isl::map StoreAccs = CandidatePair.second->getAccessRelation(); - - // Skip those with obviously unequal base addresses. - if (!LoadAccs.has_equal_space(StoreAccs)) { - continue; - } - - // And check if the remaining for overlap with other memory accesses. - isl::map AllAccsRel = LoadAccs.unite(StoreAccs); - AllAccsRel = AllAccsRel.intersect_domain(getDomain()); - isl::set AllAccs = AllAccsRel.range(); - - for (MemoryAccess *MA : MemAccs) { - if (MA == CandidatePair.first || MA == CandidatePair.second) - continue; - - isl::map AccRel = MA->getAccessRelation().intersect_domain(getDomain()); - isl::set Accs = AccRel.range(); - - if (AllAccs.has_equal_space(Accs)) { - isl::set OverlapAccs = Accs.intersect(AllAccs); - Valid = Valid && OverlapAccs.is_empty(); - } - } - - if (!Valid) - continue; - - const LoadInst *Load = - dyn_cast(CandidatePair.first->getAccessInstruction()); - MemoryAccess::ReductionType RT = - getReductionType(dyn_cast(Load->user_back()), Load); - - // If no overlapping access was found we mark the load and store as - // reduction like. - CandidatePair.first->markAsReductionLike(RT); - CandidatePair.second->markAsReductionLike(RT); - } -} - std::string ScopStmt::getDomainStr() const { return Domain.to_str(); } std::string ScopStmt::getScheduleStr() const { -- 2.11.4.GIT