diff options
| -rw-r--r-- | llvm/include/llvm/Analysis/LoopInfo.h | 2 | ||||
| -rw-r--r-- | llvm/include/llvm/Analysis/LoopInfoImpl.h | 65 | ||||
| -rw-r--r-- | llvm/lib/Analysis/LoopInfo.cpp | 9 | ||||
| -rw-r--r-- | llvm/lib/Transforms/Scalar/LoopDistribute.cpp | 2 |
4 files changed, 71 insertions, 7 deletions
diff --git a/llvm/include/llvm/Analysis/LoopInfo.h b/llvm/include/llvm/Analysis/LoopInfo.h index 651a749a6d6..85c06826dae 100644 --- a/llvm/include/llvm/Analysis/LoopInfo.h +++ b/llvm/include/llvm/Analysis/LoopInfo.h @@ -635,7 +635,7 @@ public: // Debugging void print(raw_ostream &OS) const; - void verify() const; + void verify(const DominatorTreeBase<BlockT> &DomTree) const; }; // Implementation in LoopInfoImpl.h diff --git a/llvm/include/llvm/Analysis/LoopInfoImpl.h b/llvm/include/llvm/Analysis/LoopInfoImpl.h index 72a09cdd055..6635860139b 100644 --- a/llvm/include/llvm/Analysis/LoopInfoImpl.h +++ b/llvm/include/llvm/Analysis/LoopInfoImpl.h @@ -17,6 +17,7 @@ #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/SetVector.h" #include "llvm/ADT/STLExtras.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/IR/Dominators.h" @@ -514,8 +515,26 @@ void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const { #endif } -template<class BlockT, class LoopT> -void LoopInfoBase<BlockT, LoopT>::verify() const { +template <typename T> +bool compareVectors(std::vector<T> &BB1, std::vector<T> &BB2) { + std::sort(BB1.begin(), BB1.end()); + std::sort(BB2.begin(), BB2.end()); + return BB1 == BB2; +} + +template <class BlockT, class LoopT> +static void +addInnerLoopsToHeadersMap(DenseMap<BlockT *, const LoopT *> &LoopHeaders, + const LoopInfoBase<BlockT, LoopT> &LI, + const LoopT &L) { + LoopHeaders[L.getHeader()] = &L; + for (LoopT *SL : L) + addInnerLoopsToHeadersMap(LoopHeaders, LI, *SL); +} + +template <class BlockT, class LoopT> +void LoopInfoBase<BlockT, LoopT>::verify( + const DominatorTreeBase<BlockT> &DomTree) const { DenseSet<const LoopT*> Loops; for (iterator I = begin(), E = end(); I != E; ++I) { assert(!(*I)->getParentLoop() && "Top-level loop has a parent!"); @@ -530,6 +549,48 @@ void LoopInfoBase<BlockT, LoopT>::verify() const { assert(Loops.count(L) && "orphaned loop"); assert(L->contains(BB) && "orphaned block"); } + + // Recompute LoopInfo to verify loops structure. + LoopInfoBase<BlockT, LoopT> OtherLI; + OtherLI.analyze(DomTree); + + DenseMap<BlockT *, const LoopT *> LoopHeaders1; + DenseMap<BlockT *, const LoopT *> LoopHeaders2; + + for (LoopT *L : *this) + addInnerLoopsToHeadersMap(LoopHeaders1, *this, *L); + for (LoopT *L : OtherLI) + addInnerLoopsToHeadersMap(LoopHeaders2, OtherLI, *L); + assert(LoopHeaders1.size() == LoopHeaders2.size() && + "LoopInfo is incorrect."); + + auto compareLoops = [&](const LoopT *L1, const LoopT *L2) { + BlockT *H1 = L1->getHeader(); + BlockT *H2 = L2->getHeader(); + if (H1 != H2) + return false; + std::vector<BlockT *> BB1 = L1->getBlocks(); + std::vector<BlockT *> BB2 = L2->getBlocks(); + if (!compareVectors(BB1, BB2)) + return false; + + std::vector<BlockT *> SubLoopHeaders1; + std::vector<BlockT *> SubLoopHeaders2; + for (LoopT *L : *L1) + SubLoopHeaders1.push_back(L->getHeader()); + for (LoopT *L : *L2) + SubLoopHeaders2.push_back(L->getHeader()); + + if (!compareVectors(SubLoopHeaders1, SubLoopHeaders2)) + return false; + return true; + }; + + for (auto &I : LoopHeaders1) { + BlockT *H = I.first; + bool LoopsMatch = compareLoops(LoopHeaders1[H], LoopHeaders2[H]); + assert(LoopsMatch && "LoopInfo is incorrect."); + } #endif } diff --git a/llvm/lib/Analysis/LoopInfo.cpp b/llvm/lib/Analysis/LoopInfo.cpp index 9d2e38e19da..a5f816dd5ad 100644 --- a/llvm/lib/Analysis/LoopInfo.cpp +++ b/llvm/lib/Analysis/LoopInfo.cpp @@ -703,8 +703,10 @@ void LoopInfoWrapperPass::verifyAnalysis() const { // -verify-loop-info option can enable this. In order to perform some // checking by default, LoopPass has been taught to call verifyLoop manually // during loop pass sequences. - if (VerifyLoopInfo) - LI.verify(); + if (VerifyLoopInfo) { + auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); + LI.verify(DT); + } } void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { @@ -719,7 +721,8 @@ void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const { PreservedAnalyses LoopVerifierPass::run(Function &F, FunctionAnalysisManager &AM) { LoopInfo &LI = AM.getResult<LoopAnalysis>(F); - LI.verify(); + auto &DT = AM.getResult<DominatorTreeAnalysis>(F); + LI.verify(DT); return PreservedAnalyses::all(); } diff --git a/llvm/lib/Transforms/Scalar/LoopDistribute.cpp b/llvm/lib/Transforms/Scalar/LoopDistribute.cpp index 74cfdbfa84e..ad973cf31de 100644 --- a/llvm/lib/Transforms/Scalar/LoopDistribute.cpp +++ b/llvm/lib/Transforms/Scalar/LoopDistribute.cpp @@ -742,7 +742,7 @@ public: DEBUG(Partitions.printBlocks()); if (LDistVerify) { - LI->verify(); + LI->verify(*DT); DT->verifyDomTree(); } |
