diff options
| -rw-r--r-- | polly/include/polly/ScopDetection.h | 18 | ||||
| -rw-r--r-- | polly/include/polly/ScopInfo.h | 118 | ||||
| -rw-r--r-- | polly/include/polly/Support/ScopHelper.h | 3 | ||||
| -rw-r--r-- | polly/lib/Analysis/ScopDetection.cpp | 28 | ||||
| -rw-r--r-- | polly/lib/Analysis/ScopInfo.cpp | 219 |
5 files changed, 134 insertions, 252 deletions
diff --git a/polly/include/polly/ScopDetection.h b/polly/include/polly/ScopDetection.h index a3ef86d..4f7dc69 100644 --- a/polly/include/polly/ScopDetection.h +++ b/polly/include/polly/ScopDetection.h @@ -125,12 +125,6 @@ public: // Remember the valid regions RegionSet ValidRegions; - /// @brief Set of loops (used to remember loops in non-affine subregions). - using BoxedLoopsSetTy = SetVector<const Loop *>; - - /// @brief Set to remember non-affine branches in regions. - using NonAffineSubRegionSetTy = RegionSet; - /// @brief Context variables for SCoP detection. struct DetectionContext { Region &CurRegion; // The region to check. @@ -163,7 +157,7 @@ public: bool HasUnknownAccess; /// @brief The set of non-affine subregions in the region we analyze. - NonAffineSubRegionSetTy NonAffineSubRegionSet; + RegionSet NonAffineSubRegionSet; /// @brief The set of loops contained in non-affine regions. BoxedLoopsSetTy BoxedLoopsSet; @@ -540,16 +534,6 @@ public: /// @brief Return the detection context for @p R, nullptr if @p R was invalid. const DetectionContext *getDetectionContext(const Region *R) const; - /// @brief Return the set of loops in non-affine subregions for @p R. - const BoxedLoopsSetTy *getBoxedLoops(const Region *R) const; - - /// @brief Get the instruction to memory access mapping of the current - /// function for @p R. - const MapInsnToMemAcc *getInsnToMemAccMap(const Region *R) const; - - /// @brief Return the set of required invariant loads for @p R. - const InvariantLoadsSetTy *getRequiredInvariantLoads(const Region *R) const; - /// @brief Return the set of rejection causes for @p R. const RejectLog *lookupRejectionLog(const Region *R) const; diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h index 24ce19b..b8e64db 100644 --- a/polly/include/polly/ScopInfo.h +++ b/polly/include/polly/ScopInfo.h @@ -948,9 +948,7 @@ public: ScopStmt(Scop &parent, Region &R); /// Initialize members after all MemoryAccesses have been added. - /// - /// @param SD The ScopDetection analysis for the current function. - void init(ScopDetection &SD); + void init(LoopInfo &LI); private: /// Polyhedral description @@ -1083,10 +1081,10 @@ private: /// result scanning for GEP[s] is imprecise. Even though this is not a /// correctness problem, this imprecision may result in missed optimizations /// or non-optimal run-time checks. - void deriveAssumptionsFromGEP(GetElementPtrInst *Inst, ScopDetection &SD); + void deriveAssumptionsFromGEP(GetElementPtrInst *Inst, LoopInfo &LI); /// @brief Derive assumptions about parameter values. - void deriveAssumptions(ScopDetection &SD); + void deriveAssumptions(LoopInfo &LI); public: ~ScopStmt(); @@ -1355,6 +1353,9 @@ private: /// @brief Mapping from parameters to their ids. DenseMap<const SCEV *, isl_id *> ParameterIds; + /// @brief The context of the SCoP created during SCoP detection. + const ScopDetection::DetectionContext &DC; + /// Isl context. /// /// We need a shared_ptr with reference counter to delete the context when all @@ -1493,7 +1494,8 @@ private: InvariantEquivClassesTy InvariantEquivClasses; /// @brief Scop constructor; invoked from ScopInfo::buildScop. - Scop(Region &R, ScalarEvolution &SE, LoopInfo &LI); + Scop(Region &R, ScalarEvolution &SE, LoopInfo &LI, + const ScopDetection::DetectionContext &DC); /// @brief Get or create the access function set in a BasicBlock AccFuncSetType &getOrCreateAccessFunctions(const BasicBlock *BB) { @@ -1502,8 +1504,8 @@ private: //@} /// @brief Initialize this ScopInfo . - void init(AliasAnalysis &AA, AssumptionCache &AC, ScopDetection &SD, - DominatorTree &DT, LoopInfo &LI); + void init(AliasAnalysis &AA, AssumptionCache &AC, DominatorTree &DT, + LoopInfo &LI); /// @brief Propagate domains that are known due to graph properties. /// @@ -1525,13 +1527,11 @@ private: /// @param BB The block for which the domain is currently propagated. /// @param BBLoop The innermost affine loop surrounding @p BB. /// @param FinishedExitBlocks Set of region exits the domain was set for. - /// @param SD The ScopDetection analysis for the current function. /// @param LI The LoopInfo for the current function. /// void propagateDomainConstraintsToRegionExit( BasicBlock *BB, Loop *BBLoop, - SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks, ScopDetection &SD, - LoopInfo &LI); + SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks, LoopInfo &LI); /// @brief Compute the union of predecessor domains for @p BB. /// @@ -1541,14 +1541,12 @@ private: /// /// @param BB The block for which the predecessor domains are collected. /// @param Domain The domain under which BB is executed. - /// @param SD The ScopDetection analysis for the current function. /// @param DT The DominatorTree for the current function. /// @param LI The LoopInfo for the current function. /// /// @returns The domain under which @p BB is executed. __isl_give isl_set *getPredecessorDomainConstraints(BasicBlock *BB, isl_set *Domain, - ScopDetection &SD, DominatorTree &DT, LoopInfo &LI); @@ -1563,24 +1561,21 @@ private: /// @brief Compute the branching constraints for each basic block in @p R. /// /// @param R The region we currently build branching conditions for. - /// @param SD The ScopDetection analysis for the current function. /// @param DT The DominatorTree for the current function. /// @param LI The LoopInfo for the current function. /// /// @returns True if there was no problem and false otherwise. - bool buildDomainsWithBranchConstraints(Region *R, ScopDetection &SD, - DominatorTree &DT, LoopInfo &LI); + bool buildDomainsWithBranchConstraints(Region *R, DominatorTree &DT, + LoopInfo &LI); /// @brief Propagate the domain constraints through the region @p R. /// /// @param R The region we currently build branching conditions for. - /// @param SD The ScopDetection analysis for the current function. /// @param DT The DominatorTree for the current function. /// @param LI The LoopInfo for the current function. /// /// @returns True if there was no problem and false otherwise. - bool propagateDomainConstraints(Region *R, ScopDetection &SD, - DominatorTree &DT, LoopInfo &LI); + bool propagateDomainConstraints(Region *R, DominatorTree &DT, LoopInfo &LI); /// @brief Propagate invalid domains of statements through @p R. /// @@ -1590,24 +1585,20 @@ private: /// replaced by an empty set. Later those will be removed completely. /// /// @param R The currently traversed region. - /// @param SD The ScopDetection analysis for the current function. /// @param DT The DominatorTree for the current function. /// @param LI The LoopInfo for the current function. /// /// @returns True if there was no problem and false otherwise. - bool propagateInvalidStmtDomains(Region *R, ScopDetection &SD, - DominatorTree &DT, LoopInfo &LI); + bool propagateInvalidStmtDomains(Region *R, DominatorTree &DT, LoopInfo &LI); /// @brief Compute the domain for each basic block in @p R. /// /// @param R The region we currently traverse. - /// @param SD The ScopDetection analysis for the current function. /// @param DT The DominatorTree for the current function. /// @param LI The LoopInfo for the current function. /// /// @returns True if there was no problem and false otherwise. - bool buildDomains(Region *R, ScopDetection &SD, DominatorTree &DT, - LoopInfo &LI); + bool buildDomains(Region *R, DominatorTree &DT, LoopInfo &LI); /// @brief Add parameter constraints to @p C that imply a non-empty domain. __isl_give isl_set *addNonEmptyDomainConstraints(__isl_take isl_set *C) const; @@ -1627,9 +1618,7 @@ private: /// consequence Scop::getIdForParam() will only return an id for the /// representing element of each equivalence class, thus for each required /// invariant location. - /// - /// @param SD The ScopDetection analysis for the current function. - void buildInvariantEquivalenceClasses(ScopDetection &SD); + void buildInvariantEquivalenceClasses(); /// @brief Check if a memory access can be hoisted. /// @@ -1654,8 +1643,7 @@ private: /// for (int j = 1; j < Bound[1]; j++) /// ... /// - /// @param SD The ScopDetection analysis for the current function. - void verifyInvariantLoads(ScopDetection &SD); + void verifyInvariantLoads(); /// @brief Hoist invariant memory loads and check for required ones. /// @@ -1675,8 +1663,7 @@ private: /// Common inv. loads: V, A[0][0], LB[0], LB[1] /// Required inv. loads: LB[0], LB[1], (V, if it may alias with A or LB) /// - /// @param SD The ScopDetection analysis for the current function. - void hoistInvariantLoads(ScopDetection &SD); + void hoistInvariantLoads(); /// @brief Add invariant loads listed in @p InvMAs with the domain of @p Stmt. void addInvariantLoads(ScopStmt &Stmt, MemoryAccessList &InvMAs); @@ -1732,9 +1719,8 @@ private: /// @brief Construct the schedule of this SCoP. /// - /// @param SD The ScopDetection analysis for the current function. /// @param LI The LoopInfo for the current function. - void buildSchedule(ScopDetection &SD, LoopInfo &LI); + void buildSchedule(LoopInfo &LI); /// @brief A loop stack element to keep track of per-loop information during /// schedule construction. @@ -1773,10 +1759,8 @@ private: /// @param R The region which to process. /// @param LoopStack A stack of loops that are currently under /// construction. - /// @param SD The ScopDetection analysis for the current function. /// @param LI The LoopInfo for the current function. - void buildSchedule(Region *R, LoopStackTy &LoopStack, ScopDetection &SD, - LoopInfo &LI); + void buildSchedule(Region *R, LoopStackTy &LoopStack, LoopInfo &LI); /// @brief Build Schedule for the region node @p RN and add the derived /// information to @p LoopStack. @@ -1791,10 +1775,8 @@ private: /// @param RN The RegionNode region traversed. /// @param LoopStack A stack of loops that are currently under /// construction. - /// @param SD The ScopDetection analysis for the current function. /// @param LI The LoopInfo for the current function. - void buildSchedule(RegionNode *RN, LoopStackTy &LoopStack, ScopDetection &SD, - LoopInfo &LI); + void buildSchedule(RegionNode *RN, LoopStackTy &LoopStack, LoopInfo &LI); /// @brief Collect all memory access relations of a given type. /// @@ -2051,6 +2033,15 @@ public: const_reverse_iterator rend() const { return Stmts.rend(); } //@} + const InvariantLoadsSetTy &getRequiredInvariantLoads() const { + return DC.RequiredILS; + } + const BoxedLoopsSetTy &getBoxedLoops() const { return DC.BoxedLoopsSet; } + bool isNonAffineSubRegion(const Region *R) { + return DC.NonAffineSubRegionSet.count(R); + } + const MapInsnToMemAcc &getInsnToMemAccMap() const { return DC.InsnToMemAcc; } + /// @brief Return the (possibly new) ScopArrayInfo object for @p Access. /// /// @param ElementType The type of the elements stored in this array. @@ -2235,14 +2226,9 @@ class ScopInfo : public RegionPass { /// @param Inst The Load/Store instruction that access the memory /// @param L The parent loop of the instruction /// @param R The region on which to build the data access dictionary. - /// @param BoxedLoops The set of loops that are overapproximated in @p R. - /// @param ScopRIL The required invariant loads equivalence classes. /// /// @returns True if the access could be built, False otherwise. - bool - buildAccessMultiDimFixed(MemAccInst Inst, Loop *L, Region *R, - const ScopDetection::BoxedLoopsSetTy *BoxedLoops, - const InvariantLoadsSetTy &ScopRIL); + bool buildAccessMultiDimFixed(MemAccInst Inst, Loop *L, Region *R); /// @brief Try to build a multi-dimensional parameteric sized MemoryAccess /// from the Load/Store instruction. @@ -2250,42 +2236,27 @@ class ScopInfo : public RegionPass { /// @param Inst The Load/Store instruction that access the memory /// @param L The parent loop of the instruction /// @param R The region on which to build the data access dictionary. - /// @param BoxedLoops The set of loops that are overapproximated in @p R. - /// @param ScopRIL The required invariant loads equivalence classes. - /// @param InsnToMemAcc The Instruction to MemoryAccess mapping /// /// @returns True if the access could be built, False otherwise. - bool - buildAccessMultiDimParam(MemAccInst Inst, Loop *L, Region *R, - const ScopDetection::BoxedLoopsSetTy *BoxedLoops, - const InvariantLoadsSetTy &ScopRIL, - const MapInsnToMemAcc &InsnToMemAcc); + bool buildAccessMultiDimParam(MemAccInst Inst, Loop *L, Region *R); /// @brief Try to build a MemoryAccess for a memory intrinsic. /// /// @param Inst The instruction that access the memory /// @param L The parent loop of the instruction /// @param R The region on which to build the data access dictionary. - /// @param BoxedLoops The set of loops that are overapproximated in @p R. - /// @param ScopRIL The required invariant loads equivalence classes. /// /// @returns True if the access could be built, False otherwise. - bool buildAccessMemIntrinsic(MemAccInst Inst, Loop *L, Region *R, - const ScopDetection::BoxedLoopsSetTy *BoxedLoops, - const InvariantLoadsSetTy &ScopRIL); + bool buildAccessMemIntrinsic(MemAccInst Inst, Loop *L, Region *R); /// @brief Try to build a MemoryAccess for a call instruction. /// /// @param Inst The call instruction that access the memory /// @param L The parent loop of the instruction /// @param R The region on which to build the data access dictionary. - /// @param BoxedLoops The set of loops that are overapproximated in @p R. - /// @param ScopRIL The required invariant loads equivalence classes. /// /// @returns True if the access could be built, False otherwise. - bool buildAccessCallInst(MemAccInst Inst, Loop *L, Region *R, - const ScopDetection::BoxedLoopsSetTy *BoxedLoops, - const InvariantLoadsSetTy &ScopRIL); + bool buildAccessCallInst(MemAccInst Inst, Loop *L, Region *R); /// @brief Build a single-dimensional parameteric sized MemoryAccess /// from the Load/Store instruction. @@ -2293,24 +2264,14 @@ class ScopInfo : public RegionPass { /// @param Inst The Load/Store instruction that access the memory /// @param L The parent loop of the instruction /// @param R The region on which to build the data access dictionary. - /// @param BoxedLoops The set of loops that are overapproximated in @p R. - /// @param ScopRIL The required invariant loads equivalence classes. - void buildAccessSingleDim(MemAccInst Inst, Loop *L, Region *R, - const ScopDetection::BoxedLoopsSetTy *BoxedLoops, - const InvariantLoadsSetTy &ScopRIL); + void buildAccessSingleDim(MemAccInst Inst, Loop *L, Region *R); /// @brief Build an instance of MemoryAccess from the Load/Store instruction. /// /// @param Inst The Load/Store instruction that access the memory /// @param L The parent loop of the instruction /// @param R The region on which to build the data access dictionary. - /// @param BoxedLoops The set of loops that are overapproximated in @p R. - /// @param ScopRIL The required invariant loads equivalence classes. - /// @param InsnToMemAcc The Instruction to MemoryAccess mapping. - void buildMemoryAccess(MemAccInst Inst, Loop *L, Region *R, - const ScopDetection::BoxedLoopsSetTy *BoxedLoops, - const InvariantLoadsSetTy &ScopRIL, - const MapInsnToMemAcc &InsnToMemAcc); + void buildMemoryAccess(MemAccInst Inst, Loop *L, Region *R); /// @brief Analyze and extract the cross-BB scalar dependences (or, /// dataflow dependencies) of an instruction. @@ -2339,8 +2300,7 @@ class ScopInfo : public RegionPass { /// @param R The SCoP region. /// @param SR A subregion of @p R. /// @param InsnToMemAcc The Instruction to MemoryAccess mapping. - void buildAccessFunctions(Region &R, Region &SR, - const MapInsnToMemAcc &InsnToMemAcc); + void buildAccessFunctions(Region &R, Region &SR); /// @brief Create ScopStmt for all BBs and non-affine subregions of @p SR. /// @@ -2355,11 +2315,9 @@ class ScopInfo : public RegionPass { /// /// @param R The SCoP region. /// @param BB A basic block in @p R. - /// @param InsnToMemAcc The Instruction to MemoryAccess mapping. /// @param NonAffineSubRegion The non affine sub-region @p BB is in. /// @param IsExitBlock Flag to indicate that @p BB is in the exit BB. void buildAccessFunctions(Region &R, BasicBlock &BB, - const MapInsnToMemAcc &InsnToMemAcc, Region *NonAffineSubRegion = nullptr, bool IsExitBlock = false); diff --git a/polly/include/polly/Support/ScopHelper.h b/polly/include/polly/Support/ScopHelper.h index 34a6287a..ea22a84 100644 --- a/polly/include/polly/Support/ScopHelper.h +++ b/polly/include/polly/Support/ScopHelper.h @@ -44,6 +44,9 @@ using InvariantLoadsSetTy = llvm::SetVector<llvm::AssertingVH<llvm::LoadInst>>; /// @brief Set type for parameters. using ParameterSetTy = llvm::SetVector<const llvm::SCEV *>; +/// @brief Set of loops (used to remember loops in non-affine subregions). +using BoxedLoopsSetTy = llvm::SetVector<const llvm::Loop *>; + /// @brief Utility proxy to wrap the common members of LoadInst and StoreInst. /// /// This works like the LLVM utility class CallSite, ie. it forwards all calls diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp index cf71b89..bfc9a99 100644 --- a/polly/lib/Analysis/ScopDetection.cpp +++ b/polly/lib/Analysis/ScopDetection.cpp @@ -1493,13 +1493,6 @@ bool ScopDetection::runOnFunction(llvm::Function &F) { return false; } -bool ScopDetection::isNonAffineSubRegion(const Region *SubR, - const Region *ScopR) const { - const DetectionContext *DC = getDetectionContext(ScopR); - assert(DC && "ScopR is no valid region!"); - return DC->NonAffineSubRegionSet.count(SubR); -} - const ScopDetection::DetectionContext * ScopDetection::getDetectionContext(const Region *R) const { auto DCMIt = DetectionContextMap.find(getBBPairForRegion(R)); @@ -1508,27 +1501,6 @@ ScopDetection::getDetectionContext(const Region *R) const { return &DCMIt->second; } -const ScopDetection::BoxedLoopsSetTy * -ScopDetection::getBoxedLoops(const Region *R) const { - const DetectionContext *DC = getDetectionContext(R); - assert(DC && "ScopR is no valid region!"); - return &DC->BoxedLoopsSet; -} - -const MapInsnToMemAcc * -ScopDetection::getInsnToMemAccMap(const Region *R) const { - const DetectionContext *DC = getDetectionContext(R); - assert(DC && "ScopR is no valid region!"); - return &DC->InsnToMemAcc; -} - -const InvariantLoadsSetTy * -ScopDetection::getRequiredInvariantLoads(const Region *R) const { - const DetectionContext *DC = getDetectionContext(R); - assert(DC && "ScopR is no valid region!"); - return &DC->RequiredILS; -} - const RejectLog *ScopDetection::lookupRejectionLog(const Region *R) const { const DetectionContext *DC = getDetectionContext(R); return DC ? &DC->Log : nullptr; diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp index b12af38..6c2612a 100644 --- a/polly/lib/Analysis/ScopInfo.cpp +++ b/polly/lib/Analysis/ScopInfo.cpp @@ -1402,15 +1402,14 @@ void ScopStmt::buildDomain() { Domain = isl_set_set_tuple_id(Domain, Id); } -void ScopStmt::deriveAssumptionsFromGEP(GetElementPtrInst *GEP, - ScopDetection &SD) { +void ScopStmt::deriveAssumptionsFromGEP(GetElementPtrInst *GEP, LoopInfo &LI) { isl_ctx *Ctx = Parent.getIslCtx(); isl_local_space *LSpace = isl_local_space_from_space(getDomainSpace()); Type *Ty = GEP->getPointerOperandType(); ScalarEvolution &SE = *Parent.getSE(); // The set of loads that are required to be invariant. - auto &ScopRIL = *SD.getRequiredInvariantLoads(&Parent.getRegion()); + auto &ScopRIL = Parent.getRequiredInvariantLoads(); std::vector<const SCEV *> Subscripts; std::vector<int> Sizes; @@ -1430,7 +1429,7 @@ void ScopStmt::deriveAssumptionsFromGEP(GetElementPtrInst *GEP, auto *Expr = Subscripts[i + IndexOffset]; auto Size = Sizes[i]; - auto *Scope = SD.getLI()->getLoopFor(getEntryBlock()); + auto *Scope = LI.getLoopFor(getEntryBlock()); InvariantLoadsSetTy AccessILS; if (!isAffineExpr(&Parent.getRegion(), Scope, Expr, SE, &AccessILS)) continue; @@ -1468,7 +1467,7 @@ void ScopStmt::deriveAssumptionsFromGEP(GetElementPtrInst *GEP, isl_set_free(NotExecuted); } -void ScopStmt::deriveAssumptions(ScopDetection &SD) { +void ScopStmt::deriveAssumptions(LoopInfo &LI) { for (auto *MA : *this) { if (!MA->isArrayKind()) continue; @@ -1477,7 +1476,7 @@ void ScopStmt::deriveAssumptions(ScopDetection &SD) { auto *GEP = dyn_cast_or_null<GetElementPtrInst>(Acc.getPointerOperand()); if (GEP) - deriveAssumptionsFromGEP(GEP, SD); + deriveAssumptionsFromGEP(GEP, LI); } } @@ -1503,14 +1502,14 @@ ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb) BaseName = getIslCompatibleName("Stmt_", &bb, ""); } -void ScopStmt::init(ScopDetection &SD) { +void ScopStmt::init(LoopInfo &LI) { assert(!Domain && "init must be called only once"); buildDomain(); collectSurroundingLoops(); buildAccessRelations(); - deriveAssumptions(SD); + deriveAssumptions(LI); if (DetectReductions) checkForReductions(); @@ -1996,10 +1995,10 @@ void Scop::addUserContext() { isl_space_free(Space); } -void Scop::buildInvariantEquivalenceClasses(ScopDetection &SD) { +void Scop::buildInvariantEquivalenceClasses() { DenseMap<std::pair<const SCEV *, Type *>, LoadInst *> EquivClasses; - const InvariantLoadsSetTy &RIL = *SD.getRequiredInvariantLoads(&getRegion()); + const InvariantLoadsSetTy &RIL = getRequiredInvariantLoads(); for (LoadInst *LInst : RIL) { const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand()); @@ -2267,10 +2266,9 @@ __isl_give isl_set *Scop::getDomainConditions(BasicBlock *BB) const { return getDomainConditions(BBR->getEntry()); } -bool Scop::buildDomains(Region *R, ScopDetection &SD, DominatorTree &DT, - LoopInfo &LI) { +bool Scop::buildDomains(Region *R, DominatorTree &DT, LoopInfo &LI) { - bool IsOnlyNonAffineRegion = SD.isNonAffineSubRegion(R, R); + bool IsOnlyNonAffineRegion = isNonAffineSubRegion(R); auto *EntryBB = R->getEntry(); auto *L = IsOnlyNonAffineRegion ? nullptr : LI.getLoopFor(EntryBB); int LD = getRelativeLoopDepth(L); @@ -2290,10 +2288,10 @@ bool Scop::buildDomains(Region *R, ScopDetection &SD, DominatorTree &DT, if (IsOnlyNonAffineRegion) return !containsErrorBlock(R->getNode(), *R, LI, DT); - if (!buildDomainsWithBranchConstraints(R, SD, DT, LI)) + if (!buildDomainsWithBranchConstraints(R, DT, LI)) return false; - if (!propagateDomainConstraints(R, SD, DT, LI)) + if (!propagateDomainConstraints(R, DT, LI)) return false; // Error blocks and blocks dominated by them have been assumed to never be @@ -2308,15 +2306,14 @@ bool Scop::buildDomains(Region *R, ScopDetection &SD, DominatorTree &DT, // with an empty set. Additionally, we will record for each block under which // parameter combination it would be reached via an error block in its // InvalidDomain. This information is needed during load hoisting. - if (!propagateInvalidStmtDomains(R, SD, DT, LI)) + if (!propagateInvalidStmtDomains(R, DT, LI)) return false; return true; } -static Loop * -getFirstNonBoxedLoopFor(BasicBlock *BB, LoopInfo &LI, - const ScopDetection::BoxedLoopsSetTy &BoxedLoops) { +static Loop *getFirstNonBoxedLoopFor(BasicBlock *BB, LoopInfo &LI, + const BoxedLoopsSetTy &BoxedLoops) { auto *L = LI.getLoopFor(BB); while (BoxedLoops.count(L)) L = L->getParentLoop(); @@ -2373,9 +2370,9 @@ static __isl_give isl_set *adjustDomainDimensions(Scop &S, return Dom; } -bool Scop::propagateInvalidStmtDomains(Region *R, ScopDetection &SD, - DominatorTree &DT, LoopInfo &LI) { - auto &BoxedLoops = *SD.getBoxedLoops(&getRegion()); +bool Scop::propagateInvalidStmtDomains(Region *R, DominatorTree &DT, + LoopInfo &LI) { + auto &BoxedLoops = getBoxedLoops(); ReversePostOrderTraversal<Region *> RTraversal(R); for (auto *RN : RTraversal) { @@ -2384,8 +2381,8 @@ bool Scop::propagateInvalidStmtDomains(Region *R, ScopDetection &SD, // subregions. if (RN->isSubRegion()) { Region *SubRegion = RN->getNodeAs<Region>(); - if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) { - propagateInvalidStmtDomains(SubRegion, SD, DT, LI); + if (!isNonAffineSubRegion(SubRegion)) { + propagateInvalidStmtDomains(SubRegion, DT, LI); continue; } } @@ -2459,8 +2456,7 @@ bool Scop::propagateInvalidStmtDomains(Region *R, ScopDetection &SD, void Scop::propagateDomainConstraintsToRegionExit( BasicBlock *BB, Loop *BBLoop, - SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks, ScopDetection &SD, - LoopInfo &LI) { + SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks, LoopInfo &LI) { // Check if the block @p BB is the entry of a region. If so we propagate it's // domain to the exit block of the region. Otherwise we are done. @@ -2470,7 +2466,7 @@ void Scop::propagateDomainConstraintsToRegionExit( if (!BBReg || BBReg->getEntry() != BB || !R.contains(ExitBB)) return; - auto &BoxedLoops = *SD.getBoxedLoops(&getRegion()); + auto &BoxedLoops = getBoxedLoops(); // Do not propagate the domain if there is a loop backedge inside the region // that would prevent the exit block from beeing executed. auto *L = BBLoop; @@ -2506,10 +2502,8 @@ void Scop::propagateDomainConstraintsToRegionExit( FinishedExitBlocks.insert(ExitBB); } -bool Scop::buildDomainsWithBranchConstraints(Region *R, ScopDetection &SD, - DominatorTree &DT, LoopInfo &LI) { - auto &BoxedLoops = *SD.getBoxedLoops(&getRegion()); - +bool Scop::buildDomainsWithBranchConstraints(Region *R, DominatorTree &DT, + LoopInfo &LI) { // To create the domain for each block in R we iterate over all blocks and // subregions in R and propagate the conditions under which the current region // element is executed. To this end we iterate in reverse post order over R as @@ -2529,8 +2523,8 @@ bool Scop::buildDomainsWithBranchConstraints(Region *R, ScopDetection &SD, // subregions. if (RN->isSubRegion()) { Region *SubRegion = RN->getNodeAs<Region>(); - if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) { - if (!buildDomainsWithBranchConstraints(SubRegion, SD, DT, LI)) + if (!isNonAffineSubRegion(SubRegion)) { + if (!buildDomainsWithBranchConstraints(SubRegion, DT, LI)) return false; continue; } @@ -2553,8 +2547,7 @@ bool Scop::buildDomainsWithBranchConstraints(Region *R, ScopDetection &SD, auto *BBLoop = getRegionNodeLoop(RN, LI); // Propagate the domain from BB directly to blocks that have a superset // domain, at the moment only region exit nodes of regions that start in BB. - propagateDomainConstraintsToRegionExit(BB, BBLoop, FinishedExitBlocks, SD, - LI); + propagateDomainConstraintsToRegionExit(BB, BBLoop, FinishedExitBlocks, LI); // If all successors of BB have been set a domain through the propagation // above we do not need to build condition sets but can just skip this @@ -2607,6 +2600,7 @@ bool Scop::buildDomainsWithBranchConstraints(Region *R, ScopDetection &SD, continue; } + auto &BoxedLoops = getBoxedLoops(); auto *SuccBBLoop = getFirstNonBoxedLoopFor(SuccBB, LI, BoxedLoops); CondSet = adjustDomainDimensions(*this, CondSet, BBLoop, SuccBBLoop); @@ -2640,7 +2634,6 @@ bool Scop::buildDomainsWithBranchConstraints(Region *R, ScopDetection &SD, __isl_give isl_set *Scop::getPredecessorDomainConstraints(BasicBlock *BB, isl_set *Domain, - ScopDetection &SD, DominatorTree &DT, LoopInfo &LI) { // If @p BB is the ScopEntry we are done @@ -2648,7 +2641,7 @@ __isl_give isl_set *Scop::getPredecessorDomainConstraints(BasicBlock *BB, return isl_set_universe(isl_set_get_space(Domain)); // The set of boxed loops (loops in non-affine subregions) for this SCoP. - auto &BoxedLoops = *SD.getBoxedLoops(&getRegion()); + auto &BoxedLoops = getBoxedLoops(); // The region info of this function. auto &RI = *R.getRegionInfo(); @@ -2698,8 +2691,8 @@ __isl_give isl_set *Scop::getPredecessorDomainConstraints(BasicBlock *BB, return PredDom; } -bool Scop::propagateDomainConstraints(Region *R, ScopDetection &SD, - DominatorTree &DT, LoopInfo &LI) { +bool Scop::propagateDomainConstraints(Region *R, DominatorTree &DT, + LoopInfo &LI) { // Iterate over the region R and propagate the domain constrains from the // predecessors to the current node. In contrast to the // buildDomainsWithBranchConstraints function, this one will pull the domain @@ -2716,8 +2709,8 @@ bool Scop::propagateDomainConstraints(Region *R, ScopDetection &SD, // subregions. if (RN->isSubRegion()) { Region *SubRegion = RN->getNodeAs<Region>(); - if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) { - if (!propagateDomainConstraints(SubRegion, SD, DT, LI)) + if (!isNonAffineSubRegion(SubRegion)) { + if (!propagateDomainConstraints(SubRegion, DT, LI)) return false; continue; } @@ -2728,7 +2721,7 @@ bool Scop::propagateDomainConstraints(Region *R, ScopDetection &SD, assert(Domain); // Under the union of all predecessor conditions we can reach this block. - auto *PredDom = getPredecessorDomainConstraints(BB, Domain, SD, DT, LI); + auto *PredDom = getPredecessorDomainConstraints(BB, Domain, DT, LI); Domain = isl_set_coalesce(isl_set_intersect(Domain, PredDom)); Domain = isl_set_align_params(Domain, getParamSpace()); @@ -3058,22 +3051,23 @@ static Loop *getLoopSurroundingRegion(Region &R, LoopInfo &LI) { return L ? (R.contains(L) ? L->getParentLoop() : L) : nullptr; } -Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, LoopInfo &LI) +Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, LoopInfo &LI, + const ScopDetection::DetectionContext &DC) : SE(&ScalarEvolution), R(R), IsOptimized(false), HasSingleExitEdge(R.getExitingBlock()), HasErrorBlock(false), - MaxLoopDepth(0), IslCtx(isl_ctx_alloc(), isl_ctx_free), Context(nullptr), - Affinator(this, LI), AssumedContext(nullptr), InvalidContext(nullptr), - Schedule(nullptr) { + MaxLoopDepth(0), DC(DC), IslCtx(isl_ctx_alloc(), isl_ctx_free), + Context(nullptr), Affinator(this, LI), AssumedContext(nullptr), + InvalidContext(nullptr), Schedule(nullptr) { if (IslOnErrorAbort) isl_options_set_on_error(getIslCtx(), ISL_ON_ERROR_ABORT); buildContext(); } -void Scop::init(AliasAnalysis &AA, AssumptionCache &AC, ScopDetection &SD, - DominatorTree &DT, LoopInfo &LI) { - buildInvariantEquivalenceClasses(SD); +void Scop::init(AliasAnalysis &AA, AssumptionCache &AC, DominatorTree &DT, + LoopInfo &LI) { + buildInvariantEquivalenceClasses(); - if (!buildDomains(&R, SD, DT, LI)) + if (!buildDomains(&R, DT, LI)) return; addUserAssumptions(AC, DT, LI); @@ -3086,7 +3080,7 @@ void Scop::init(AliasAnalysis &AA, AssumptionCache &AC, ScopDetection &SD, // The ScopStmts now have enough information to initialize themselves. for (ScopStmt &Stmt : Stmts) - Stmt.init(SD); + Stmt.init(LI); // Check early for profitability. Afterwards it cannot change anymore, // only the runtime context could become infeasible. @@ -3095,7 +3089,7 @@ void Scop::init(AliasAnalysis &AA, AssumptionCache &AC, ScopDetection &SD, return; } - buildSchedule(SD, LI); + buildSchedule(LI); updateAccessDimensionality(); realignParams(); @@ -3109,8 +3103,8 @@ void Scop::init(AliasAnalysis &AA, AssumptionCache &AC, ScopDetection &SD, simplifyContexts(); buildAliasChecks(AA); - hoistInvariantLoads(SD); - verifyInvariantLoads(SD); + hoistInvariantLoads(); + verifyInvariantLoads(); simplifySCoP(true, DT, LI); // Check late for a feasible runtime context because profitability did not @@ -3450,8 +3444,8 @@ bool Scop::isHoistableAccess(MemoryAccess *Access, return true; } -void Scop::verifyInvariantLoads(ScopDetection &SD) { - auto &RIL = *SD.getRequiredInvariantLoads(&getRegion()); +void Scop::verifyInvariantLoads() { + auto &RIL = getRequiredInvariantLoads(); for (LoadInst *LI : RIL) { assert(LI && getRegion().contains(LI)); ScopStmt *Stmt = getStmtFor(LI); @@ -3462,7 +3456,7 @@ void Scop::verifyInvariantLoads(ScopDetection &SD) { } } -void Scop::hoistInvariantLoads(ScopDetection &SD) { +void Scop::hoistInvariantLoads() { if (!PollyInvariantLoadHoisting) return; @@ -4041,10 +4035,10 @@ void Scop::addScopStmt(BasicBlock *BB, Region *R) { } } -void Scop::buildSchedule(ScopDetection &SD, LoopInfo &LI) { +void Scop::buildSchedule(LoopInfo &LI) { Loop *L = getLoopSurroundingRegion(getRegion(), LI); LoopStackTy LoopStack({LoopStackElementTy(L, nullptr, 0)}); - buildSchedule(getRegion().getNode(), LoopStack, SD, LI); + buildSchedule(getRegion().getNode(), LoopStack, LI); assert(LoopStack.size() == 1 && LoopStack.back().L == L); Schedule = LoopStack[0].Schedule; } @@ -4073,8 +4067,7 @@ void Scop::buildSchedule(ScopDetection &SD, LoopInfo &LI) { /// sub-regions or blocks that are outside the last loop on the @p LoopStack. /// These region-nodes are then queue and only traverse after the all nodes /// within the current loop have been processed. -void Scop::buildSchedule(Region *R, LoopStackTy &LoopStack, ScopDetection &SD, - LoopInfo &LI) { +void Scop::buildSchedule(Region *R, LoopStackTy &LoopStack, LoopInfo &LI) { Loop *OuterScopLoop = getLoopSurroundingRegion(getRegion(), LI); ReversePostOrderTraversal<Region *> RTraversal(R); @@ -4114,19 +4107,18 @@ void Scop::buildSchedule(Region *R, LoopStackTy &LoopStack, ScopDetection &SD, } LoopStack.push_back({L, nullptr, 0}); } - buildSchedule(RN, LoopStack, SD, LI); + buildSchedule(RN, LoopStack, LI); } return; } -void Scop::buildSchedule(RegionNode *RN, LoopStackTy &LoopStack, - ScopDetection &SD, LoopInfo &LI) { +void Scop::buildSchedule(RegionNode *RN, LoopStackTy &LoopStack, LoopInfo &LI) { if (RN->isSubRegion()) { auto *LocalRegion = RN->getNodeAs<Region>(); - if (!SD.isNonAffineSubRegion(LocalRegion, &getRegion())) { - buildSchedule(LocalRegion, LoopStack, SD, LI); + if (!isNonAffineSubRegion(LocalRegion)) { + buildSchedule(LocalRegion, LoopStack, LI); return; } } @@ -4270,10 +4262,7 @@ void ScopInfo::buildEscapingDependences(Instruction *Inst) { } } -bool ScopInfo::buildAccessMultiDimFixed( - MemAccInst Inst, Loop *L, Region *R, - const ScopDetection::BoxedLoopsSetTy *BoxedLoops, - const InvariantLoadsSetTy &ScopRIL) { +bool ScopInfo::buildAccessMultiDimFixed(MemAccInst Inst, Loop *L, Region *R) { Value *Val = Inst.getValueOperand(); Type *ElementType = Val->getType(); Value *Address = Inst.getPointerOperand(); @@ -4317,6 +4306,7 @@ bool ScopInfo::buildAccessMultiDimFixed( std::vector<const SCEV *> SizesSCEV; + const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads(); for (auto *Subscript : Subscripts) { InvariantLoadsSetTy AccessILS; if (!isAffineExpr(R, L, Subscript, *SE, &AccessILS)) @@ -4339,10 +4329,7 @@ bool ScopInfo::buildAccessMultiDimFixed( return true; } -bool ScopInfo::buildAccessMultiDimParam( - MemAccInst Inst, Loop *L, Region *R, - const ScopDetection::BoxedLoopsSetTy *BoxedLoops, - const InvariantLoadsSetTy &ScopRIL, const MapInsnToMemAcc &InsnToMemAcc) { +bool ScopInfo::buildAccessMultiDimParam(MemAccInst Inst, Loop *L, Region *R) { if (!PollyDelinearize) return false; @@ -4360,6 +4347,7 @@ bool ScopInfo::buildAccessMultiDimParam( assert(BasePointer && "Could not find base pointer"); AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer); + auto &InsnToMemAcc = scop->getInsnToMemAccMap(); auto AccItr = InsnToMemAcc.find(Inst); if (AccItr == InsnToMemAcc.end()) return false; @@ -4384,10 +4372,7 @@ bool ScopInfo::buildAccessMultiDimParam( return true; } -bool ScopInfo::buildAccessMemIntrinsic( - MemAccInst Inst, Loop *L, Region *R, - const ScopDetection::BoxedLoopsSetTy *BoxedLoops, - const InvariantLoadsSetTy &ScopRIL) { +bool ScopInfo::buildAccessMemIntrinsic(MemAccInst Inst, Loop *L, Region *R) { auto *MemIntr = dyn_cast_or_null<MemIntrinsic>(Inst); if (MemIntr == nullptr) @@ -4398,6 +4383,7 @@ bool ScopInfo::buildAccessMemIntrinsic( // Check if the length val is actually affine or if we overapproximate it InvariantLoadsSetTy AccessILS; + const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads(); bool LengthIsAffine = isAffineExpr(R, L, LengthVal, *SE, &AccessILS); for (LoadInst *LInst : AccessILS) if (!ScopRIL.count(LInst)) @@ -4449,10 +4435,7 @@ bool ScopInfo::buildAccessMemIntrinsic( return true; } -bool ScopInfo::buildAccessCallInst( - MemAccInst Inst, Loop *L, Region *R, - const ScopDetection::BoxedLoopsSetTy *BoxedLoops, - const InvariantLoadsSetTy &ScopRIL) { +bool ScopInfo::buildAccessCallInst(MemAccInst Inst, Loop *L, Region *R) { auto *CI = dyn_cast_or_null<CallInst>(Inst); if (CI == nullptr) @@ -4495,10 +4478,7 @@ bool ScopInfo::buildAccessCallInst( return true; } -void ScopInfo::buildAccessSingleDim( - MemAccInst Inst, Loop *L, Region *R, - const ScopDetection::BoxedLoopsSetTy *BoxedLoops, - const InvariantLoadsSetTy &ScopRIL) { +void ScopInfo::buildAccessSingleDim(MemAccInst Inst, Loop *L, Region *R) { Value *Address = Inst.getPointerOperand(); Value *Val = Inst.getValueOperand(); Type *ElementType = Val->getType(); @@ -4514,18 +4494,18 @@ void ScopInfo::buildAccessSingleDim( // Check if the access depends on a loop contained in a non-affine subregion. bool isVariantInNonAffineLoop = false; - if (BoxedLoops) { - SetVector<const Loop *> Loops; - findLoops(AccessFunction, Loops); - for (const Loop *L : Loops) - if (BoxedLoops->count(L)) - isVariantInNonAffineLoop = true; - } + SetVector<const Loop *> Loops; + auto &BoxedLoops = scop->getBoxedLoops(); + findLoops(AccessFunction, Loops); + for (const Loop *L : Loops) + if (BoxedLoops.count(L)) + isVariantInNonAffineLoop = true; InvariantLoadsSetTy AccessILS; bool IsAffine = !isVariantInNonAffineLoop && isAffineExpr(R, L, AccessFunction, *SE, &AccessILS); + const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads(); for (LoadInst *LInst : AccessILS) if (!ScopRIL.count(LInst)) IsAffine = false; @@ -4537,45 +4517,41 @@ void ScopInfo::buildAccessSingleDim( {AccessFunction}, {}, Val); } -void ScopInfo::buildMemoryAccess( - MemAccInst Inst, Loop *L, Region *R, - const ScopDetection::BoxedLoopsSetTy *BoxedLoops, - const InvariantLoadsSetTy &ScopRIL, const MapInsnToMemAcc &InsnToMemAcc) { +void ScopInfo::buildMemoryAccess(MemAccInst Inst, Loop *L, Region *R) { - if (buildAccessMemIntrinsic(Inst, L, R, BoxedLoops, ScopRIL)) + if (buildAccessMemIntrinsic(Inst, L, R)) return; - if (buildAccessCallInst(Inst, L, R, BoxedLoops, ScopRIL)) + if (buildAccessCallInst(Inst, L, R)) return; - if (buildAccessMultiDimFixed(Inst, L, R, BoxedLoops, ScopRIL)) + if (buildAccessMultiDimFixed(Inst, L, R)) return; - if (buildAccessMultiDimParam(Inst, L, R, BoxedLoops, ScopRIL, InsnToMemAcc)) + if (buildAccessMultiDimParam(Inst, L, R)) return; - buildAccessSingleDim(Inst, L, R, BoxedLoops, ScopRIL); + buildAccessSingleDim(Inst, L, R); } -void ScopInfo::buildAccessFunctions(Region &R, Region &SR, - const MapInsnToMemAcc &InsnToMemAcc) { +void ScopInfo::buildAccessFunctions(Region &R, Region &SR) { - if (SD->isNonAffineSubRegion(&SR, &R)) { + if (scop->isNonAffineSubRegion(&SR)) { for (BasicBlock *BB : SR.blocks()) - buildAccessFunctions(R, *BB, InsnToMemAcc, &SR); + buildAccessFunctions(R, *BB, &SR); return; } for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I) if (I->isSubRegion()) - buildAccessFunctions(R, *I->getNodeAs<Region>(), InsnToMemAcc); + buildAccessFunctions(R, *I->getNodeAs<Region>()); else - buildAccessFunctions(R, *I->getNodeAs<BasicBlock>(), InsnToMemAcc); + buildAccessFunctions(R, *I->getNodeAs<BasicBlock>()); } void ScopInfo::buildStmts(Region &R, Region &SR) { - if (SD->isNonAffineSubRegion(&SR, &R)) { + if (scop->isNonAffineSubRegion(&SR)) { scop->addScopStmt(nullptr, &SR); return; } @@ -4588,7 +4564,6 @@ void ScopInfo::buildStmts(Region &R, Region &SR) { } void ScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB, - const MapInsnToMemAcc &InsnToMemAcc, Region *NonAffineSubRegion, bool IsExitBlock) { // We do not build access functions for error blocks, as they may contain @@ -4598,12 +4573,6 @@ void ScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB, Loop *L = LI->getLoopFor(&BB); - // The set of loops contained in non-affine subregions that are part of R. - const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD->getBoxedLoops(&R); - - // The set of loads that are required to be invariant. - auto &ScopRIL = *SD->getRequiredInvariantLoads(&R); - for (Instruction &Inst : BB) { PHINode *PHI = dyn_cast<PHINode>(&Inst); if (PHI) @@ -4613,12 +4582,8 @@ void ScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB, if (!PHI && IsExitBlock) break; - // TODO: At this point we only know that elements of ScopRIL have to be - // invariant and will be hoisted for the SCoP to be processed. Though, - // there might be other invariant accesses that will be hoisted and - // that would allow to make a non-affine access affine. if (auto MemInst = MemAccInst::dyn_cast(Inst)) - buildMemoryAccess(MemInst, L, &R, BoxedLoops, ScopRIL, InsnToMemAcc); + buildMemoryAccess(MemInst, L, &R); if (isIgnoredIntrinsic(&Inst)) continue; @@ -4727,8 +4692,8 @@ void ScopInfo::ensureValueRead(Value *V, BasicBlock *UserBB) { // Do not build scalar dependences for required invariant loads as we will // hoist them later on anyway or drop the SCoP if we cannot. - auto *ScopRIL = SD->getRequiredInvariantLoads(&ScopRegion); - if (ScopRIL->count(dyn_cast<LoadInst>(V))) + auto &ScopRIL = scop->getRequiredInvariantLoads(); + if (ScopRIL.count(dyn_cast<LoadInst>(V))) return; // Determine the ScopStmt containing the value's definition and use. There is @@ -4810,10 +4775,10 @@ void ScopInfo::addPHIReadAccess(PHINode *PHI) { } void ScopInfo::buildScop(Region &R, AssumptionCache &AC) { - scop.reset(new Scop(R, *SE, *LI)); + scop.reset(new Scop(R, *SE, *LI, *SD->getDetectionContext(&R))); buildStmts(R, R); - buildAccessFunctions(R, R, *SD->getInsnToMemAccMap(&R)); + buildAccessFunctions(R, R); // In case the region does not have an exiting block we will later (during // code generation) split the exit block. This will move potential PHI nodes @@ -4823,7 +4788,7 @@ void ScopInfo::buildScop(Region &R, AssumptionCache &AC) { // accesses. Note that we do not model anything in the exit block if we have // an exiting block in the region, as there will not be any splitting later. if (!R.getExitingBlock()) - buildAccessFunctions(R, *R.getExit(), *SD->getInsnToMemAccMap(&R), nullptr, + buildAccessFunctions(R, *R.getExit(), nullptr, /* IsExitBlock */ true); // Create memory accesses for global reads since all arrays are now known. @@ -4833,7 +4798,7 @@ void ScopInfo::buildScop(Region &R, AssumptionCache &AC) { addArrayAccess(MemAccInst(GlobalRead), MemoryAccess::READ, BP, BP->getType(), false, {AF}, {}, GlobalRead); - scop->init(*AA, AC, *SD, *DT, *LI); + scop->init(*AA, AC, *DT, *LI); } void ScopInfo::print(raw_ostream &OS, const Module *) const { |