[mlir] Fix post-dominance between blocks of different regions.

[ThomasRaoux]

Summary

If block A and B are in different regions and region of A is not an ancestor of B, either A is included in region of B or the two regions are disjoint. In both case A doesn't post-dominate B.

mlir/lib/IR/Dominance.cpp

bool DominanceInfoBase<IsPostDom>::properlyDominates(Block *a, Block *b) const {
   // If both blocks are not in the same region, 'a' properly dominates 'b' if
   // 'b' is defined in an operation region that (recursively) ends up being
   // dominated by 'a'. Walk up the list of containers enclosing B.
   Region *regionA = a->getParent();
   if (regionA != b->getParent()) {
     b = traverseAncestors(
         b, [&](Block *block) { return block->getParent() == regionA; });
 
-    // If we could not find a valid block b then it is either a not a dominator
-    // or a post dominator.
+    // If we could not find a valid block b then it is a not a dominator.
     if (!b)
-      return IsPostDom;
+      return false;
 
     // Check to see if the ancestor of 'b' is the same block as 'a'.
     if (a == b)
       return true;
   }
 
   // Otherwise, use the standard dominance functionality.
 

mlir/test/Analysis/test-dominance.mlir

 // CHECK-NEXT: Nearest(3, 3) = 3
 // CHECK-NEXT: Nearest(3, 4) = 4
 // CHECK-NEXT: Nearest(3, 5) = 5
 // CHECK: Nearest(4, 0) = 1
 // CHECK-NEXT: Nearest(4, 1) = 1
 // CHECK-NEXT: Nearest(4, 2) = 2
 // CHECK-NEXT: Nearest(4, 3) = 4
 // CHECK-NEXT: Nearest(4, 4) = 4
-// CHECK-NEXT: Nearest(4, 5) = 5
+// CHECK-NEXT: Nearest(4, 5) = 5
+// CHECK-LABEL: --- Block Dominance relationship ---
+// CHECK-NEXT: dominates(0, 0) = true
+// CHECK-NEXT: dominates(0, 1) = true
+// CHECK-NEXT: dominates(0, 2) = true
+// CHECK-NEXT: dominates(0, 3) = true
+// CHECK-NEXT: dominates(0, 4) = true
+// CHECK-NEXT: dominates(0, 5) = true
+// CHECK-NEXT: dominates(0, 6) = false
+// CHECK-NEXT: dominates(1, 0) = false
+// CHECK-NEXT: dominates(1, 1) = true
+// CHECK-NEXT: dominates(1, 2) = true
+// CHECK-NEXT: dominates(1, 3) = true
+// CHECK-NEXT: dominates(1, 4) = true
+// CHECK-NEXT: dominates(1, 5) = true
+// CHECK-NEXT: dominates(1, 6) = false
+// CHECK-NEXT: dominates(2, 0) = false
+// CHECK-NEXT: dominates(2, 1) = false
+// CHECK-NEXT: dominates(2, 2) = true
+// CHECK-NEXT: dominates(2, 3) = true
+// CHECK-NEXT: dominates(2, 4) = true
+// CHECK-NEXT: dominates(2, 5) = false
+// CHECK-NEXT: dominates(2, 6) = false
+// CHECK-NEXT: dominates(3, 0) = false
+// CHECK-NEXT: dominates(3, 1) = false
+// CHECK-NEXT: dominates(3, 2) = false
+// CHECK-NEXT: dominates(3, 3) = true
+// CHECK-NEXT: dominates(3, 4) = false
+// CHECK-NEXT: dominates(3, 5) = false
+// CHECK-NEXT: dominates(3, 6) = false
+// CHECK-NEXT: dominates(4, 0) = false
+// CHECK-NEXT: dominates(4, 1) = false
+// CHECK-NEXT: dominates(4, 2) = false
+// CHECK-NEXT: dominates(4, 3) = true
+// CHECK-NEXT: dominates(4, 4) = true
+// CHECK-NEXT: dominates(4, 5) = false
+// CHECK-NEXT: dominates(4, 6) = false
+// CHECK-NEXT: dominates(5, 0) = false
+// CHECK-NEXT: dominates(5, 1) = false
+// CHECK-NEXT: dominates(5, 2) = false
+// CHECK-NEXT: dominates(5, 3) = false
+// CHECK-NEXT: dominates(5, 4) = false
+// CHECK-NEXT: dominates(5, 5) = true
+// CHECK-NEXT: dominates(5, 6) = false
+// CHECK-NEXT: dominates(6, 0) = true
+// CHECK-NEXT: dominates(6, 1) = true
+// CHECK-NEXT: dominates(6, 2) = true
+// CHECK-NEXT: dominates(6, 3) = true
+// CHECK-NEXT: dominates(6, 4) = true
+// CHECK-NEXT: dominates(6, 5) = true
+// CHECK-NEXT: dominates(6, 6) = true
+// CHECK-LABEL: --- Block PostDominance relationship ---
+// CHECK-NEXT: postdominates(0, 0) = true
+// CHECK-NEXT: postdominates(0, 1) = false
+// CHECK-NEXT: postdominates(0, 2) = false
+// CHECK-NEXT: postdominates(0, 3) = false
+// CHECK-NEXT: postdominates(0, 4) = false
+// CHECK-NEXT: postdominates(0, 5) = false
+// CHECK-NEXT: postdominates(0, 6) = false
+// CHECK-NEXT: postdominates(1, 0) = true
+// CHECK-NEXT: postdominates(1, 1) = true
+// CHECK-NEXT: postdominates(1, 2) = true
+// CHECK-NEXT: postdominates(1, 3) = true
+// CHECK-NEXT: postdominates(1, 4) = true
+// CHECK-NEXT: postdominates(1, 5) = false
+// CHECK-NEXT: postdominates(1, 6) = false
+// CHECK-NEXT: postdominates(2, 0) = false
+// CHECK-NEXT: postdominates(2, 1) = false
+// CHECK-NEXT: postdominates(2, 2) = true
+// CHECK-NEXT: postdominates(2, 3) = true
+// CHECK-NEXT: postdominates(2, 4) = true
+// CHECK-NEXT: postdominates(2, 5) = false
+// CHECK-NEXT: postdominates(2, 6) = false
+// CHECK-NEXT: postdominates(3, 0) = false
+// CHECK-NEXT: postdominates(3, 1) = false
+// CHECK-NEXT: postdominates(3, 2) = false
+// CHECK-NEXT: postdominates(3, 3) = true
+// CHECK-NEXT: postdominates(3, 4) = false
+// CHECK-NEXT: postdominates(3, 5) = false
+// CHECK-NEXT: postdominates(3, 6) = false
+// CHECK-NEXT: postdominates(4, 0) = false
+// CHECK-NEXT: postdominates(4, 1) = false
+// CHECK-NEXT: postdominates(4, 2) = false
+// CHECK-NEXT: postdominates(4, 3) = true
+// CHECK-NEXT: postdominates(4, 4) = true
+// CHECK-NEXT: postdominates(4, 5) = false
+// CHECK-NEXT: postdominates(4, 6) = false
+// CHECK-NEXT: postdominates(5, 0) = true
+// CHECK-NEXT: postdominates(5, 1) = true
+// CHECK-NEXT: postdominates(5, 2) = true
+// CHECK-NEXT: postdominates(5, 3) = true
+// CHECK-NEXT: postdominates(5, 4) = true
+// CHECK-NEXT: postdominates(5, 5) = true
+// CHECK-NEXT: postdominates(5, 6) = false
+// CHECK-NEXT: postdominates(6, 0) = true
+// CHECK-NEXT: postdominates(6, 1) = true
+// CHECK-NEXT: postdominates(6, 2) = true
+// CHECK-NEXT: postdominates(6, 3) = true
+// CHECK-NEXT: postdominates(6, 4) = true
+// CHECK-NEXT: postdominates(6, 5) = true
+// CHECK-NEXT: postdominates(6, 6) = true

mlir/test/lib/Transforms/TestDominance.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "mlir/IR/Dominance.h"
 #include "mlir/Pass/Pass.h"
 
 using namespace mlir;
 
+/// Overloaded helper to call the right function based on whether we are testing
+/// dominance or post-dominance.
+static bool dominatesOrPostDominates(DominanceInfo &dominanceInfo, Block *a,
+                                     Block *b) {
+  return dominanceInfo.dominates(a, b);
+}
+
+static bool dominatesOrPostDominates(PostDominanceInfo &dominanceInfo, Block *a,
+                                     Block *b) {
+  return dominanceInfo.postDominates(a, b);
+}
+
 namespace {
 
 /// Helper class to print dominance information.
 class DominanceTest {
 public:
   /// Constructs a new test instance using the given operation.
   DominanceTest(Operation *operation) : operation(operation) {
     // Create unique ids for each block.
     operation->walk([&](Operation *nested) {
       if (blockIds.count(nested->getBlock()) > 0)
         return;
       blockIds.insert({nested->getBlock(), blockIds.size()});
     });
   }
 
   /// Prints dominance information of all blocks.
   template <typename DominanceT>
-  void printDominance(DominanceT &dominanceInfo) {
+  void printDominance(DominanceT &dominanceInfo,
+                      bool printCommonDominatorInfo) {
     DenseSet<Block *> parentVisited;
     operation->walk([&](Operation *op) {
       Block *block = op->getBlock();
       if (!parentVisited.insert(block).second)
         return;
 
       DenseSet<Block *> visited;
       operation->walk([&](Operation *nested) {
         Block *nestedBlock = nested->getBlock();
         if (!visited.insert(nestedBlock).second)
           return;
+        if (printCommonDominatorInfo) {
           llvm::errs() << "Nearest(" << blockIds[block] << ", "
                        << blockIds[nestedBlock] << ") = ";
           Block *dom =
               dominanceInfo.findNearestCommonDominator(block, nestedBlock);
           if (dom)
             llvm::errs() << blockIds[dom];
           else
             llvm::errs() << "<no dom>";
           llvm::errs() << "\n";
+        } else {
+          if (std::is_same<DominanceInfo, DominanceT>::value)
+            llvm::errs() << "dominates(";
+          else
+            llvm::errs() << "postdominates(";
+          llvm::errs() << blockIds[block] << ", " << blockIds[nestedBlock]
+                       << ") = ";
+          if (dominatesOrPostDominates(dominanceInfo, block, nestedBlock))
+            llvm::errs() << "true\n";
+          else
+            llvm::errs() << "false\n";
+        }
       });
     });
   }
 
 private:
   Operation *operation;
   DenseMap<Block *, size_t> blockIds;
 };
 
 struct TestDominancePass : public PassWrapper<TestDominancePass, FunctionPass> {
 
   void runOnFunction() override {
     llvm::errs() << "Testing : " << getFunction().getName() << "\n";
     DominanceTest dominanceTest(getFunction());
 
     // Print dominance information.
     llvm::errs() << "--- DominanceInfo ---\n";
-    dominanceTest.printDominance(getAnalysis<DominanceInfo>());
+    dominanceTest.printDominance(getAnalysis<DominanceInfo>(),
+                                 /*printCommonDominatorInfo=*/true);
 
     llvm::errs() << "--- PostDominanceInfo ---\n";
-    dominanceTest.printDominance(getAnalysis<PostDominanceInfo>());
+    dominanceTest.printDominance(getAnalysis<PostDominanceInfo>(),
+                                 /*printCommonDominatorInfo=*/true);
+
+    // Print dominance relationship between blocks.
+    llvm::errs() << "--- Block Dominance relationship ---\n";
+    dominanceTest.printDominance(getAnalysis<DominanceInfo>(),
+                                 /*printCommonDominatorInfo=*/false);
+
+    llvm::errs() << "--- Block PostDominance relationship ---\n";
+    dominanceTest.printDominance(getAnalysis<PostDominanceInfo>(),
+                                 /*printCommonDominatorInfo=*/false);
   }
 };
 
 } // end anonymous namespace
 
 namespace mlir {
 namespace test {
 void registerTestDominancePass() {
   PassRegistration<TestDominancePass>(
       "test-print-dominance",
       "Print the dominance information for multiple regions.");
 }
 } // namespace test
 } // namespace mlir