[LoopInfo] Add a routine for verification by recomputation.

[mzolotukhin]

Summary

Current implementation of LI verifier isn't ideal and fails to detect
some cases when LI is incorrect. For instance, it checks that all
recorded loops are in a correct form, but it has no way to check if
there are no more other (unrecorded in LI) loops in the function. This
patch adds a way to detect such bugs.

Examples of potential use:

• In PR28888 loop-unroll breaks LI, but we don't detect it (with this patch we will).
• IRCE breaks LI in IRCE/with-parent-loops.ll test. I'm xfail-ing this test for now (I'll file a separate PR for it).

[mzolotukhin]

I filed PR28944 for the IRCE issue.

[chandlerc]

lib/Analysis/LoopInfo.cpp

707–708

Rather than this, how about putting this into verify (and behind a command line flag if necessary) and computing a fresh DomTree rather than trusting whatever the analysis manager might have?

[mzolotukhin]

• Move new verifier to the existing verify() routine.
• Remove XFAIL.

[mzolotukhin]

Hi,

I moved the new logic to verify() routine, does it look good? I'm not convinced that we need to recalculate DT though: we have a separate verifier for it and in my view recalculating it here would be functionality duplication to some extent. IOW I think we should rely on DT being correct and use verifiers to make sure it holds true; if we don't trust corresponding verifiers, we should fix them. Does it make sense?

Thanks,
Michael

[mzolotukhin]

Ping!

[chandlerc]

Sorry for the delay. Feel free to commit, this is all just nit picky stuff that can be sorted out and even changed afterward if desired.

In D23437#523726, @mzolotukhin wrote:

I moved the new logic to verify() routine, does it look good? I'm not convinced that we need to recalculate DT though: we have a separate verifier for it and in my view recalculating it here would be functionality duplication to some extent. IOW I think we should rely on DT being correct and use verifiers to make sure it holds true; if we don't trust corresponding verifiers, we should fix them. Does it make sense?

It makes a certain amount of sense. I guess my view is more that if someone adds the loop verify pass because their loop pass is misbehaving, it'll be frustrating of the verify misses the issue because of an out-of-date dominator tree.

We could instead verify the dominator tree, or just compute a known-correct one. I could see reasonable arguments in both directions.

As perhaps a better rationale -- imagine someone is writing code to update LoopInfo (and possibly DominatorTree). They call verify as part of their update to debug stuff. Is it reasonable to have imposed an ordering requirement that the dominator tree update be applied first?

Anyways, this isn't a big deal, just that I somewhat prefer that where possible each verify step be as free-standing of other passes and state as possible in order to isolate problems. And here, we can compute the dominator tree with a single function call so it seems very much low-cost.

Some minor comments below about the particular code used. Happy for these to be "post commit" comments or whatever that you address as you go.

include/llvm/Analysis/LoopInfoImpl.h

535–541

Why not a lambda below? It wouldn't need to be a generic lambda as its already inside a function template and within that context you have specific types BlockT and LoopT already.

544

Same question, why not a lambda?

549–552

std::sort and std::equals? Seems simpler and there is no order concern.

[mzolotukhin]

Thanks, committed in r280280.

For DT recalculation we need to get Function from somewhere and I don't see an easy way to get it now. As for DT verification, it's possible, and I don't feel strong about either way, but slightly prefer keeping the stuff separate as we have an easy way to invoke each verifier both from command line and in the code.

Thanks,
Michael

include/llvm/Analysis/LoopInfoImpl.h

535–541

Can lambda be recursive?

544

Fixed.

549–552

Done, thanks!

[mehdi_amini]

llvm/trunk/include/llvm/Analysis/LoopInfoImpl.h

552 ↗

(On Diff #69894)

I'd expect it to be possible to get the Function at any time using BBMap.begin().first->getParent() here (assuming an early exit if empty earlier).

include/llvm/Analysis/LoopInfo.h

public:
   }
 
   /// Create the loop forest using a stable algorithm.
   void analyze(const DominatorTreeBase<BlockT> &DomTree);
 
   // Debugging
   void print(raw_ostream &OS) const;
 
-  void verify() const;
+  void verify(const DominatorTreeBase<BlockT> &DomTree) const;
 };
 
 // Implementation in LoopInfoImpl.h
 extern template class LoopInfoBase<BasicBlock, Loop>;
 
 class LoopInfo : public LoopInfoBase<BasicBlock, Loop> {
   typedef LoopInfoBase<BasicBlock, Loop> BaseT;
 

include/llvm/Analysis/LoopInfoImpl.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_LOOPINFOIMPL_H
 #define LLVM_ANALYSIS_LOOPINFOIMPL_H
 
 #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"
 
 namespace llvm {
 
 //===----------------------------------------------------------------------===//
 // APIs for simple analysis of the loop. See header notes.

 #if 0
   for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(),
          E = BBMap.end(); I != E; ++I)
     OS << "BB '" << I->first->getName() << "' level = "
        << I->second->getLoopDepth() << "\n";
 #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) {
+  if (BB1.size() != BB2.size())
+    return false;
+
+  SmallSetVector<T, 4> BBSet1;
+  for (T BB : BB1)
+    BBSet1.insert(BB);
+  for (T BB : BB2)
+    if (BBSet1.count(BB) != 1)
+      return false;
+
+  return true;
+}
+
+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>
+static bool 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;
+}
+
+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!");
     (*I)->verifyLoopNest(&Loops);
   }
 
   // Verify that blocks are mapped to valid loops.
 #ifndef NDEBUG
   for (auto &Entry : BBMap) {
     const BlockT *BB = Entry.first;
     LoopT *L = Entry.second;
     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.");
+
+  for (auto &I : LoopHeaders1) {
+    BlockT *H = I.first;
+    bool LoopsMatch =
+        compareLoops<BlockT, LoopT>(LoopHeaders1[H], LoopHeaders2[H]);
+    assert(LoopsMatch && "LoopInfo is incorrect.");
+  }
 #endif
 }
 
 } // End llvm namespace
 
 #endif

lib/Analysis/LoopInfo.cpp

 }
 
 void LoopInfoWrapperPass::verifyAnalysis() const {
   // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
   // function each time verifyAnalysis is called is very expensive. The
   // -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 {
   AU.setPreservesAll();
   AU.addRequired<DominatorTreeWrapperPass>();
 }
 
 void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
   LI.print(OS);
 }
 
 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();
 }
 
 //===----------------------------------------------------------------------===//
 // LoopBlocksDFS implementation
 //
 
 /// Traverse the loop blocks and store the DFS result.
 /// Useful for clients that just want the final DFS result and don't need to
 /// visit blocks during the initial traversal.
 void LoopBlocksDFS::perform(LoopInfo *LI) {
   LoopBlocksTraversal Traversal(*this, LI);
   for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
          POE = Traversal.end(); POI != POE; ++POI) ;
 }

lib/Transforms/Scalar/LoopDistribute.cpp

bool processLoop(std::function<const LoopAccessInfo &(Loop &)> &GetLAA) {
 
     // Now, we remove the instruction from each loop that don't belong to that
     // partition.
     Partitions.removeUnusedInsts();
     DEBUG(dbgs() << "\nAfter removing unused Instrs:\n");
     DEBUG(Partitions.printBlocks());
 
     if (LDistVerify) {
-      LI->verify();
+      LI->verify(*DT);
       DT->verifyDomTree();
     }
 
     ++NumLoopsDistributed;
     // Report the success.
     ORE->emitOptimizationRemark(LDIST_NAME, L, "distributed loop");
     return true;
   }