[MLIR] Fix dominance info method - properlyDominates

[bondhugula]

Summary

Fix properlyDominates for the case where an operation could dominate
another one appearing before it in the same block. The only paths to the
latter could be from the former.

[bondhugula]

Update comments.

[lattner]

Thank you for tackling this Uday!

The right check here is to see if the block isReachableFromEntry (which is a method of dominator set), not hasNoPredecessors().

It could be part of an unreachable cycle or something like that, in which the same (lack of) dominance properties hold.

[lattner]

The equivalent check in LLVM is here if it is helpful:
https://github.com/llvm/llvm-project/blob/master/llvm/lib/IR/Dominators.cpp#L258

[bondhugula]

In D78012#1977945, @lattner wrote:

Thank you for tackling this Uday!

The right check here is to see if the block isReachableFromEntry (which is a method of dominator set), not hasNoPredecessors().

Looks like I jumped on to the revision too quickly - but what you suggest above and the LLVM one goes against my understanding of the dominance model. Even if the use is unreachable from the entry, with this revision, you only consider it dominated if the def dominates the use (within that unreachable part). See lines 206-208 in the revision - hasNoPredecessors() isn't the only thing I'm doing. We could discuss this on the discussion forum first.

It could be part of an unreachable cycle or something like that, in which the same (lack of) dominance properties hold.

[bondhugula]

Abandoning this for want of more clarity...

mlir/lib/Analysis/Dominance.cpp

 
 template class mlir::detail::DominanceInfoBase</*IsPostDom=*/true>;
 template class mlir::detail::DominanceInfoBase</*IsPostDom=*/false>;
 
 //===----------------------------------------------------------------------===//
 // DominanceInfo
 //===----------------------------------------------------------------------===//
 
-/// Return true if operation A properly dominates operation B.
+/// Returns true if operation A properly dominates operation B.
 bool DominanceInfo::properlyDominates(Operation *a, Operation *b) {
   auto *aBlock = a->getBlock(), *bBlock = b->getBlock();
 
-  // If a or b are not within a block, then a does not dominate b.
+  // If a or b are not within a block, then a does not properly dominate b.
   if (!aBlock || !bBlock)
     return false;
 
   // If the blocks are the same, then check if b is before a in the block.
-  if (aBlock == bBlock)
-    return a->isBeforeInBlock(b);
+  if (aBlock == bBlock) {
+    if (a->isBeforeInBlock(b))
+      return true;
+
+    // Even if b is before a in their block, if aBlock dominates all
+    // predecessors of aBlock, a dominates b.
+
+    // Can't be equal for proper dominance.
+    if (a == b || aBlock->hasNoPredecessors())
+      return false;
+
+    return llvm::all_of(aBlock->getPredecessors(),
+                        [&](Block *p) { return dominates(aBlock, p); });
+  }
 
   // Traverse up b's hierarchy to check if b's block is contained in a's.
   if (auto *bAncestor = aBlock->findAncestorOpInBlock(*b)) {
     // Since we already know that aBlock != bBlock, here bAncestor != b.
     // a and bAncestor are in the same block; check if 'a' dominates
     // bAncestor.
     return dominates(a, bAncestor);
   }

mlir/test/IR/dominance.mlir

+// RUN: mlir-opt %s | FileCheck %s
+
+// Verify dominance related functions in "cyclic" cases.
+// CHECK-LABEL: func @dominance
+func @dominance(%n: i32, %p : i1) -> i32 {
+  %x = addi %n, %n : i32
+  return %x : i32
+
+  // Self loop.
+^bar:
+  %y = addi %z, %x : i32
+  // muli does dominate addi.
+  %z = muli %y, %y : i32
+  br ^bar
+
+  // abc and xyz cycle.
+^abc:
+  %a = addi %b, %x : i32
+  // muli does dominate addi.
+  %b = muli %a, %a : i32
+  br ^xyz
+
+^xyz:
+  br ^abc
+
+  // c1, c2, c3 are an SCC.
+^c1:
+  %u = addi %v, %x : i32
+  // muli does dominate addi.
+  %v = muli %u, %u : i32
+  cond_br %p, ^c2, ^c3
+
+^c2:
+  br ^c1
+
+^c3:
+  br ^c1
+}