Index: polly/trunk/include/polly/ScopBuilder.h =================================================================== --- polly/trunk/include/polly/ScopBuilder.h +++ polly/trunk/include/polly/ScopBuilder.h @@ -584,6 +584,62 @@ /// have been hoisted as loop invariant. void canonicalizeDynamicBasePtrs(); + /// Construct the schedule of this SCoP. + void buildSchedule(); + + /// A loop stack element to keep track of per-loop information during + /// schedule construction. + using LoopStackElementTy = struct LoopStackElement { + // The loop for which we keep information. + Loop *L; + + // The (possibly incomplete) schedule for this loop. + isl::schedule Schedule; + + // The number of basic blocks in the current loop, for which a schedule has + // already been constructed. + unsigned NumBlocksProcessed; + + LoopStackElement(Loop *L, isl::schedule S, unsigned NumBlocksProcessed) + : L(L), Schedule(S), NumBlocksProcessed(NumBlocksProcessed) {} + }; + + /// The loop stack used for schedule construction. + /// + /// The loop stack keeps track of schedule information for a set of nested + /// loops as well as an (optional) 'nullptr' loop that models the outermost + /// schedule dimension. The loops in a loop stack always have a parent-child + /// relation where the loop at position n is the parent of the loop at + /// position n + 1. + using LoopStackTy = SmallVector; + + /// Construct schedule information for a given Region and add the + /// derived information to @p LoopStack. + /// + /// Given a Region we derive schedule information for all RegionNodes + /// contained in this region ensuring that the assigned execution times + /// correctly model the existing control flow relations. + /// + /// @param R The region which to process. + /// @param LoopStack A stack of loops that are currently under + /// construction. + void buildSchedule(Region *R, LoopStackTy &LoopStack); + + /// Build Schedule for the region node @p RN and add the derived + /// information to @p LoopStack. + /// + /// In case @p RN is a BasicBlock or a non-affine Region, we construct the + /// schedule for this @p RN and also finalize loop schedules in case the + /// current @p RN completes the loop. + /// + /// In case @p RN is a not-non-affine Region, we delegate the construction to + /// buildSchedule(Region *R, ...). + /// + /// @param RN The RegionNode region traversed. + /// @param LoopStack A stack of loops that are currently under + /// construction. + void buildSchedule(RegionNode *RN, LoopStackTy &LoopStack); + public: explicit ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA, const DataLayout &DL, DominatorTree &DT, LoopInfo &LI, Index: polly/trunk/include/polly/ScopInfo.h =================================================================== --- polly/trunk/include/polly/ScopInfo.h +++ polly/trunk/include/polly/ScopInfo.h @@ -2109,66 +2109,6 @@ /// have a corresponding domain in the domain map (or it is empty). void removeStmtNotInDomainMap(); - /// Construct the schedule of this SCoP. - /// - /// @param LI The LoopInfo for the current function. - void buildSchedule(LoopInfo &LI); - - /// A loop stack element to keep track of per-loop information during - /// schedule construction. - using LoopStackElementTy = struct LoopStackElement { - // The loop for which we keep information. - Loop *L; - - // The (possibly incomplete) schedule for this loop. - isl::schedule Schedule; - - // The number of basic blocks in the current loop, for which a schedule has - // already been constructed. - unsigned NumBlocksProcessed; - - LoopStackElement(Loop *L, isl::schedule S, unsigned NumBlocksProcessed) - : L(L), Schedule(S), NumBlocksProcessed(NumBlocksProcessed) {} - }; - - /// The loop stack used for schedule construction. - /// - /// The loop stack keeps track of schedule information for a set of nested - /// loops as well as an (optional) 'nullptr' loop that models the outermost - /// schedule dimension. The loops in a loop stack always have a parent-child - /// relation where the loop at position n is the parent of the loop at - /// position n + 1. - using LoopStackTy = SmallVector; - - /// Construct schedule information for a given Region and add the - /// derived information to @p LoopStack. - /// - /// Given a Region we derive schedule information for all RegionNodes - /// contained in this region ensuring that the assigned execution times - /// correctly model the existing control flow relations. - /// - /// @param R The region which to process. - /// @param LoopStack A stack of loops that are currently under - /// construction. - /// @param LI The LoopInfo for the current function. - void buildSchedule(Region *R, LoopStackTy &LoopStack, LoopInfo &LI); - - /// Build Schedule for the region node @p RN and add the derived - /// information to @p LoopStack. - /// - /// In case @p RN is a BasicBlock or a non-affine Region, we construct the - /// schedule for this @p RN and also finalize loop schedules in case the - /// current @p RN completes the loop. - /// - /// In case @p RN is a not-non-affine Region, we delegate the construction to - /// buildSchedule(Region *R, ...). - /// - /// @param RN The RegionNode region traversed. - /// @param LoopStack A stack of loops that are currently under - /// construction. - /// @param LI The LoopInfo for the current function. - void buildSchedule(RegionNode *RN, LoopStackTy &LoopStack, LoopInfo &LI); - /// Collect all memory access relations of a given type. /// /// @param Predicate A predicate function that returns true if an access is Index: polly/trunk/include/polly/Support/ScopHelper.h =================================================================== --- polly/trunk/include/polly/Support/ScopHelper.h +++ polly/trunk/include/polly/Support/ScopHelper.h @@ -27,6 +27,7 @@ class Pass; class DominatorTree; class RegionInfo; +class RegionNode; } // namespace llvm namespace polly { @@ -379,6 +380,27 @@ /// @return The condition of @p TI and nullptr if none could be extracted. llvm::Value *getConditionFromTerminator(llvm::Instruction *TI); +/// Get the smallest loop that contains @p S but is not in @p S. +llvm::Loop *getLoopSurroundingScop(Scop &S, llvm::LoopInfo &LI); + +/// Get the number of blocks in @p L. +/// +/// The number of blocks in a loop are the number of basic blocks actually +/// belonging to the loop, as well as all single basic blocks that the loop +/// exits to and which terminate in an unreachable instruction. We do not +/// allow such basic blocks in the exit of a scop, hence they belong to the +/// scop and represent run-time conditions which we want to model and +/// subsequently speculate away. +/// +/// @see getRegionNodeLoop for additional details. +unsigned getNumBlocksInLoop(llvm::Loop *L); + +/// Get the number of blocks in @p RN. +unsigned getNumBlocksInRegionNode(llvm::RegionNode *RN); + +/// Return the smallest loop surrounding @p RN. +llvm::Loop *getRegionNodeLoop(llvm::RegionNode *RN, llvm::LoopInfo &LI); + /// Check if @p LInst can be hoisted in @p R. /// /// @param LInst The load to check. Index: polly/trunk/lib/Analysis/ScopBuilder.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopBuilder.cpp +++ polly/trunk/lib/Analysis/ScopBuilder.cpp @@ -24,6 +24,7 @@ #include "polly/Support/VirtualInstruction.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/EquivalenceClasses.h" +#include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/Loads.h" @@ -222,6 +223,179 @@ ensureValueRead(Op.get(), UserStmt); } +// Create a sequence of two schedules. Either argument may be null and is +// interpreted as the empty schedule. Can also return null if both schedules are +// empty. +static isl::schedule combineInSequence(isl::schedule Prev, isl::schedule Succ) { + if (!Prev) + return Succ; + if (!Succ) + return Prev; + + return Prev.sequence(Succ); +} + +// Create an isl_multi_union_aff that defines an identity mapping from the +// elements of USet to their N-th dimension. +// +// # Example: +// +// Domain: { A[i,j]; B[i,j,k] } +// N: 1 +// +// Resulting Mapping: { {A[i,j] -> [(j)]; B[i,j,k] -> [(j)] } +// +// @param USet A union set describing the elements for which to generate a +// mapping. +// @param N The dimension to map to. +// @returns A mapping from USet to its N-th dimension. +static isl::multi_union_pw_aff mapToDimension(isl::union_set USet, int N) { + assert(N >= 0); + assert(USet); + assert(!USet.is_empty()); + + auto Result = isl::union_pw_multi_aff::empty(USet.get_space()); + + for (isl::set S : USet.get_set_list()) { + int Dim = S.dim(isl::dim::set); + auto PMA = isl::pw_multi_aff::project_out_map(S.get_space(), isl::dim::set, + N, Dim - N); + if (N > 1) + PMA = PMA.drop_dims(isl::dim::out, 0, N - 1); + + Result = Result.add_pw_multi_aff(PMA); + } + + return isl::multi_union_pw_aff(isl::union_pw_multi_aff(Result)); +} + +void ScopBuilder::buildSchedule() { + Loop *L = getLoopSurroundingScop(*scop, LI); + LoopStackTy LoopStack({LoopStackElementTy(L, nullptr, 0)}); + buildSchedule(scop->getRegion().getNode(), LoopStack); + assert(LoopStack.size() == 1 && LoopStack.back().L == L); + scop->setScheduleTree(LoopStack[0].Schedule); +} + +/// To generate a schedule for the elements in a Region we traverse the Region +/// in reverse-post-order and add the contained RegionNodes in traversal order +/// to the schedule of the loop that is currently at the top of the LoopStack. +/// For loop-free codes, this results in a correct sequential ordering. +/// +/// Example: +/// bb1(0) +/// / \. +/// bb2(1) bb3(2) +/// \ / \. +/// bb4(3) bb5(4) +/// \ / +/// bb6(5) +/// +/// Including loops requires additional processing. Whenever a loop header is +/// encountered, the corresponding loop is added to the @p LoopStack. Starting +/// from an empty schedule, we first process all RegionNodes that are within +/// this loop and complete the sequential schedule at this loop-level before +/// processing about any other nodes. To implement this +/// loop-nodes-first-processing, the reverse post-order traversal is +/// insufficient. Hence, we additionally check if the traversal yields +/// 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 ScopBuilder::buildSchedule(Region *R, LoopStackTy &LoopStack) { + Loop *OuterScopLoop = getLoopSurroundingScop(*scop, LI); + + ReversePostOrderTraversal RTraversal(R); + std::deque WorkList(RTraversal.begin(), RTraversal.end()); + std::deque DelayList; + bool LastRNWaiting = false; + + // Iterate over the region @p R in reverse post-order but queue + // sub-regions/blocks iff they are not part of the last encountered but not + // completely traversed loop. The variable LastRNWaiting is a flag to indicate + // that we queued the last sub-region/block from the reverse post-order + // iterator. If it is set we have to explore the next sub-region/block from + // the iterator (if any) to guarantee progress. If it is not set we first try + // the next queued sub-region/blocks. + while (!WorkList.empty() || !DelayList.empty()) { + RegionNode *RN; + + if ((LastRNWaiting && !WorkList.empty()) || DelayList.empty()) { + RN = WorkList.front(); + WorkList.pop_front(); + LastRNWaiting = false; + } else { + RN = DelayList.front(); + DelayList.pop_front(); + } + + Loop *L = getRegionNodeLoop(RN, LI); + if (!scop->contains(L)) + L = OuterScopLoop; + + Loop *LastLoop = LoopStack.back().L; + if (LastLoop != L) { + if (LastLoop && !LastLoop->contains(L)) { + LastRNWaiting = true; + DelayList.push_back(RN); + continue; + } + LoopStack.push_back({L, nullptr, 0}); + } + buildSchedule(RN, LoopStack); + } +} + +void ScopBuilder::buildSchedule(RegionNode *RN, LoopStackTy &LoopStack) { + if (RN->isSubRegion()) { + auto *LocalRegion = RN->getNodeAs(); + if (!scop->isNonAffineSubRegion(LocalRegion)) { + buildSchedule(LocalRegion, LoopStack); + return; + } + } + + assert(LoopStack.rbegin() != LoopStack.rend()); + auto LoopData = LoopStack.rbegin(); + LoopData->NumBlocksProcessed += getNumBlocksInRegionNode(RN); + + for (auto *Stmt : scop->getStmtListFor(RN)) { + isl::union_set UDomain{Stmt->getDomain()}; + auto StmtSchedule = isl::schedule::from_domain(UDomain); + LoopData->Schedule = combineInSequence(LoopData->Schedule, StmtSchedule); + } + + // Check if we just processed the last node in this loop. If we did, finalize + // the loop by: + // + // - adding new schedule dimensions + // - folding the resulting schedule into the parent loop schedule + // - dropping the loop schedule from the LoopStack. + // + // Then continue to check surrounding loops, which might also have been + // completed by this node. + size_t Dimension = LoopStack.size(); + while (LoopData->L && + LoopData->NumBlocksProcessed == getNumBlocksInLoop(LoopData->L)) { + isl::schedule Schedule = LoopData->Schedule; + auto NumBlocksProcessed = LoopData->NumBlocksProcessed; + + assert(std::next(LoopData) != LoopStack.rend()); + ++LoopData; + --Dimension; + + if (Schedule) { + isl::union_set Domain = Schedule.get_domain(); + isl::multi_union_pw_aff MUPA = mapToDimension(Domain, Dimension); + Schedule = Schedule.insert_partial_schedule(MUPA); + LoopData->Schedule = combineInSequence(LoopData->Schedule, Schedule); + } + + LoopData->NumBlocksProcessed += NumBlocksProcessed; + } + // Now pop all loops processed up there from the LoopStack + LoopStack.erase(LoopStack.begin() + Dimension, LoopStack.end()); +} + void ScopBuilder::buildEscapingDependences(Instruction *Inst) { // Check for uses of this instruction outside the scop. Because we do not // iterate over such instructions and therefore did not "ensure" the existence @@ -2554,7 +2728,7 @@ return; } - scop->buildSchedule(LI); + buildSchedule(); finalizeAccesses(); Index: polly/trunk/lib/Analysis/ScopInfo.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopInfo.cpp +++ polly/trunk/lib/Analysis/ScopInfo.cpp @@ -163,18 +163,6 @@ //===----------------------------------------------------------------------===// -// Create a sequence of two schedules. Either argument may be null and is -// interpreted as the empty schedule. Can also return null if both schedules are -// empty. -static isl::schedule combineInSequence(isl::schedule Prev, isl::schedule Succ) { - if (!Prev) - return Succ; - if (!Succ) - return Prev; - - return Prev.sequence(Succ); -} - static isl::set addRangeBoundsToSet(isl::set S, const ConstantRange &Range, int dim, isl::dim type) { isl::val V; @@ -2125,72 +2113,6 @@ return TI->getSuccessor(idx); } -/// Return the smallest loop surrounding @p RN. -static inline Loop *getRegionNodeLoop(RegionNode *RN, LoopInfo &LI) { - if (!RN->isSubRegion()) { - BasicBlock *BB = RN->getNodeAs(); - Loop *L = LI.getLoopFor(BB); - - // Unreachable statements are not considered to belong to a LLVM loop, as - // they are not part of an actual loop in the control flow graph. - // Nevertheless, we handle certain unreachable statements that are common - // when modeling run-time bounds checks as being part of the loop to be - // able to model them and to later eliminate the run-time bounds checks. - // - // Specifically, for basic blocks that terminate in an unreachable and - // where the immediate predecessor is part of a loop, we assume these - // basic blocks belong to the loop the predecessor belongs to. This - // allows us to model the following code. - // - // for (i = 0; i < N; i++) { - // if (i > 1024) - // abort(); <- this abort might be translated to an - // unreachable - // - // A[i] = ... - // } - if (!L && isa(BB->getTerminator()) && BB->getPrevNode()) - L = LI.getLoopFor(BB->getPrevNode()); - return L; - } - - Region *NonAffineSubRegion = RN->getNodeAs(); - Loop *L = LI.getLoopFor(NonAffineSubRegion->getEntry()); - while (L && NonAffineSubRegion->contains(L)) - L = L->getParentLoop(); - return L; -} - -/// Get the number of blocks in @p L. -/// -/// The number of blocks in a loop are the number of basic blocks actually -/// belonging to the loop, as well as all single basic blocks that the loop -/// exits to and which terminate in an unreachable instruction. We do not -/// allow such basic blocks in the exit of a scop, hence they belong to the -/// scop and represent run-time conditions which we want to model and -/// subsequently speculate away. -/// -/// @see getRegionNodeLoop for additional details. -unsigned getNumBlocksInLoop(Loop *L) { - unsigned NumBlocks = L->getNumBlocks(); - SmallVector ExitBlocks; - L->getExitBlocks(ExitBlocks); - - for (auto ExitBlock : ExitBlocks) { - if (isa(ExitBlock->getTerminator())) - NumBlocks++; - } - return NumBlocks; -} - -static inline unsigned getNumBlocksInRegionNode(RegionNode *RN) { - if (!RN->isSubRegion()) - return 1; - - Region *R = RN->getNodeAs(); - return std::distance(R->block_begin(), R->block_end()); -} - static bool containsErrorBlock(RegionNode *RN, const Region &R, LoopInfo &LI, const DominatorTree &DT) { if (!RN->isSubRegion()) @@ -2761,26 +2683,6 @@ return true; } -/// Get the smallest loop that contains @p S but is not in @p S. -static Loop *getLoopSurroundingScop(Scop &S, LoopInfo &LI) { - // Start with the smallest loop containing the entry and expand that - // loop until it contains all blocks in the region. If there is a loop - // containing all blocks in the region check if it is itself contained - // and if so take the parent loop as it will be the smallest containing - // the region but not contained by it. - Loop *L = LI.getLoopFor(S.getEntry()); - while (L) { - bool AllContained = true; - for (auto *BB : S.blocks()) - AllContained &= L->contains(BB); - if (AllContained) - break; - L = L->getParentLoop(); - } - - return L ? (S.contains(L) ? L->getParentLoop() : L) : nullptr; -} - int Scop::NextScopID = 0; std::string Scop::CurrentFunc; @@ -3463,40 +3365,6 @@ ScalarEvolution *Scop::getSE() const { return SE; } -// Create an isl_multi_union_aff that defines an identity mapping from the -// elements of USet to their N-th dimension. -// -// # Example: -// -// Domain: { A[i,j]; B[i,j,k] } -// N: 1 -// -// Resulting Mapping: { {A[i,j] -> [(j)]; B[i,j,k] -> [(j)] } -// -// @param USet A union set describing the elements for which to generate a -// mapping. -// @param N The dimension to map to. -// @returns A mapping from USet to its N-th dimension. -static isl::multi_union_pw_aff mapToDimension(isl::union_set USet, int N) { - assert(N >= 0); - assert(USet); - assert(!USet.is_empty()); - - auto Result = isl::union_pw_multi_aff::empty(USet.get_space()); - - for (isl::set S : USet.get_set_list()) { - int Dim = S.dim(isl::dim::set); - auto PMA = isl::pw_multi_aff::project_out_map(S.get_space(), isl::dim::set, - N, Dim - N); - if (N > 1) - PMA = PMA.drop_dims(isl::dim::out, 0, N - 1); - - Result = Result.add_pw_multi_aff(PMA); - } - - return isl::multi_union_pw_aff(isl::union_pw_multi_aff(Result)); -} - void Scop::addScopStmt(BasicBlock *BB, StringRef Name, Loop *SurroundingLoop, std::vector Instructions) { assert(BB && "Unexpected nullptr!"); @@ -3549,133 +3417,6 @@ return &(Stmts.back()); } -void Scop::buildSchedule(LoopInfo &LI) { - Loop *L = getLoopSurroundingScop(*this, LI); - LoopStackTy LoopStack({LoopStackElementTy(L, nullptr, 0)}); - buildSchedule(getRegion().getNode(), LoopStack, LI); - assert(LoopStack.size() == 1 && LoopStack.back().L == L); - Schedule = LoopStack[0].Schedule; -} - -/// To generate a schedule for the elements in a Region we traverse the Region -/// in reverse-post-order and add the contained RegionNodes in traversal order -/// to the schedule of the loop that is currently at the top of the LoopStack. -/// For loop-free codes, this results in a correct sequential ordering. -/// -/// Example: -/// bb1(0) -/// / \. -/// bb2(1) bb3(2) -/// \ / \. -/// bb4(3) bb5(4) -/// \ / -/// bb6(5) -/// -/// Including loops requires additional processing. Whenever a loop header is -/// encountered, the corresponding loop is added to the @p LoopStack. Starting -/// from an empty schedule, we first process all RegionNodes that are within -/// this loop and complete the sequential schedule at this loop-level before -/// processing about any other nodes. To implement this -/// loop-nodes-first-processing, the reverse post-order traversal is -/// insufficient. Hence, we additionally check if the traversal yields -/// 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, LoopInfo &LI) { - Loop *OuterScopLoop = getLoopSurroundingScop(*this, LI); - - ReversePostOrderTraversal RTraversal(R); - std::deque WorkList(RTraversal.begin(), RTraversal.end()); - std::deque DelayList; - bool LastRNWaiting = false; - - // Iterate over the region @p R in reverse post-order but queue - // sub-regions/blocks iff they are not part of the last encountered but not - // completely traversed loop. The variable LastRNWaiting is a flag to indicate - // that we queued the last sub-region/block from the reverse post-order - // iterator. If it is set we have to explore the next sub-region/block from - // the iterator (if any) to guarantee progress. If it is not set we first try - // the next queued sub-region/blocks. - while (!WorkList.empty() || !DelayList.empty()) { - RegionNode *RN; - - if ((LastRNWaiting && !WorkList.empty()) || DelayList.empty()) { - RN = WorkList.front(); - WorkList.pop_front(); - LastRNWaiting = false; - } else { - RN = DelayList.front(); - DelayList.pop_front(); - } - - Loop *L = getRegionNodeLoop(RN, LI); - if (!contains(L)) - L = OuterScopLoop; - - Loop *LastLoop = LoopStack.back().L; - if (LastLoop != L) { - if (LastLoop && !LastLoop->contains(L)) { - LastRNWaiting = true; - DelayList.push_back(RN); - continue; - } - LoopStack.push_back({L, nullptr, 0}); - } - buildSchedule(RN, LoopStack, LI); - } -} - -void Scop::buildSchedule(RegionNode *RN, LoopStackTy &LoopStack, LoopInfo &LI) { - if (RN->isSubRegion()) { - auto *LocalRegion = RN->getNodeAs(); - if (!isNonAffineSubRegion(LocalRegion)) { - buildSchedule(LocalRegion, LoopStack, LI); - return; - } - } - - assert(LoopStack.rbegin() != LoopStack.rend()); - auto LoopData = LoopStack.rbegin(); - LoopData->NumBlocksProcessed += getNumBlocksInRegionNode(RN); - - for (auto *Stmt : getStmtListFor(RN)) { - isl::union_set UDomain{Stmt->getDomain()}; - auto StmtSchedule = isl::schedule::from_domain(UDomain); - LoopData->Schedule = combineInSequence(LoopData->Schedule, StmtSchedule); - } - - // Check if we just processed the last node in this loop. If we did, finalize - // the loop by: - // - // - adding new schedule dimensions - // - folding the resulting schedule into the parent loop schedule - // - dropping the loop schedule from the LoopStack. - // - // Then continue to check surrounding loops, which might also have been - // completed by this node. - size_t Dimension = LoopStack.size(); - while (LoopData->L && - LoopData->NumBlocksProcessed == getNumBlocksInLoop(LoopData->L)) { - isl::schedule Schedule = LoopData->Schedule; - auto NumBlocksProcessed = LoopData->NumBlocksProcessed; - - assert(std::next(LoopData) != LoopStack.rend()); - ++LoopData; - --Dimension; - - if (Schedule) { - isl::union_set Domain = Schedule.get_domain(); - isl::multi_union_pw_aff MUPA = mapToDimension(Domain, Dimension); - Schedule = Schedule.insert_partial_schedule(MUPA); - LoopData->Schedule = combineInSequence(LoopData->Schedule, Schedule); - } - - LoopData->NumBlocksProcessed += NumBlocksProcessed; - } - // Now pop all loops processed up there from the LoopStack - LoopStack.erase(LoopStack.begin() + Dimension, LoopStack.end()); -} - ArrayRef Scop::getStmtListFor(BasicBlock *BB) const { auto StmtMapIt = StmtMap.find(BB); if (StmtMapIt == StmtMap.end()) Index: polly/trunk/lib/Support/ScopHelper.cpp =================================================================== --- polly/trunk/lib/Support/ScopHelper.cpp +++ polly/trunk/lib/Support/ScopHelper.cpp @@ -461,6 +461,80 @@ return nullptr; } +Loop *polly::getLoopSurroundingScop(Scop &S, LoopInfo &LI) { + // Start with the smallest loop containing the entry and expand that + // loop until it contains all blocks in the region. If there is a loop + // containing all blocks in the region check if it is itself contained + // and if so take the parent loop as it will be the smallest containing + // the region but not contained by it. + Loop *L = LI.getLoopFor(S.getEntry()); + while (L) { + bool AllContained = true; + for (auto *BB : S.blocks()) + AllContained &= L->contains(BB); + if (AllContained) + break; + L = L->getParentLoop(); + } + + return L ? (S.contains(L) ? L->getParentLoop() : L) : nullptr; +} + +unsigned polly::getNumBlocksInLoop(Loop *L) { + unsigned NumBlocks = L->getNumBlocks(); + SmallVector ExitBlocks; + L->getExitBlocks(ExitBlocks); + + for (auto ExitBlock : ExitBlocks) { + if (isa(ExitBlock->getTerminator())) + NumBlocks++; + } + return NumBlocks; +} + +unsigned polly::getNumBlocksInRegionNode(RegionNode *RN) { + if (!RN->isSubRegion()) + return 1; + + Region *R = RN->getNodeAs(); + return std::distance(R->block_begin(), R->block_end()); +} + +Loop *polly::getRegionNodeLoop(RegionNode *RN, LoopInfo &LI) { + if (!RN->isSubRegion()) { + BasicBlock *BB = RN->getNodeAs(); + Loop *L = LI.getLoopFor(BB); + + // Unreachable statements are not considered to belong to a LLVM loop, as + // they are not part of an actual loop in the control flow graph. + // Nevertheless, we handle certain unreachable statements that are common + // when modeling run-time bounds checks as being part of the loop to be + // able to model them and to later eliminate the run-time bounds checks. + // + // Specifically, for basic blocks that terminate in an unreachable and + // where the immediate predecessor is part of a loop, we assume these + // basic blocks belong to the loop the predecessor belongs to. This + // allows us to model the following code. + // + // for (i = 0; i < N; i++) { + // if (i > 1024) + // abort(); <- this abort might be translated to an + // unreachable + // + // A[i] = ... + // } + if (!L && isa(BB->getTerminator()) && BB->getPrevNode()) + L = LI.getLoopFor(BB->getPrevNode()); + return L; + } + + Region *NonAffineSubRegion = RN->getNodeAs(); + Loop *L = LI.getLoopFor(NonAffineSubRegion->getEntry()); + while (L && NonAffineSubRegion->contains(L)) + L = L->getParentLoop(); + return L; +} + static bool hasVariantIndex(GetElementPtrInst *Gep, Loop *L, Region &R, ScalarEvolution &SE) { for (const Use &Val : llvm::drop_begin(Gep->operands(), 1)) {