Index: polly/include/polly/LinkAllPasses.h =================================================================== --- polly/include/polly/LinkAllPasses.h +++ polly/include/polly/LinkAllPasses.h @@ -162,7 +162,7 @@ #endif void initializeIslScheduleOptimizerWrapperPassPass(llvm::PassRegistry &); void initializeIslScheduleOptimizerPrinterLegacyPassPass(llvm::PassRegistry &); -void initializeMaximalStaticExpanderPass(llvm::PassRegistry &); +void initializeMaximalStaticExpanderWrapperPassPass(llvm::PassRegistry &); void initializePollyCanonicalizePass(llvm::PassRegistry &); void initializeFlattenSchedulePass(llvm::PassRegistry &); void initializeFlattenSchedulePrinterLegacyPassPass(llvm::PassRegistry &); Index: polly/include/polly/MaximalStaticExpansion.h =================================================================== --- /dev/null +++ polly/include/polly/MaximalStaticExpansion.h @@ -0,0 +1,42 @@ +//===- polly/MaximalStaticExpansion.h - expand memory access -*- C++ -*-======// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This pass fully expand the memory accesses of a Scop to get rid of +// dependencies. +// +//===----------------------------------------------------------------------===// + +#ifndef POLLY_MAXIMALSTATICEXPANSION_H +#define POLLY_MAXIMALSTATICEXPANSIO_H + +#include "polly/ScopPass.h" +#include "llvm/IR/PassManager.h" + +namespace polly { + +class MaximalStaticExpansionPass + : public llvm::PassInfoMixin { +public: + llvm::PreservedAnalyses run(Scop &, ScopAnalysisManager &, + ScopStandardAnalysisResults &, SPMUpdater &); +}; + +struct MaximalStaticExpansionPrinterPass + : llvm::PassInfoMixin { + MaximalStaticExpansionPrinterPass(raw_ostream &OS) : OS(OS) {} + + PreservedAnalyses run(Scop &S, ScopAnalysisManager &, + ScopStandardAnalysisResults &SAR, SPMUpdater &); + +private: + llvm::raw_ostream &OS; +}; + +} // namespace polly + +#endif /* POLLY_MAXIMALSTATICEXPANSION_H */ Index: polly/lib/Support/PollyPasses.def =================================================================== --- polly/lib/Support/PollyPasses.def +++ polly/lib/Support/PollyPasses.def @@ -43,4 +43,6 @@ SCOP_PASS("polly-opt-isl", IslScheduleOptimizerPass()) SCOP_PASS("print", IslScheduleOptimizerPrinterPass(llvm::outs())) SCOP_PASS("polly-dce", DeadCodeElimPass()) +SCOP_PASS("polly-mse", MaximalStaticExpansionPass()) +SCOP_PASS("print", MaximalStaticExpansionPrinterPass(llvm::outs())) #undef SCOP_PASS Index: polly/lib/Support/RegisterPasses.cpp =================================================================== --- polly/lib/Support/RegisterPasses.cpp +++ polly/lib/Support/RegisterPasses.cpp @@ -30,6 +30,7 @@ #include "polly/ForwardOpTree.h" #include "polly/JSONExporter.h" #include "polly/LinkAllPasses.h" +#include "polly/MaximalStaticExpansion.h" #include "polly/PolyhedralInfo.h" #include "polly/PruneUnprofitable.h" #include "polly/ScheduleOptimizer.h" @@ -264,7 +265,7 @@ initializeJSONExporterPass(Registry); initializeJSONImporterPass(Registry); initializeJSONImporterPrinterLegacyPassPass(Registry); - initializeMaximalStaticExpanderPass(Registry); + initializeMaximalStaticExpanderWrapperPassPass(Registry); initializeIslAstInfoWrapperPassPass(Registry); initializeIslAstInfoPrinterLegacyPassPass(Registry); initializeIslScheduleOptimizerWrapperPassPass(Registry); Index: polly/lib/Transform/MaximalStaticExpansion.cpp =================================================================== --- polly/lib/Transform/MaximalStaticExpansion.cpp +++ polly/lib/Transform/MaximalStaticExpansion.cpp @@ -11,6 +11,7 @@ // //===----------------------------------------------------------------------===// +#include "polly/MaximalStaticExpansion.h" #include "polly/DependenceInfo.h" #include "polly/LinkAllPasses.h" #include "polly/ScopInfo.h" @@ -34,34 +35,31 @@ namespace { -class MaximalStaticExpander : public ScopPass { -public: - static char ID; - - explicit MaximalStaticExpander() : ScopPass(ID) {} - - ~MaximalStaticExpander() override = default; - - /// Expand the accesses of the SCoP. - /// - /// @param S The SCoP that must be expanded. - bool runOnScop(Scop &S) override; - - /// Print the SCoP. - /// - /// @param OS The stream where to print. - /// @param S The SCop that must be printed. - void printScop(raw_ostream &OS, Scop &S) const override; - - /// Register all analyses and transformations required. - void getAnalysisUsage(AnalysisUsage &AU) const override; +#ifndef NDEBUG +/// Whether a dimension of a set is bounded (lower and upper) by a constant, +/// i.e. there are two constants Min and Max, such that every value x of the +/// chosen dimensions is Min <= x <= Max. +static bool isDimBoundedByConstant(isl::set Set, unsigned dim) { + auto ParamDims = unsignedFromIslSize(Set.dim(isl::dim::param)); + Set = Set.project_out(isl::dim::param, 0, ParamDims); + Set = Set.project_out(isl::dim::set, 0, dim); + auto SetDims = unsignedFromIslSize(Set.tuple_dim()); + assert(SetDims >= 1); + Set = Set.project_out(isl::dim::set, 1, SetDims - 1); + return bool(Set.is_bounded()); +} +#endif -private: - /// OptimizationRemarkEmitter object for displaying diagnostic remarks. - OptimizationRemarkEmitter *ORE; +class MaximalStaticExpansionImpl { + OptimizationRemarkEmitter &ORE; + Scop &S; + isl::union_map &Dependences; /// Emit remark - void emitRemark(StringRef Msg, Instruction *Inst); + void emitRemark(StringRef Msg, Instruction *Inst) { + ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "ExpansionRejection", Inst) + << Msg); + } /// Return true if the SAI in parameter is expandable. /// @@ -72,416 +70,483 @@ /// @param Dependences The RAW dependences of the SCop. bool isExpandable(const ScopArrayInfo *SAI, SmallPtrSetImpl &Writes, - SmallPtrSetImpl &Reads, Scop &S, - const isl::union_map &Dependences); + SmallPtrSetImpl &Reads, Scop &S) { + if (SAI->isValueKind()) { + Writes.insert(S.getValueDef(SAI)); + for (auto MA : S.getValueUses(SAI)) + Reads.insert(MA); + return true; + } else if (SAI->isPHIKind()) { + auto Read = S.getPHIRead(SAI); - /// Expand the MemoryAccess according to its domain. - /// - /// @param S The SCop in which the memory access appears in. - /// @param MA The memory access that need to be expanded. - ScopArrayInfo *expandAccess(Scop &S, MemoryAccess *MA); + auto StmtDomain = isl::union_set(Read->getStatement()->getDomain()); - /// Filter the dependences to have only one related to current memory access. - /// - /// @param S The SCop in which the memory access appears in. - /// @param MapDependences The dependences to filter. - /// @param MA The memory access that need to be expanded. - isl::union_map filterDependences(Scop &S, - const isl::union_map &MapDependences, - MemoryAccess *MA); + auto Writes = S.getPHIIncomings(SAI); - /// Expand the MemoryAccess according to Dependences and already expanded - /// MemoryAccesses. - /// - /// @param The SCop in which the memory access appears in. - /// @param The memory access that need to be expanded. - /// @param Dependences The RAW dependences of the SCop. - /// @param ExpandedSAI The expanded SAI created during write expansion. - /// @param Reverse if true, the Dependences union_map is reversed before - /// intersection. - void mapAccess(Scop &S, SmallPtrSetImpl &Accesses, - const isl::union_map &Dependences, ScopArrayInfo *ExpandedSAI, - bool Reverse); + // Get the domain where all the writes are writing to. + auto WriteDomain = isl::union_set::empty(S.getIslCtx()); - /// Expand PHI memory accesses. - /// - /// @param The SCop in which the memory access appears in. - /// @param The ScopArrayInfo representing the PHI accesses to expand. - /// @param Dependences The RAW dependences of the SCop. - void expandPhi(Scop &S, const ScopArrayInfo *SAI, - const isl::union_map &Dependences); -}; -} // namespace - -#ifndef NDEBUG -/// Whether a dimension of a set is bounded (lower and upper) by a constant, -/// i.e. there are two constants Min and Max, such that every value x of the -/// chosen dimensions is Min <= x <= Max. -static bool isDimBoundedByConstant(isl::set Set, unsigned dim) { - auto ParamDims = unsignedFromIslSize(Set.dim(isl::dim::param)); - Set = Set.project_out(isl::dim::param, 0, ParamDims); - Set = Set.project_out(isl::dim::set, 0, dim); - auto SetDims = unsignedFromIslSize(Set.tuple_dim()); - assert(SetDims >= 1); - Set = Set.project_out(isl::dim::set, 1, SetDims - 1); - return bool(Set.is_bounded()); -} -#endif + for (auto Write : Writes) { + auto MapDeps = filterDependences(Dependences, Write); + for (isl::map Map : MapDeps.get_map_list()) + WriteDomain = WriteDomain.unite(Map.range()); + } -char MaximalStaticExpander::ID = 0; + // For now, read from original scalar is not possible. + if (!StmtDomain.is_equal(WriteDomain)) { + emitRemark(SAI->getName() + " read from its original value.", + Read->getAccessInstruction()); + return false; + } -isl::union_map MaximalStaticExpander::filterDependences( - Scop &S, const isl::union_map &Dependences, MemoryAccess *MA) { - auto SAI = MA->getLatestScopArrayInfo(); + return true; + } else if (SAI->isExitPHIKind()) { + // For now, we are not able to expand ExitPhi. + emitRemark(SAI->getName() + " is a ExitPhi node.", + S.getEnteringBlock()->getFirstNonPHI()); + return false; + } - auto AccessDomainSet = MA->getAccessRelation().domain(); - auto AccessDomainId = AccessDomainSet.get_tuple_id(); + int NumberWrites = 0; + for (ScopStmt &Stmt : S) { + auto StmtReads = isl::union_map::empty(S.getIslCtx()); + auto StmtWrites = isl::union_map::empty(S.getIslCtx()); + + for (MemoryAccess *MA : Stmt) { + // Check if the current MemoryAccess involved the current SAI. + if (SAI != MA->getLatestScopArrayInfo()) + continue; + + // For now, we are not able to expand array where read come after write + // (to the same location) in a same statement. + auto AccRel = isl::union_map(MA->getAccessRelation()); + if (MA->isRead()) { + // Reject load after store to same location. + if (!StmtWrites.is_disjoint(AccRel)) { + emitRemark(SAI->getName() + " has read after write to the same " + "element in same statement. The " + "dependences found during analysis may " + "be wrong because Polly is not able to " + "handle such case for now.", + MA->getAccessInstruction()); + return false; + } + + StmtReads = StmtReads.unite(AccRel); + } else { + StmtWrites = StmtWrites.unite(AccRel); + } - isl::union_map MapDependences = isl::union_map::empty(S.getIslCtx()); + // For now, we are not able to expand MayWrite. + if (MA->isMayWrite()) { + emitRemark(SAI->getName() + " has a maywrite access.", + MA->getAccessInstruction()); + return false; + } - for (isl::map Map : Dependences.get_map_list()) { - // Filter out Statement to Statement dependences. - if (!Map.can_curry()) - continue; + // For now, we are not able to expand SAI with more than one write. + if (MA->isMustWrite()) { + Writes.insert(MA); + NumberWrites++; + if (NumberWrites > 1) { + emitRemark(SAI->getName() + " has more than 1 write access.", + MA->getAccessInstruction()); + return false; + } + } - // Intersect with the relevant SAI. - auto TmpMapDomainId = - Map.get_space().domain().unwrap().range().get_tuple_id(isl::dim::set); + // Check if it is possible to expand this read. + if (MA->isRead()) { + // Get the domain of the current ScopStmt. + auto StmtDomain = Stmt.getDomain(); + + // Get the domain of the future Read access. + auto ReadDomainSet = MA->getAccessRelation().domain(); + auto ReadDomain = isl::union_set(ReadDomainSet); + + // Get the dependences relevant for this MA + auto MapDependences = filterDependences(Dependences.reverse(), MA); + unsigned NumberElementMap = isl_union_map_n_map(MapDependences.get()); + + if (NumberElementMap == 0) { + emitRemark("The expansion of " + SAI->getName() + + " would lead to a read from the original array.", + MA->getAccessInstruction()); + return false; + } + + auto DepsDomain = MapDependences.domain(); + + // If there are multiple maps in the Deps, we cannot handle this case + // for now. + if (NumberElementMap != 1) { + emitRemark(SAI->getName() + + " has too many dependences to be handle for now.", + MA->getAccessInstruction()); + return false; + } + + auto DepsDomainSet = isl::set(DepsDomain); + + // For now, read from the original array is not possible. + if (!StmtDomain.is_subset(DepsDomainSet)) { + emitRemark("The expansion of " + SAI->getName() + + " would lead to a read from the original array.", + MA->getAccessInstruction()); + return false; + } + + Reads.insert(MA); + } + } + } - ScopArrayInfo *UserSAI = - static_cast(TmpMapDomainId.get_user()); + // No need to expand SAI with no write. + if (NumberWrites == 0) { + emitRemark(SAI->getName() + " has 0 write access.", + S.getEnteringBlock()->getFirstNonPHI()); + return false; + } - if (SAI != UserSAI) - continue; + return true; + } - // Get the correct S1[] -> S2[] dependence. - auto NewMap = Map.factor_domain(); - auto NewMapDomainId = NewMap.domain().get_tuple_id(); + /// Expand the MemoryAccess according to its domain. + /// + /// @param S The SCop in which the memory access appears in. + /// @param MA The memory access that need to be expanded. + ScopArrayInfo *expandAccess(MemoryAccess *MA) { + // Get the current AM. + auto CurrentAccessMap = MA->getAccessRelation(); - if (AccessDomainId.get() != NewMapDomainId.get()) - continue; + unsigned in_dimensions = + unsignedFromIslSize(CurrentAccessMap.domain_tuple_dim()); + + // Get domain from the current AM. + auto Domain = CurrentAccessMap.domain(); + + // Create a new AM from the domain. + auto NewAccessMap = isl::map::from_domain(Domain); + + // Add dimensions to the new AM according to the current in_dim. + NewAccessMap = NewAccessMap.add_dims(isl::dim::out, in_dimensions); + + // Create the string representing the name of the new SAI. + // One new SAI for each statement so that each write go to a different + // memory cell. + auto CurrentStmtDomain = MA->getStatement()->getDomain(); + auto CurrentStmtName = CurrentStmtDomain.get_tuple_name(); + auto CurrentOutId = CurrentAccessMap.get_tuple_id(isl::dim::out); + std::string CurrentOutIdString = + MA->getScopArrayInfo()->getName() + "_" + CurrentStmtName + "_expanded"; + + // Set the tuple id for the out dimension. + NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, CurrentOutId); + + // Create the size vector. + std::vector Sizes; + for (unsigned i = 0; i < in_dimensions; i++) { + assert(isDimBoundedByConstant(CurrentStmtDomain, i) && + "Domain boundary are not constant."); + auto UpperBound = getConstant(CurrentStmtDomain.dim_max(i), true, false); + assert(!UpperBound.is_null() && UpperBound.is_pos() && + !UpperBound.is_nan() && + "The upper bound is not a positive integer."); + assert(UpperBound.le(isl::val(CurrentAccessMap.ctx(), + std::numeric_limits::max() - 1)) && + "The upper bound overflow a int."); + Sizes.push_back(UpperBound.get_num_si() + 1); + } - // Add the corresponding map to MapDependences. - MapDependences = MapDependences.unite(NewMap); - } + // Get the ElementType of the current SAI. + auto ElementType = MA->getLatestScopArrayInfo()->getElementType(); - return MapDependences; -} + // Create (or get if already existing) the new expanded SAI. + auto ExpandedSAI = + S.createScopArrayInfo(ElementType, CurrentOutIdString, Sizes); + ExpandedSAI->setIsOnHeap(true); -bool MaximalStaticExpander::isExpandable( - const ScopArrayInfo *SAI, SmallPtrSetImpl &Writes, - SmallPtrSetImpl &Reads, Scop &S, - const isl::union_map &Dependences) { - if (SAI->isValueKind()) { - Writes.insert(S.getValueDef(SAI)); - for (auto MA : S.getValueUses(SAI)) - Reads.insert(MA); - return true; - } else if (SAI->isPHIKind()) { - auto Read = S.getPHIRead(SAI); + // Get the out Id of the expanded Array. + auto NewOutId = ExpandedSAI->getBasePtrId(); - auto StmtDomain = isl::union_set(Read->getStatement()->getDomain()); + // Set the out id of the new AM to the new SAI id. + NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, NewOutId); - auto Writes = S.getPHIIncomings(SAI); + // Add constraints to linked output with input id. + auto SpaceMap = NewAccessMap.get_space(); + auto ConstraintBasicMap = isl::basic_map::equal( + SpaceMap, unsignedFromIslSize(SpaceMap.dim(isl::dim::in))); + NewAccessMap = isl::map(ConstraintBasicMap); - // Get the domain where all the writes are writing to. - auto WriteDomain = isl::union_set::empty(S.getIslCtx()); + // Set the new access relation map. + MA->setNewAccessRelation(NewAccessMap); - for (auto Write : Writes) { - auto MapDeps = filterDependences(S, Dependences, Write); - for (isl::map Map : MapDeps.get_map_list()) - WriteDomain = WriteDomain.unite(Map.range()); - } + return ExpandedSAI; + } - // For now, read from original scalar is not possible. - if (!StmtDomain.is_equal(WriteDomain)) { - emitRemark(SAI->getName() + " read from its original value.", - Read->getAccessInstruction()); - return false; - } + /// Filter the dependences to have only one related to current memory access. + /// + /// @param S The SCop in which the memory access appears in. + /// @param MapDependences The dependences to filter. + /// @param MA The memory access that need to be expanded. + isl::union_map filterDependences(const isl::union_map &Dependences, + MemoryAccess *MA) { + auto SAI = MA->getLatestScopArrayInfo(); - return true; - } else if (SAI->isExitPHIKind()) { - // For now, we are not able to expand ExitPhi. - emitRemark(SAI->getName() + " is a ExitPhi node.", - S.getEnteringBlock()->getFirstNonPHI()); - return false; - } + auto AccessDomainSet = MA->getAccessRelation().domain(); + auto AccessDomainId = AccessDomainSet.get_tuple_id(); - int NumberWrites = 0; - for (ScopStmt &Stmt : S) { - auto StmtReads = isl::union_map::empty(S.getIslCtx()); - auto StmtWrites = isl::union_map::empty(S.getIslCtx()); + isl::union_map MapDependences = isl::union_map::empty(S.getIslCtx()); - for (MemoryAccess *MA : Stmt) { - // Check if the current MemoryAccess involved the current SAI. - if (SAI != MA->getLatestScopArrayInfo()) + for (isl::map Map : Dependences.get_map_list()) { + // Filter out Statement to Statement dependences. + if (!Map.can_curry()) continue; - // For now, we are not able to expand array where read come after write - // (to the same location) in a same statement. - auto AccRel = isl::union_map(MA->getAccessRelation()); - if (MA->isRead()) { - // Reject load after store to same location. - if (!StmtWrites.is_disjoint(AccRel)) { - emitRemark(SAI->getName() + " has read after write to the same " - "element in same statement. The " - "dependences found during analysis may " - "be wrong because Polly is not able to " - "handle such case for now.", - MA->getAccessInstruction()); - return false; - } + // Intersect with the relevant SAI. + auto TmpMapDomainId = + Map.get_space().domain().unwrap().range().get_tuple_id(isl::dim::set); - StmtReads = StmtReads.unite(AccRel); - } else { - StmtWrites = StmtWrites.unite(AccRel); - } + ScopArrayInfo *UserSAI = + static_cast(TmpMapDomainId.get_user()); - // For now, we are not able to expand MayWrite. - if (MA->isMayWrite()) { - emitRemark(SAI->getName() + " has a maywrite access.", - MA->getAccessInstruction()); - return false; - } + if (SAI != UserSAI) + continue; - // For now, we are not able to expand SAI with more than one write. - if (MA->isMustWrite()) { - Writes.insert(MA); - NumberWrites++; - if (NumberWrites > 1) { - emitRemark(SAI->getName() + " has more than 1 write access.", - MA->getAccessInstruction()); - return false; - } - } + // Get the correct S1[] -> S2[] dependence. + auto NewMap = Map.factor_domain(); + auto NewMapDomainId = NewMap.domain().get_tuple_id(); - // Check if it is possible to expand this read. - if (MA->isRead()) { - // Get the domain of the current ScopStmt. - auto StmtDomain = Stmt.getDomain(); + if (AccessDomainId.get() != NewMapDomainId.get()) + continue; - // Get the domain of the future Read access. - auto ReadDomainSet = MA->getAccessRelation().domain(); - auto ReadDomain = isl::union_set(ReadDomainSet); + // Add the corresponding map to MapDependences. + MapDependences = MapDependences.unite(NewMap); + } - // Get the dependences relevant for this MA - auto MapDependences = filterDependences(S, Dependences.reverse(), MA); - unsigned NumberElementMap = isl_union_map_n_map(MapDependences.get()); + return MapDependences; + } - if (NumberElementMap == 0) { - emitRemark("The expansion of " + SAI->getName() + - " would lead to a read from the original array.", - MA->getAccessInstruction()); - return false; - } + /// Expand the MemoryAccess according to Dependences and already expanded + /// MemoryAccesses. + /// + /// @param The SCop in which the memory access appears in. + /// @param The memory access that need to be expanded. + /// @param Dependences The RAW dependences of the SCop. + /// @param ExpandedSAI The expanded SAI created during write expansion. + /// @param Reverse if true, the Dependences union_map is reversed before + /// intersection. + void mapAccess(SmallPtrSetImpl &Accesses, + const isl::union_map &Dependences, ScopArrayInfo *ExpandedSAI, + bool Reverse) { + for (auto MA : Accesses) { + // Get the current AM. + auto CurrentAccessMap = MA->getAccessRelation(); - auto DepsDomain = MapDependences.domain(); + // Get RAW dependences for the current WA. + auto DomainSet = MA->getAccessRelation().domain(); + auto Domain = isl::union_set(DomainSet); - // If there are multiple maps in the Deps, we cannot handle this case - // for now. - if (NumberElementMap != 1) { - emitRemark(SAI->getName() + - " has too many dependences to be handle for now.", - MA->getAccessInstruction()); - return false; - } + // Get the dependences relevant for this MA. + isl::union_map MapDependences = + filterDependences(Reverse ? Dependences.reverse() : Dependences, MA); - auto DepsDomainSet = isl::set(DepsDomain); + // If no dependences, no need to modify anything. + if (MapDependences.is_empty()) + return; - // For now, read from the original array is not possible. - if (!StmtDomain.is_subset(DepsDomainSet)) { - emitRemark("The expansion of " + SAI->getName() + - " would lead to a read from the original array.", - MA->getAccessInstruction()); - return false; - } + assert(isl_union_map_n_map(MapDependences.get()) == 1 && + "There are more than one RAW dependencies in the union map."); + auto NewAccessMap = isl::map::from_union_map(MapDependences); - Reads.insert(MA); - } + auto Id = ExpandedSAI->getBasePtrId(); + + // Replace the out tuple id with the one of the access array. + NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, Id); + + // Set the new access relation. + MA->setNewAccessRelation(NewAccessMap); } } - // No need to expand SAI with no write. - if (NumberWrites == 0) { - emitRemark(SAI->getName() + " has 0 write access.", - S.getEnteringBlock()->getFirstNonPHI()); - return false; + /// Expand PHI memory accesses. + /// + /// @param The SCop in which the memory access appears in. + /// @param The ScopArrayInfo representing the PHI accesses to expand. + /// @param Dependences The RAW dependences of the SCop. + void expandPhi(Scop &S, const ScopArrayInfo *SAI, + const isl::union_map &Dependences) { + SmallPtrSet Writes; + for (auto MA : S.getPHIIncomings(SAI)) + Writes.insert(MA); + auto Read = S.getPHIRead(SAI); + auto ExpandedSAI = expandAccess(Read); + + mapAccess(Writes, Dependences, ExpandedSAI, false); } - return true; -} +public: + MaximalStaticExpansionImpl(Scop &S, isl::union_map &Dependences, + OptimizationRemarkEmitter &ORE) + : S(S), Dependences(Dependences), ORE(ORE) {} -void MaximalStaticExpander::mapAccess(Scop &S, - SmallPtrSetImpl &Accesses, - const isl::union_map &Dependences, - ScopArrayInfo *ExpandedSAI, - bool Reverse) { - for (auto MA : Accesses) { - // Get the current AM. - auto CurrentAccessMap = MA->getAccessRelation(); + /// Expand the accesses of the SCoP + /// + /// @param S The SCoP that must be expanded + /// @param D The dependencies information of SCoP + void expand() { + SmallVector CurrentSAI(S.arrays().begin(), + S.arrays().end()); + for (auto SAI : CurrentSAI) { + SmallPtrSet AllWrites; + SmallPtrSet AllReads; + if (!isExpandable(SAI, AllWrites, AllReads, S)) + continue; - // Get RAW dependences for the current WA. - auto DomainSet = MA->getAccessRelation().domain(); - auto Domain = isl::union_set(DomainSet); + if (SAI->isValueKind() || SAI->isArrayKind()) { + assert(AllWrites.size() == 1 || SAI->isValueKind()); - // Get the dependences relevant for this MA. - isl::union_map MapDependences = - filterDependences(S, Reverse ? Dependences.reverse() : Dependences, MA); + auto TheWrite = *(AllWrites.begin()); + ScopArrayInfo *ExpandedArray = expandAccess(TheWrite); - // If no dependences, no need to modify anything. - if (MapDependences.is_empty()) - return; + mapAccess(AllReads, Dependences, ExpandedArray, true); + } else if (SAI->isPHIKind()) { + expandPhi(S, SAI, Dependences); + } + } + } - assert(isl_union_map_n_map(MapDependences.get()) == 1 && - "There are more than one RAW dependencies in the union map."); - auto NewAccessMap = isl::map::from_union_map(MapDependences); + /// Dump the internal information about a performed MSE to @p OS. + void print(llvm::raw_ostream &OS) { + OS << "After arrays {\n"; - auto Id = ExpandedSAI->getBasePtrId(); + for (auto &Array : S.arrays()) + Array->print(OS); - // Replace the out tuple id with the one of the access array. - NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, Id); + OS << "}\n"; - // Set the new access relation. - MA->setNewAccessRelation(NewAccessMap); + OS << "After accesses {\n"; + for (auto &Stmt : S) { + OS.indent(4) << Stmt.getBaseName() << "{\n"; + for (auto *MA : Stmt) + MA->print(OS); + OS.indent(4) << "}\n"; + } + OS << "}\n"; } -} +}; -ScopArrayInfo *MaximalStaticExpander::expandAccess(Scop &S, MemoryAccess *MA) { - // Get the current AM. - auto CurrentAccessMap = MA->getAccessRelation(); - - unsigned in_dimensions = - unsignedFromIslSize(CurrentAccessMap.domain_tuple_dim()); - - // Get domain from the current AM. - auto Domain = CurrentAccessMap.domain(); - - // Create a new AM from the domain. - auto NewAccessMap = isl::map::from_domain(Domain); - - // Add dimensions to the new AM according to the current in_dim. - NewAccessMap = NewAccessMap.add_dims(isl::dim::out, in_dimensions); - - // Create the string representing the name of the new SAI. - // One new SAI for each statement so that each write go to a different memory - // cell. - auto CurrentStmtDomain = MA->getStatement()->getDomain(); - auto CurrentStmtName = CurrentStmtDomain.get_tuple_name(); - auto CurrentOutId = CurrentAccessMap.get_tuple_id(isl::dim::out); - std::string CurrentOutIdString = - MA->getScopArrayInfo()->getName() + "_" + CurrentStmtName + "_expanded"; - - // Set the tuple id for the out dimension. - NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, CurrentOutId); - - // Create the size vector. - std::vector Sizes; - for (unsigned i = 0; i < in_dimensions; i++) { - assert(isDimBoundedByConstant(CurrentStmtDomain, i) && - "Domain boundary are not constant."); - auto UpperBound = getConstant(CurrentStmtDomain.dim_max(i), true, false); - assert(!UpperBound.is_null() && UpperBound.is_pos() && - !UpperBound.is_nan() && - "The upper bound is not a positive integer."); - assert(UpperBound.le(isl::val(CurrentAccessMap.ctx(), - std::numeric_limits::max() - 1)) && - "The upper bound overflow a int."); - Sizes.push_back(UpperBound.get_num_si() + 1); - } +static std::unique_ptr +runMaximalStaticExpansion(Scop &S, OptimizationRemarkEmitter &ORE, + const Dependences &D) { + auto Dependences = D.getDependences(Dependences::TYPE_RAW); - // Get the ElementType of the current SAI. - auto ElementType = MA->getLatestScopArrayInfo()->getElementType(); + std::unique_ptr Impl = + std::make_unique(S, Dependences, ORE); - // Create (or get if already existing) the new expanded SAI. - auto ExpandedSAI = - S.createScopArrayInfo(ElementType, CurrentOutIdString, Sizes); - ExpandedSAI->setIsOnHeap(true); + Impl->expand(); + return Impl; +} - // Get the out Id of the expanded Array. - auto NewOutId = ExpandedSAI->getBasePtrId(); +static PreservedAnalyses runMSEUsingNPM(Scop &S, ScopAnalysisManager &SAM, + ScopStandardAnalysisResults &SAR, + raw_ostream *OS) { + OptimizationRemarkEmitter ORE(&S.getFunction()); - // Set the out id of the new AM to the new SAI id. - NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, NewOutId); + auto &DI = SAM.getResult(S, SAR); + auto &D = DI.getDependences(Dependences::AL_Reference); - // Add constraints to linked output with input id. - auto SpaceMap = NewAccessMap.get_space(); - auto ConstraintBasicMap = isl::basic_map::equal( - SpaceMap, unsignedFromIslSize(SpaceMap.dim(isl::dim::in))); - NewAccessMap = isl::map(ConstraintBasicMap); + auto Impl = runMaximalStaticExpansion(S, ORE, D); - // Set the new access relation map. - MA->setNewAccessRelation(NewAccessMap); + if (OS) { + *OS << "Printing analysis 'Polly - Maximal static expansion of SCoP' for " + "region: '" + << S.getName() << "' in function '" << S.getFunction().getName() + << "':\n"; - return ExpandedSAI; + if (Impl) { + *OS << "MSE result:\n"; + Impl->print(*OS); + } + } + + return PreservedAnalyses::all(); } -void MaximalStaticExpander::expandPhi(Scop &S, const ScopArrayInfo *SAI, - const isl::union_map &Dependences) { - SmallPtrSet Writes; - for (auto MA : S.getPHIIncomings(SAI)) - Writes.insert(MA); - auto Read = S.getPHIRead(SAI); - auto ExpandedSAI = expandAccess(S, Read); +} // namespace - mapAccess(S, Writes, Dependences, ExpandedSAI, false); +PreservedAnalyses +MaximalStaticExpansionPass::run(Scop &S, ScopAnalysisManager &SAM, + ScopStandardAnalysisResults &SAR, + SPMUpdater &) { + return runMSEUsingNPM(S, SAM, SAR, nullptr); } -void MaximalStaticExpander::emitRemark(StringRef Msg, Instruction *Inst) { - ORE->emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "ExpansionRejection", Inst) - << Msg); +PreservedAnalyses +MaximalStaticExpansionPrinterPass::run(Scop &S, ScopAnalysisManager &SAM, + ScopStandardAnalysisResults &SAR, + SPMUpdater &) { + return runMSEUsingNPM(S, SAM, SAR, &OS); } -bool MaximalStaticExpander::runOnScop(Scop &S) { - // Get the ORE from OptimizationRemarkEmitterWrapperPass. - ORE = &(getAnalysis().getORE()); +class MaximalStaticExpanderWrapperPass : public ScopPass { +public: + static char ID; - // Get the RAW Dependences. - auto &DI = getAnalysis(); - auto &D = DI.getDependences(Dependences::AL_Reference); - isl::union_map Dependences = D.getDependences(Dependences::TYPE_RAW); + explicit MaximalStaticExpanderWrapperPass() : ScopPass(ID) {} + + ~MaximalStaticExpanderWrapperPass() override = default; + + /// Expand the accesses of the SCoP. + /// + /// @param S The SCoP that must be expanded. + bool runOnScop(Scop &S) override; + + /// Print the SCoP. + /// + /// @param OS The stream where to print. + /// @param S The SCop that must be printed. + void printScop(raw_ostream &OS, Scop &S) const override; - SmallVector CurrentSAI(S.arrays().begin(), - S.arrays().end()); + /// Register all analyses and transformations required. + void getAnalysisUsage(AnalysisUsage &AU) const override; +}; - for (auto SAI : CurrentSAI) { - SmallPtrSet AllWrites; - SmallPtrSet AllReads; - if (!isExpandable(SAI, AllWrites, AllReads, S, Dependences)) - continue; +char MaximalStaticExpanderWrapperPass::ID = 0; - if (SAI->isValueKind() || SAI->isArrayKind()) { - assert(AllWrites.size() == 1 || SAI->isValueKind()); +bool MaximalStaticExpanderWrapperPass::runOnScop(Scop &S) { + // Get the ORE from OptimizationRemarkEmitterWrapperPass. + OptimizationRemarkEmitter *ORE = + &(getAnalysis().getORE()); - auto TheWrite = *(AllWrites.begin()); - ScopArrayInfo *ExpandedArray = expandAccess(S, TheWrite); + // Get the RAW Dependences. + auto &DI = getAnalysis(); + auto &D = DI.getDependences(Dependences::AL_Reference); - mapAccess(S, AllReads, Dependences, ExpandedArray, true); - } else if (SAI->isPHIKind()) { - expandPhi(S, SAI, Dependences); - } - } + auto Impl = runMaximalStaticExpansion(S, *ORE, D); return false; } -void MaximalStaticExpander::printScop(raw_ostream &OS, Scop &S) const { +void MaximalStaticExpanderWrapperPass::printScop(raw_ostream &OS, + Scop &S) const { S.print(OS, false); } -void MaximalStaticExpander::getAnalysisUsage(AnalysisUsage &AU) const { +void MaximalStaticExpanderWrapperPass::getAnalysisUsage( + AnalysisUsage &AU) const { ScopPass::getAnalysisUsage(AU); AU.addRequired(); AU.addRequired(); } Pass *polly::createMaximalStaticExpansionPass() { - return new MaximalStaticExpander(); + return new MaximalStaticExpanderWrapperPass(); } -INITIALIZE_PASS_BEGIN(MaximalStaticExpander, "polly-mse", +INITIALIZE_PASS_BEGIN(MaximalStaticExpanderWrapperPass, "polly-mse", "Polly - Maximal static expansion of SCoP", false, false); INITIALIZE_PASS_DEPENDENCY(DependenceInfo); INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass); -INITIALIZE_PASS_END(MaximalStaticExpander, "polly-mse", +INITIALIZE_PASS_END(MaximalStaticExpanderWrapperPass, "polly-mse", "Polly - Maximal static expansion of SCoP", false, false) Index: polly/test/MaximalStaticExpansion/load_after_store_same_statement.ll =================================================================== --- polly/test/MaximalStaticExpansion/load_after_store_same_statement.ll +++ polly/test/MaximalStaticExpansion/load_after_store_same_statement.ll @@ -1,5 +1,7 @@ ; RUN: opt %loadPolly -polly-stmt-granularity=bb -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s +; RUN: opt %loadNPMPolly -polly-stmt-granularity=bb "-passes=scop(print)" -disable-output < %s | FileCheck %s ; RUN: opt %loadPolly -polly-stmt-granularity=bb -polly-mse -polly-print-scops -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1| FileCheck %s --check-prefix=MSE +; RUN: opt %loadNPMPolly -polly-stmt-granularity=bb "-passes=scop(print)" -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=MSE ; ; Verify that the expansion of an array with load after store in a same statement is not done. ; Index: polly/test/MaximalStaticExpansion/read_from_original.ll =================================================================== --- polly/test/MaximalStaticExpansion/read_from_original.ll +++ polly/test/MaximalStaticExpansion/read_from_original.ll @@ -1,5 +1,7 @@ ; RUN: opt %loadPolly -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s +; RUN: opt %loadNPMPolly "-passes=scop(print)" -disable-output < %s | FileCheck %s ; RUN: opt %loadPolly -polly-mse -polly-print-scops -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1| FileCheck %s --check-prefix=MSE +; RUN: opt %loadNPMPolly "-passes=scop(print)" -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=MSE ; ; Verify that Polly detects problems and does not expand the array ; Index: polly/test/MaximalStaticExpansion/too_many_writes.ll =================================================================== --- polly/test/MaximalStaticExpansion/too_many_writes.ll +++ polly/test/MaximalStaticExpansion/too_many_writes.ll @@ -1,5 +1,7 @@ ; RUN: opt %loadPolly -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s +; RUN: opt %loadNPMPolly "-passes=scop(print)" -disable-output < %s | FileCheck %s ; RUN: opt %loadPolly -polly-mse -polly-print-scops -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=MSE +; RUN: opt %loadNPMPolly "-passes=scop(print)" -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=MSE ; ; Verify that Polly detects problems and does not expand the array ; Index: polly/test/MaximalStaticExpansion/working_deps_between_inners.ll =================================================================== --- polly/test/MaximalStaticExpansion/working_deps_between_inners.ll +++ polly/test/MaximalStaticExpansion/working_deps_between_inners.ll @@ -1,4 +1,5 @@ ; RUN: opt %loadPolly -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s +; RUN: opt %loadNPMPolly "-passes=scop(print)" -disable-output < %s | FileCheck %s ; ; Verify that the accesses are correctly expanded for MemoryKind::Array ; Index: polly/test/MaximalStaticExpansion/working_deps_between_inners_phi.ll =================================================================== --- polly/test/MaximalStaticExpansion/working_deps_between_inners_phi.ll +++ polly/test/MaximalStaticExpansion/working_deps_between_inners_phi.ll @@ -1,5 +1,7 @@ ; RUN: opt %loadPolly -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s +; RUN: opt %loadNPMPolly "-passes=scop(print)" -disable-output < %s | FileCheck %s ; RUN: opt %loadPolly -polly-mse -polly-print-scops -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=MSE +; RUN: opt %loadNPMPolly -polly-stmt-granularity=bb "-passes=scop(print)" -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=MSE ; ; Verify that the accesses are correctly expanded for MemoryKind::Array and MemoryKind::PHI. ; tmp_06_phi is not expanded because it need copy in. Index: polly/test/MaximalStaticExpansion/working_expansion.ll =================================================================== --- polly/test/MaximalStaticExpansion/working_expansion.ll +++ polly/test/MaximalStaticExpansion/working_expansion.ll @@ -1,4 +1,5 @@ ; RUN: opt %loadPolly -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s +; RUN: opt %loadNPMPolly "-passes=scop(print)" -disable-output < %s | FileCheck %s ; ; Verify that the accesses are correctly expanded for MemoryKind::Array ; Index: polly/test/MaximalStaticExpansion/working_expansion_multiple_dependences_per_statement.ll =================================================================== --- polly/test/MaximalStaticExpansion/working_expansion_multiple_dependences_per_statement.ll +++ polly/test/MaximalStaticExpansion/working_expansion_multiple_dependences_per_statement.ll @@ -1,4 +1,5 @@ ; RUN: opt %loadPolly -polly-stmt-granularity=bb -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s +; RUN: opt %loadNPMPolly -polly-stmt-granularity=bb "-passes=scop(print)" -disable-output < %s | FileCheck %s ; ; Verify that the accesses are correctly expanded ; Index: polly/test/MaximalStaticExpansion/working_expansion_multiple_instruction_per_statement.ll =================================================================== --- polly/test/MaximalStaticExpansion/working_expansion_multiple_instruction_per_statement.ll +++ polly/test/MaximalStaticExpansion/working_expansion_multiple_instruction_per_statement.ll @@ -1,4 +1,5 @@ ; RUN: opt %loadPolly -polly-stmt-granularity=bb -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s +; RUN: opt %loadNPMPolly -polly-stmt-granularity=bb "-passes=scop(print)" -disable-output < %s | FileCheck %s ; ; Verify that the accesses are correctly expanded ; Index: polly/test/MaximalStaticExpansion/working_phi_expansion.ll =================================================================== --- polly/test/MaximalStaticExpansion/working_phi_expansion.ll +++ polly/test/MaximalStaticExpansion/working_phi_expansion.ll @@ -1,5 +1,7 @@ ; RUN: opt %loadPolly -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s +; RUN: opt %loadNPMPolly "-passes=scop(print)" -disable-output < %s | FileCheck %s ; RUN: opt %loadPolly -polly-mse -polly-print-scops -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=MSE +; RUN: opt %loadPolly "-passes=scop(print)" -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=MSE ; ; Verify that the accesses are correctly expanded for MemoryKind::PHI ; tmp_04 is not expanded because it need copy-in. Index: polly/test/MaximalStaticExpansion/working_phi_two_scalars.ll =================================================================== --- polly/test/MaximalStaticExpansion/working_phi_two_scalars.ll +++ polly/test/MaximalStaticExpansion/working_phi_two_scalars.ll @@ -1,5 +1,7 @@ ; RUN: opt %loadPolly -polly-stmt-granularity=bb -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s +; RUN: opt %loadNPMPolly -polly-stmt-granularity=bb "-passes=scop(print)" -disable-output < %s | FileCheck %s ; RUN: opt %loadPolly -polly-stmt-granularity=bb -polly-mse -polly-print-scops -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=MSE +; RUN: opt %loadPolly -polly-stmt-granularity=bb "-passes=scop(print)" -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=MSE ; ; Verify that the accesses are correctly expanded for MemoryKind::PHI ; tmp_05 and tmp2_06 are not expanded because they need copy-in. Index: polly/test/MaximalStaticExpansion/working_value_expansion.ll =================================================================== --- polly/test/MaximalStaticExpansion/working_value_expansion.ll +++ polly/test/MaximalStaticExpansion/working_value_expansion.ll @@ -1,4 +1,5 @@ ; RUN: opt %loadPolly -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s +; RUN: opt %loadNPMPolly "-passes=scop(print)" -disable-output < %s | FileCheck %s ; ; Verify that the accesses are correctly expanded for MemoryKind::Value ;