[LoopInfo] Verify BBMap tracks innermost loops for BBs.

[fhahn]

Summary

By checking that none of the child loops contain a BB we make sure BBMap
contains the innermost loop defining BB. This invariant was violated in
LoopInterchange and got caught by this assertion.

[fhahn]

LoopInterchange did that wrong and this additional assertion catches that. The fix for LoopInterchange is at D45970

[efriedma]

LGTM

While you're at it, could you also add a check to compareLoops to make sure the DenseBlockSet is consistent?

[fhahn]

Add check to make sure the blocks sets match. I had to add a function to get a handle for a const blocks sets, what do you think? I would be happy to split this up in 2 patches if necessary.

[efriedma]

LGTM

include/llvm/Analysis/LoopInfo.h

public:
   }
   /// Return a direct, mutable handle to the blocks set so that we can
   /// mutate it efficiently.
   SmallPtrSetImpl<const BlockT *> &getBlocksSet() {
     assert(!isInvalid() && "Loop not in a valid state!");
     return DenseBlockSet;
   }
 
+  /// Return a direct, immutable handle to the blocks set.
+  const SmallPtrSetImpl<const BlockT *> &getBlocksSet() const {
+    assert(!isInvalid() && "Loop not in a valid state!");
+    return DenseBlockSet;
+  }
+
   /// Return true if this loop is no longer valid.  The only valid use of this
   /// helper is "assert(L.isInvalid())" or equivalent, since IsInvalid is set to
   /// true by the destructor.  In other words, if this accessor returns true,
   /// the caller has already triggered UB by calling this accessor; and so it
   /// can only be called in a context where a return value of true indicates a
   /// programmer error.
   bool isInvalid() const {
 #if LLVM_ENABLE_ABI_BREAKING_CHECKS

include/llvm/Analysis/LoopInfoImpl.h

for (const LoopT *SubL : *L) {
     OtherLoopHeaders.erase(SubH);
     compareLoops(SubL, OtherSubL, OtherLoopHeaders);
   }
 
   std::vector<BlockT *> BBs = L->getBlocks();
   std::vector<BlockT *> OtherBBs = OtherL->getBlocks();
   assert(compareVectors(BBs, OtherBBs) &&
          "Mismatched basic blocks in the loops!");
+
+  const SmallPtrSetImpl<const BlockT *> &BlocksSet = L->getBlocksSet();
+  const SmallPtrSetImpl<const BlockT *> &OtherBlocksSet = L->getBlocksSet();
+  assert(BlocksSet.size() == OtherBlocksSet.size() &&
+         std::all_of(BlocksSet.begin(), BlocksSet.end(),
+                     [&OtherBlocksSet](const BlockT *BB) {
+                       return OtherBlocksSet.count(BB);
+                     }) &&
+         "Mismatched basic blocks in BlocksSets!");
 }
 #endif
 
 template <class BlockT, class LoopT>
 void LoopInfoBase<BlockT, LoopT>::verify(
     const DomTreeBase<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");
+    for (LoopT *ChildLoop : *L)
+      assert(!ChildLoop->contains(BB) &&
+             "BBMap should point to the innermost loop containing BB");
   }
 
   // Recompute LoopInfo to verify loops structure.
   LoopInfoBase<BlockT, LoopT> OtherLI;
   OtherLI.analyze(DomTree);
 
   // Build a map we can use to move from our LI to the computed one. This
   // allows us to ignore the particular order in any layer of the loop forest