[MLIR] Fixed missing append when adding an domain

[kumasento]

Summary

The prior diff that introduced addAffineIfOpDomain forgot to append constraints from the ifOp domain. This diff fixed that problem.

[kumasento]

mlir/test/Transforms/memref-dependence-check.mlir

20

Hi Uday @bondhugula

When taking into account the constraints introduced by affine.if, this affine.store statement will not be executed and there won't have dependences from 0 to 1. Please correct me if there is anything wrong.

If that is true, I'm wondering how would you prefer to make changes. Should I revise the test case as above, or should I change the dependence analysis behaviour, e.g., don't involve the domain from affine.if when checking dependences?

Thanks!

[kumasento]

Hi Uday @bondhugula

Sorry that my prior diff D84698 has a stupid bug: I thought that mergeAndAlighIdsWithOthers would append constraints as well (merge seemed like an action on constraints not IDs), and apparently I was wrong. I need to use append to insert new constraints from the IfOp's domain. The test case that I introduced last time cannot find this kind of bug.

There are two things that I may need your input:

1. It is possible that append may add some redundant constraints, is that OK?
2. The old store_may_execute_before_load test case now have a different behaviour because we take into account the IfOp domain. How do you suggest we should update that test case?

Thanks!

Ruizhe

[bondhugula]

mlir/test/Transforms/memref-dependence-check.mlir

20

You should definitely consider the domain of affine.if - that makes the dependence analysis precise. So you should revise the test case. :) Adding the constraints for any surrounding if's is the right thing.

[bondhugula]

In D86421#2232613, @kumasento wrote:

Hi Uday @bondhugula

Sorry that my prior diff D84698 has a stupid bug: I thought that mergeAndAlighIdsWithOthers would append constraints as well (merge seemed like an action on constraints not IDs), and apparently I was wrong. I need to use append to insert new constraints from the IfOp's domain. The test case that I introduced last time cannot find this kind of bug.

There are two things that I may need your input:

1. It is possible that append may add some redundant constraints, is that OK?

Yes, of course. You aren't in general expected to check in a scenario like this if the constraints you are adding are redundant - we don't in other cases. There are other simple O(N) methods to remove duplicate constraints like this (where N = number of constraints), and more complex methods to remove more complex redundancy.

2. The old store_may_execute_before_load test case now have a different behaviour because we take into account the IfOp domain. How do you suggest we should update that test case?

The test case should definitely be updated given that the dependence analysis and any other routines using the same infra would now be more precise. I've responded to your other inline comment as well.

• Uday

Thanks!

Ruizhe

[bondhugula]

mlir/lib/Analysis/AffineStructures.cpp

738

I missed this earlier in the review. We should have tested some of the infra that was affected (became more powerful) as a result of this.

mlir/test/Transforms/memref-dependence-check.mlir

1047

We'll need a comment here to explain the check (the increased upper bound) - otherwise, it would appear subtle.

[bondhugula]

mlir/test/Transforms/memref-dependence-check.mlir

1047

Please also add an extra test case either in this file or in memref-bound-check where you have a surrounding affine.if and the test is in bounds as a result of having considered the affine.if's domain. That would be a good positive test case for addAffineIfDomain. Note that those methods aren't able to deal with else yet (would still be imprecise), but under affine.if should be accounted for now.

[kumasento]

Updated store_may_execute_before_load comments

mlir/test/Transforms/memref-dependence-check.mlir

20

Sure! I've revised the comments to reflect the new updates.

1047

Thank you Uday. It is a trivial update to fix a typo. Keeping 100 may cause confusion since there are 101 number of elements.

1047

Please also add an extra test case either in this file or in memref-bound-check where you have a surrounding affine.if and the test is in bounds as a result of having considered the affine.if's domain. That would be a good positive test case for addAffineIfDomain. Note that those methods aren't able to deal with else yet (would still be imprecise), but under affine.if should be accounted for now.

Thank you for pointing that test out! Currently I don't think memref-hound-check has considered affine.if. For example, when computing the MemRefRegion only constraints from loop IVs are involved.

I will fix this in another diff later.

[bondhugula]

mlir/test/Transforms/memref-dependence-check.mlir

13

-> indicates

[bondhugula]

mlir/test/Transforms/memref-dependence-check.mlir

1047

Sounds good, thanks. You are right - MemRefRegion::compute actually needs an update.

[bondhugula]

I've committed this after taking care of the typo, a whitespace error, and typos in the commit title/summary.

[kumasento]

In D86421#2242810, @bondhugula wrote:

I've committed this after taking care of the typo, a whitespace error, and typos in the commit title/summary.

Thank you Uday for taking care of them! I will improve memref-bound-check later.

mlir/lib/Analysis/AffineStructures.cpp

 void FlatAffineConstraints::addAffineIfOpDomain(AffineIfOp ifOp) {
   // Create the base constraints from the integer set attached to ifOp.
   FlatAffineConstraints cst(ifOp.getIntegerSet());
 
   // Bind ids in the constraints to ifOp operands.
   SmallVector<Value, 4> operands = ifOp.getOperands();
   cst.setIdValues(0, cst.getNumDimAndSymbolIds(), operands);
 
-  // Merge the constraints from ifOp to the current domain.
+  // Merge the constraints from ifOp to the current domain. We need first merge
+  // and align the IDs from both constraints, and then append the constraints
+  // from the ifOp into the current one.
   mergeAndAlignIdsWithOther(0, &cst);
+  append(cst);
 }
 
 // Searches for a constraint with a non-zero coefficient at 'colIdx' in
 // equality (isEq=true) or inequality (isEq=false) constraints.
 // Returns true and sets row found in search in 'rowIdx'.
 // Returns false otherwise.
 static bool findConstraintWithNonZeroAt(const FlatAffineConstraints &cst,
                                         unsigned colIdx, bool isEq,

mlir/test/Transforms/memref-dependence-check.mlir

 // RUN: mlir-opt %s -test-memref-dependence-check  -split-input-file -verify-diagnostics | FileCheck %s
 
 // -----
 
 #set0 = affine_set<(d0) : (1 == 0)>
 
 // CHECK-LABEL: func @store_may_execute_before_load() {
 func @store_may_execute_before_load() {
   %m = alloc() : memref<10xf32>
   %cf7 = constant 7.0 : f32
   %c0 = constant 4 : index
-  // There is a dependence from store 0 to load 1 at depth 1 because the
-  // ancestor IfOp of the store, dominates the ancestor ForSmt of the load,
-  // and thus the store "may" conditionally execute before the load.
+  // There is no dependence from store 0 to load 1 at depth if we take into account
+  // the constraint introduced by the following `affine.if`, which indicate that 
+  // the store 0 will never be executed.
   affine.if #set0(%c0) {
     affine.for %i0 = 0 to 10 {
       affine.store %cf7, %m[%i0] : memref<10xf32>
       // expected-remark@above {{dependence from 0 to 0 at depth 1 = false}}
       // expected-remark@above {{dependence from 0 to 0 at depth 2 = false}}
-      // expected-remark@above {{dependence from 0 to 1 at depth 1 = true}}
+      // expected-remark@above {{dependence from 0 to 1 at depth 1 = false}}
     }
   }
   affine.for %i1 = 0 to 10 {
     %v0 = affine.load %m[%i1] : memref<10xf32>
     // expected-remark@above {{dependence from 1 to 1 at depth 1 = false}}
     // expected-remark@above {{dependence from 1 to 1 at depth 2 = false}}
     // expected-remark@above {{dependence from 1 to 0 at depth 1 = false}}
   }

 
 // CHECK-LABEL: func @test_interleaved_affine_for_if() {
 func @test_interleaved_affine_for_if() {
   %0 = alloc() : memref<101xf32>
   %c0 = constant 0 : index
   %N = dim %0, %c0 : memref<101xf32>
   %cf7 = constant 7.0 : f32
 
-  affine.for %i0 = 0 to 100 {
+  affine.for %i0 = 0 to 101 {
     affine.if #set1(%i0)[%N] {
       %1 = affine.load %0[%i0] : memref<101xf32>
       // expected-remark@above {{dependence from 0 to 0 at depth 1 = false}}
       // expected-remark@above {{dependence from 0 to 0 at depth 2 = false}}
       // expected-remark@above {{dependence from 0 to 1 at depth 1 = false}}
       // expected-remark@above {{dependence from 0 to 1 at depth 2 = true}}
     }