[MLIR] Allow unreachable blocks to violate dominance property.

[stephenneuendorffer]

Summary

It is possible for optimizations to create SSA code which violates
the dominance property in unreachable blocks. Equivalently, dominance
computed using normal mechanisms is undefined in unreachable blocks.

See discussion here: https://llvm.discourse.group/t/rfc-allowing-dialects-to-relax-the-ssa-dominance-condition/833/51

This patch only checks the dominance condition inside blocks which are
reachable from the the entry block of their region. Note that the
dominance conditions of regions contained in an unreachable block are
still checked.

[lattner]

This looks great, thank you!

mlir/lib/IR/Verifier.cpp

228

Please run clang format on this in the LLVM Style. You need a space after the 'if' and put the brace below on the same line as the 'else'.

[rriddle]

mlir/lib/IR/Dominance.cpp

186

Is there a reason we assume unknown blocks are reachable?

186

(Not that I disagree with your choice here, just checking if you thought about it)

mlir/lib/IR/Verifier.cpp

228

nit: These if/else are big enough that they should have braces.

if (...) {
  ...
  return success();
}

...
return success();

mlir/test/IR/invalid.mlir

1539

nit: align the message with the code line.

1545

nit: Move this expected message above.

mlir/test/IR/parser.mlir

1248

nit: Format these checks like the other tests in this file. Right now this test is really hard to read.

mlir/include/mlir/IR/Dominance.h

public:
   DominanceInfoNode *getNode(Block *a);
 
 protected:
   using super = DominanceInfoBase<IsPostDom>;
 
   /// Return true if the specified block A properly dominates block B.
   bool properlyDominates(Block *a, Block *b) const;
 
+  /// Return true if the specified block is reachable from the entry
+  /// block of its region.
+  bool isReachableFromEntry(Block *a) const;
+
   /// A mapping of regions to their base dominator tree.
   DenseMap<Region *, std::unique_ptr<base>> dominanceInfos;
 };
 } // end namespace detail
 
 /// A class for computing basic dominance information.
 class DominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/false> {
 public:
   using super::super;
 
+  /// Return true if the specified block is reachable from the entry
+  /// block of its region.
+  bool isReachableFromEntry(Block *a) const {
+    return super::isReachableFromEntry(a);
+  }
+
   /// Return true if operation A properly dominates operation B.
   bool properlyDominates(Operation *a, Operation *b) const;
 
   /// Return true if operation A dominates operation B.
   bool dominates(Operation *a, Operation *b) const {
     return a == b || properlyDominates(a, b);
   }
 
public:
   void updateDFSNumbers();
 };
 
 /// A class for computing basic postdominance information.
 class PostDominanceInfo : public detail::DominanceInfoBase</*IsPostDom=*/true> {
 public:
   using super::super;
 
+  /// Return true if the specified block is reachable from the entry
+  /// block of its region.
+  bool isReachableFromEntry(Block *a) const {
+    return super::isReachableFromEntry(a);
+  }
+
   /// Return true if operation A properly postdominates operation B.
   bool properlyPostDominates(Operation *a, Operation *b);
 
   /// Return true if operation A postdominates operation B.
   bool postDominates(Operation *a, Operation *b) {
     return a == b || properlyPostDominates(a, b);
   }
 

mlir/lib/IR/Dominance.cpp

bool DominanceInfoBase<IsPostDom>::properlyDominates(Block *a, Block *b) const {
   // If we don't have a dominance information for this region, assume that b is
   // dominated by anything.
   auto baseInfoIt = dominanceInfos.find(regionA);
   if (baseInfoIt == dominanceInfos.end())
     return true;
   return baseInfoIt->second->properlyDominates(a, b);
 }
 
+/// Return true if the specified block is reachable from the entry block of its
+/// region.
+template <bool IsPostDom>
+bool DominanceInfoBase<IsPostDom>::isReachableFromEntry(Block *a) const {
+  auto *regionA = a->getParent();
+  auto baseInfoIt = dominanceInfos.find(regionA);
+  if (baseInfoIt == dominanceInfos.end())
+    return true;
+  return baseInfoIt->second->isReachableFromEntry(a);
+}
+
 template class mlir::detail::DominanceInfoBase</*IsPostDom=*/true>;
 template class mlir::detail::DominanceInfoBase</*IsPostDom=*/false>;
 
 //===----------------------------------------------------------------------===//
 // DominanceInfo
 //===----------------------------------------------------------------------===//
 
 /// Return true if operation A properly dominates operation B.

mlir/lib/IR/Verifier.cpp

LogicalResult OperationVerifier::verifyOperation(Operation &op) {
   }
 
   return success();
 }
 
 LogicalResult OperationVerifier::verifyDominance(Region &region) {
   // Verify the dominance of each of the held operations.
   for (auto &block : region)
-    for (auto &op : block)
+    // Dominance is only reachable inside reachable blocks.
+    if (domInfo->isReachableFromEntry(&block))
+      for (auto &op : block) {
         if (failed(verifyDominance(op)))
           return failure();
+      }
+    else
+      // Verify the dominance of each of the nested blocks within this
+      // operation, even if the operation itself is not reachable.
+      for (auto &op : block)
+        for (auto &region : op.getRegions())
+          if (failed(verifyDominance(region)))
+            return failure();
   return success();
 }
 
 LogicalResult OperationVerifier::verifyDominance(Operation &op) {
   // Check that operands properly dominate this use.
   for (unsigned operandNo = 0, e = op.getNumOperands(); operandNo != e;
        ++operandNo) {
     auto operand = op.getOperand(operandNo);

mlir/test/IR/invalid.mlir

^bb1:
   // expected-note @+1 {{previously used here with type 'i8'}}
   return %1 : i8
 
 ^bb2:
   // expected-error @+1 {{definition of SSA value '%1#0' has type 'f32'}}
   %1 = "bar"() : () -> (f32)
   br ^bb1
 }
+
+// -----
+
+func @dominance_error_in_unreachable_op() -> i1 {
+  %c = constant 0 : i1
+  return %c : i1
+^bb0:
+  "dummy" () ({  // unreachable
+    ^bb1:
+// expected-error @+1 {{operand #0 does not dominate this use}}
+      %2:3 = "bar"(%1) : (i64) -> (i1,i1,i1)
+      br ^bb4
+    ^bb2:
+      br ^bb2
+    ^bb4:
+      %1 = "foo"() : ()->i64   // expected-note {{operand defined here}}
+  }) : () -> ()
+  return %c : i1
+}

mlir/test/IR/parser.mlir

func @pretty_names() {
   // CHECK-NOT: attributes
 
   %q:3, %r = test.string_attr_pretty_name
   // CHECK: %q, %q_1, %q_2, %r = test.string_attr_pretty_name attributes {names = ["q", "q", "q", "r"]}
 
   // CHECK: return
   return
 }
+
+func @unreachable_dominance_violation_ok() -> i1 {
+  %c = constant 0 : i1       // CHECK: [[VAL:%.*]] = constant 0 : i1
+  return %c : i1    // CHECK:   return [[VAL]] : i1
+^bb1:         // CHECK: ^bb1:   // no predecessors
+  // %1 is not dominated by it's definition, but block is not reachable.
+  %2:3 = "bar"(%1) : (i64) -> (i1,i1,i1) // CHECK: [[VAL2:%.*]]:3 = "bar"([[VAL3:%.*]]) : (i64) -> (i1, i1, i1)
+  br ^bb4     // CHECK:   br ^bb3
+^bb2:         // CHECK: ^bb2:   // pred: ^bb2
+  br ^bb2     // CHECK:   br ^bb2
+^bb4:         // CHECK: ^bb3:   // pred: ^bb1
+  %1 = "foo"() : ()->i64 // CHECK: [[VAL3]] = "foo"() : () -> i64
+  return %2#1 : i1 // CHECK: return [[VAL2]]#1 : i1
+}            // CHECK: }