[mlir][IR] Hash nesting structure in OperationFingerPrint

[springerm]

Summary

The following ops currently have the same finger print, even though they are different:

func.func @test() {
  "test.foo"() ({
    "test.bar"() : () -> ()
  }) : () -> ()
}

And:

func.func @test() {
  "test.bar"() : () -> ()
  "test.foo"() ({ }) : () -> ()
}

The SHA1 hash used in OperationFingerPrint is order-sensitive, but the ops are hashed in the same order (post-order traversal), so the hash is the same. Switching to pre-order traversal does not solve the issue; a similar example, where IR differs just in its nesting structure, can be constructed.

The problem is solved by hashing the parent op pointer. (Alternatively, a custom traversal over the IR that hashes scope markers ({}) could be used.)

Note: Without this change, the expensive check in D144552 detects a false positive in mlir/test/IR/greedy-pattern-rewriter-driver.mlir.

mlir/lib/IR/OperationSupport.cpp

 
 OperationFingerPrint::OperationFingerPrint(Operation *topOp) {
   llvm::SHA1 hasher;
 
   // Hash each of the operations based upon their mutable bits:
   topOp->walk([&](Operation *op) {
     //   - Operation pointer
     addDataToHash(hasher, op);
+    //   - Parent operation pointer (to take into account the nesting structure)
+    if (op != topOp)
+      addDataToHash(hasher, op->getParentOp());
     //   - Attributes
     addDataToHash(hasher, op->getDiscardableAttrDictionary());
     //   - Properties
     addDataToHash(hasher, op->hashProperties());
     //   - Blocks in Regions
     for (Region &region : op->getRegions()) {
       for (Block &block : region) {
         addDataToHash(hasher, &block);