[RegionInfo] Verify getRegionFor

[Meinersbur]

Summary

Check the contents of BBtoRegion during analysis verification. It only takes place if -verify-region-info is passed or LLVM is compiled with XDEBUG.

RegionBase<Tr>::verifyRegion() also checks the RegionInfoBase<Tr>::VerifyRegionInfo flag, which is redundant, but verifyRegion() is public API and might be invoked from other sites. In order to avoid behavioral change, this check is not removed. In any case, no region will be verified unless VerifyRegionInfo is set.

[grosser]

This patch looks good (besides some smaller comments below).

First, it seems this patch contains three different changes in one, which could probably be committed
separately.

1. Use more descriptive error messages in RegionInfo's verifier

2. Verify the BBMap during

3. Take into account VerifyRegionInfo

We already have similar code in verifyRegion

template <class Tr>                                                              
void RegionBase<Tr>::verifyRegion() const {                                      
  // Only do verification when user wants to, otherwise this expensive check     
  // will be invoked by PMDataManager::verifyPreservedAnalysis when              
  // a regionpass (marked PreservedAll) finish.                                  
  if (!RegionInfoBase<Tr>::VerifyRegionInfo)                                     
    return;

I agree that the location you propose is better, but it probably makes sense to remove the old code and to briefly explain why this is safe and why you believe the new location is better.

include/llvm/Analysis/RegionInfo.h

695

Do not add verifyBBMap - at the beginning of the comment. This is an outdated style and LLVM is working towards removing such comments. If you
like you can drop (in a separate commit) the other 'functionName -' comment pieces as well in this file.

[Meinersbur]

In D11872#220006, @grosser wrote:

1. Use more descriptive error messages in RegionInfo's verifier

Would consider this trivial

3. Take into account VerifyRegionInfo

We already have similar code in verifyRegion

template <class Tr>                                                              
void RegionBase<Tr>::verifyRegion() const {                                      
  // Only do verification when user wants to, otherwise this expensive check     
  // will be invoked by PMDataManager::verifyPreservedAnalysis when              
  // a regionpass (marked PreservedAll) finish.                                  
  if (!RegionInfoBase<Tr>::VerifyRegionInfo)                                     
    return;

I agree that the location you propose is better, but it probably makes sense to remove the old code and to briefly explain why this is safe and why you believe the new location is better.

Before this addition verifyAnalysis only called verifyRegionNest which would do nothing unless VerifyRegionInfo is true. To keep it that way, I added the check to verifyAnalysis.

However, I don't know whether verifyRegionNest is called from elsewhere so I left the check there to avoid behavioral change.

[Meinersbur]

Adressed comments

include/llvm/Analysis/RegionInfo.h

class RegionInfoBase {
 
   /// The top level region.
   RegionT *TopLevelRegion;
 
 private:
   /// Map every BB to the smallest region, that contains BB.
   BBtoRegionMap BBtoRegion;
 
+  // verifyBBMap - Check whether the entries of BBtoRegion for the BBs of region
+  // SR are correct. Triggers an assertion if not. Calls itself recursively for
+  // subregions.
+  void verifyBBMap(const RegionT *SR) const;
+
   // isCommonDomFrontier - Returns true if BB is in the dominance frontier of
   // entry, because it was inherited from exit. In the other case there is an
   // edge going from entry to BB without passing exit.
   bool isCommonDomFrontier(BlockT *BB, BlockT *entry, BlockT *exit) const;
 
   // isRegion - Check if entry and exit surround a valid region, based on
   // dominance tree and dominance frontier.
   bool isRegion(BlockT *entry, BlockT *exit) const;

include/llvm/Analysis/RegionInfoImpl.h

if (getExit()) {
     exitName = "<Function Return>";
 
   return entryName + " => " + exitName;
 }
 
 template <class Tr>
 void RegionBase<Tr>::verifyBBInRegion(BlockT *BB) const {
   if (!contains(BB))
-    llvm_unreachable("Broken region found!");
+    llvm_unreachable("Broken region found: enumerated BB not in region!");
 
   BlockT *entry = getEntry(), *exit = getExit();
 
   for (SuccIterTy SI = BlockTraits::child_begin(BB),
                   SE = BlockTraits::child_end(BB);
        SI != SE; ++SI) {
     if (!contains(*SI) && exit != *SI)
-      llvm_unreachable("Broken region found!");
+      llvm_unreachable("Broken region found: edges leaving the region must go "
+                       "to the exit node!");
   }
 
   if (entry != BB) {
     for (PredIterTy SI = InvBlockTraits::child_begin(BB),
                     SE = InvBlockTraits::child_end(BB);
          SI != SE; ++SI) {
       if (!contains(*SI))
-        llvm_unreachable("Broken region found!");
+        llvm_unreachable("Broken region found: edges entering the region must "
+                         "go to the entry node!");
     }
   }
 }
 
 template <class Tr>
 void RegionBase<Tr>::verifyWalk(BlockT *BB, std::set<BlockT *> *visited) const {
   BlockT *exit = getExit();
 
RegionInfoBase<Tr>::RegionInfoBase()
     : TopLevelRegion(nullptr) {}
 
 template <class Tr>
 RegionInfoBase<Tr>::~RegionInfoBase() {
   releaseMemory();
 }
 
 template <class Tr>
+void RegionInfoBase<Tr>::verifyBBMap(const RegionT *R) const {
+  assert(R && "Re must be non-null");
+  for (auto I = R->element_begin(), E = R->element_end(); I != E; ++I) {
+    if (I->isSubRegion()) {
+      const RegionT *SR = I->template getNodeAs<RegionT>();
+      verifyBBMap(SR);
+    } else {
+      BlockT *BB = I->template getNodeAs<BlockT>();
+      if (getRegionFor(BB) != R)
+        llvm_unreachable("BB map does not match region nesting");
+    }
+  }
+}
+
+template <class Tr>
 bool RegionInfoBase<Tr>::isCommonDomFrontier(BlockT *BB, BlockT *entry,
                                              BlockT *exit) const {
   for (PredIterTy PI = InvBlockTraits::child_begin(BB),
                   PE = InvBlockTraits::child_end(BB);
        PI != PE; ++PI) {
     BlockT *P = *PI;
     if (DT->dominates(entry, P) && !DT->dominates(exit, P))
       return false;
void RegionInfoBase<Tr>::releaseMemory() {
   BBtoRegion.clear();
   if (TopLevelRegion)
     delete TopLevelRegion;
   TopLevelRegion = nullptr;
 }
 
 template <class Tr>
 void RegionInfoBase<Tr>::verifyAnalysis() const {
+  // Do only verify regions if explicitely activated using XDEBUG or
+  // -verify-region-info
+  if (!RegionInfoBase<Tr>::VerifyRegionInfo)
+    return;
+
   TopLevelRegion->verifyRegionNest();
+
+  verifyBBMap(TopLevelRegion);
 }
 
 // Region pass manager support.
 template <class Tr>
 typename Tr::RegionT *RegionInfoBase<Tr>::getRegionFor(BlockT *BB) const {
   typename BBtoRegionMap::const_iterator I = BBtoRegion.find(BB);
   return I != BBtoRegion.end() ? I->second : nullptr;
 }