Index: include/llvm/Analysis/ParallelRegionInfo.h =================================================================== --- include/llvm/Analysis/ParallelRegionInfo.h +++ include/llvm/Analysis/ParallelRegionInfo.h @@ -45,9 +45,20 @@ /// @TODO The update interface to add/remove parallel regions is missing. /// class ParallelRegionInfo { +public: + /// The container type used to store top level parallel regions. + using ParallelRegionVectorTy = SmallVector; + + /// Iterator types for top level parallel regions. + /// + ///{ + using iterator = ParallelRegionVectorTy::iterator; + using const_iterator = ParallelRegionVectorTy::const_iterator; + ///} +private: /// The parallel regions that are not nested in other parallel regions. - SmallVector TopLevelParallelRegions; + ParallelRegionVectorTy TopLevelParallelRegions; public: ParallelRegionInfo() {} @@ -71,14 +82,57 @@ /// Return the top-level parallel regions in this function. /// ///{ - SmallVectorImpl &getTopLevelParallelRegions() { + ParallelRegionVectorTy &getTopLevelParallelRegions() { return TopLevelParallelRegions; } - const SmallVectorImpl &getTopLevelParallelRegions() const { + const ParallelRegionVectorTy &getTopLevelParallelRegions() const { return TopLevelParallelRegions; } ///} + /// Return true if there is no parallel region in this function. + bool empty() const { return TopLevelParallelRegions.empty(); } + + /// Remove all cached parallel regions of this function. + void clear() { TopLevelParallelRegions.clear(); } + + /// Return the number of top level parallel regions in this function. + ParallelRegionVectorTy::size_type size() const { + return TopLevelParallelRegions.size(); + } + + /// Iterators for parallel regions. + /// + ///{ + iterator begin() { return TopLevelParallelRegions.begin(); } + iterator end() { return TopLevelParallelRegions.end(); } + const_iterator begin() const { return TopLevelParallelRegions.begin(); } + const_iterator end() const { return TopLevelParallelRegions.end(); } + ///} + + /// Return the parallel region that makes @p L a parallel loop, if any. + /// + /// A parallel loop is a loop that does fork (parts of) its body to a new + /// task which are joined only after the loop. It is also ensured that + /// everything that is not forked but part of the loop does not cause + /// side-effects. These instructions usually compute the exit condition + /// and the new values for the induction variable(s). + /// + /// Note: We allow multiple induction variables and complex exit conditions + /// here. However, for some parallel runtimes these have to be simplified, + /// e.g. expressed with regards to one canonical induction variable. + /// TODO: Provide an interface to perform the simplification. + /// + /// Note: We allow arbitrary code after the loop but before a join + /// instruction. + ParallelRegion *getParallelLoopRegion(const Loop &L, + const DominatorTree &DT) const; + + /// Return true if @p L is a parallel loop. + /// + /// See ParallelRegionInfo::getParallelLoopRegion for more information. + bool isParallelLoop(const Loop &L, const DominatorTree &DT) const; + /// Check for containment in any parallel region. ///{ bool containedInAny(const BasicBlock *BB, const DominatorTree &DT) const; @@ -308,6 +362,11 @@ } ///} + /// Return true if this is a parallel loop region for @p L. + /// + /// See ParallelRegionInfo::getParallelLoopRegion for more information. + bool isParallelLoopRegion(const Loop &L, const DominatorTree &DT) const; + /// @see ParallelTask::contains(const BasicBlock *BB, DominatorTree &DT) bool contains(const BasicBlock *BB, const DominatorTree &DT) const; Index: lib/Analysis/ParallelRegionInfo.cpp =================================================================== --- lib/Analysis/ParallelRegionInfo.cpp +++ lib/Analysis/ParallelRegionInfo.cpp @@ -182,6 +182,72 @@ ParallelSubRegions[&ParallelSubRegion.getFork()] = &ParallelSubRegion; } +bool ParallelRegion::isParallelLoopRegion(const Loop &L, + const DominatorTree &DT) const { + // Bail if the fork is not part of the loop. + if (!L.contains(getFork().getParent())) + return false; + + // Bail if a join is part of the loop. + const auto &JoinsVector = ContinuationTask.getHaltsOrJoints(); + if (std::any_of(JoinsVector.begin(), JoinsVector.end(), + [&L](TerminatorInst *TI) { return L.contains(TI); })) + return false; + + // Now check for possible side effects outside the forked task. First the + // header to the fork and then the part of the continuation which is inside + // the loop. + SmallVector Worklist; + BasicBlock *HeaderBB = L.getHeader(); + Worklist.push_back(HeaderBB); + + while (!Worklist.empty()) { + BasicBlock *BB = Worklist.pop_back_val(); + assert(L.contains(BB)); + + for (Instruction &I : *BB) + if (I.mayHaveSideEffects()) + return false; + + if (&getFork() == BB->getTerminator()) + continue; + + for (BasicBlock *SuccessorBB : successors(BB)) + if (L.contains(SuccessorBB)) + Worklist.push_back(SuccessorBB); + } + + BasicBlock &ContinuationEntryBB = ContinuationTask.getEntry(); + assert(L.contains(&ContinuationEntryBB) && + "Fork instructions should not be used to exit a loop!"); + + // We do not support nested loops in the continuation part. + if (std::any_of(L.begin(), L.end(), [&](Loop *SubLoop) { + return ContinuationTask.contains(SubLoop, DT); + })) + return false; + + // Traverse all blocks that are in the continuation and in the loop and check + // for side-effects. + assert(Worklist.empty()); + Worklist.push_back(&ContinuationEntryBB); + + while (!Worklist.empty()) { + BasicBlock *BB = Worklist.pop_back_val(); + assert(L.contains(BB)); + + for (Instruction &I : *BB) + if (I.mayHaveSideEffects()) + return false; + + for (BasicBlock *SuccessorBB : successors(BB)) + if (L.contains(SuccessorBB) && SuccessorBB != HeaderBB) + Worklist.push_back(SuccessorBB); + } + + return true; +} + bool ParallelRegion::contains(const BasicBlock *BB, const DominatorTree &DT) const { // All contained blocks are dominated by the fork block. @@ -430,6 +496,47 @@ return BB2PTMap; } +ParallelRegion *ParallelRegionInfo::getParallelLoopRegion(const Loop &L, + const DominatorTree &DT) const { + if (empty()) + return nullptr; + + SmallVector ParallelRegions; + ParallelRegions.append(begin(), end()); + + // The parallel region we are looking for. + ParallelRegion *ParallelLoopRegion = nullptr; + + while (!ParallelRegions.empty()) { + ParallelRegion *PR = ParallelRegions.pop_back_val(); + + for (const auto &It : PR->getSubRegions()) + ParallelRegions.push_back(It.getSecond()); + + if (!PR->isParallelLoopRegion(L, DT)) + continue; + + assert(!ParallelLoopRegion && + "Broken nesting resulted in multiple parallel loop regions"); + + ParallelLoopRegion = PR; + +#ifdef NDEBUG + // For debug builds we verify that at most one parallel loop region exists, + // otherwise we just assume the nesting was intact. + break; +#endif + } + + return ParallelLoopRegion; +} + +bool ParallelRegionInfo::isParallelLoop(const Loop &L, + const DominatorTree &DT) const { + // See ParallelRegionInfo::getParallelLoopRegion(...) for more information. + return getParallelLoopRegion(L, DT) != nullptr; +} + bool ParallelRegionInfo::containedInAny(const BasicBlock *BB, const DominatorTree &DT) const { return std::any_of( @@ -468,7 +575,7 @@ bool ParallelRegionInfo::isSafeToPromote(const AllocaInst &AI, const DominatorTree &DT) const { - if (TopLevelParallelRegions.empty()) + if (empty()) return true; // First check if we know that AI is contained in a parallel region.