Update static bound checker for Linalg to cover decreasing cases

[• inho9606]

Summary

The current static checker for linalg does not work on the decreasing index cases well. So, this is to Update the current static bound checker for linalg to cover decreasing index cases.

[nicolasvasilache]

canyou please add some tests?

[hanchung]

Thanks for adding this!

Please add some tests to invalid.mlir

mlir/lib/Dialect/Linalg/IR/LinalgInterfaces.cpp

472–473

We don't have to declare startLoopRangeValues above. Instead we can declare it here. E.g.,

SmallVector<int64_t, 4> startLoopRangeValues((*endLoopRangeValues).size(), 0);

492

I think we don't need to check if shapedDimSize > 0. It won't be dynamic dim because you already check it above.

493–501

Do we really need mapStr here? Can't we use indexingMaps[en.index()] directly?

508–521

How about having a inferredDimSize = std::max(firstIndex, lastIndex) + 1, so we can simplify the check. In this case, we don't have to check two times for the last part.

[• inho9606]

mlir/lib/Dialect/Linalg/IR/LinalgInterfaces.cpp

472–473

Oh, I remember it caused a linking error when I tried this first, but it works now.. I think I did something wrong. Thanks

492

Yes, but there is a testcase using shapes like memref<0xf32>.. If the size is 0, then the index should be -1 which would be always an error by this condition.

#accesses = [

affine_map<(i) -> (i)>

]

#trait = {

indexing_maps = #accesses,
iterator_types = ["parallel"]

}

func @dce_zero_memref(%arg0 : memref<0xf32>, %arg1: tensor<0xf32>) -> tensor<0xf32> {

// memref<0x32> is expected to be dce'ed
linalg.copy(%arg0, %arg0): memref<0xf32>, memref<0xf32>

// tensor<0xf32> cannot be dce'ed
%1 = linalg.generic #trait outs(%arg1 : tensor<0xf32>) {
^bb(%0: f32) :
  linalg.yield %0 : f32
} -> tensor<0xf32>

return %1: tensor<0xf32>

}

493–501

I couldn't find the way to use indexingMaps[en.index()] directly in the message.. I think it should be something convertable to string for the message. But the indexingMap is affineMap, so I thought I would need a method to convert it, but couldn't find.. Could you help me?

508–521

You are right. Thanks for reminding me max method..

[• inho9606]

1. Updating D101026: Update static bound checker for Linalg to cover decreasing cases #
2. Enter a brief description of the changes included in this update.
3. The first line is used as subject, next lines as comment.

Reflected the comments and added invalid test cases.

[hanchung]

I think you accidentally delete some invalid tests, could you add them back?

mlir/lib/Dialect/Linalg/IR/LinalgInterfaces.cpp

475–477

Let's rename them as startIndices and endIndices

492

I see. Seems to be corner case. It will be killed, though. Let's skip the check for this directly, we don't have to make it work with below logic.

493–501

I thought it is streamable and you could pass it to emitError directly. Does this work?

linalgOp.emitError("unexpected result less than 0 at expression #")
                 << j << " in affineMap\n" << indexingMaps[en.index()];

mlir/test/Dialect/Linalg/invalid.mlir

740–744

Can we use a simpler test case? This looks like an matmul with weird accessing. Let's create a reverse op test case?

[• inho9606]

mlir/lib/Dialect/Linalg/IR/LinalgInterfaces.cpp

492

Okay, then I'll ignore the case that dimsize is 0.

493–501

No it does not work,, it causes no match error..
error: no match for 'operator<<' (operand types are 'mlir::Diagnostic' and 'mlir::AffineMap')..

mlir/test/Dialect/Linalg/invalid.mlir

740–744

Okay sounds better! I'll update it next Monday.

[• inho9606]

1. Updating D101026: Update static bound checker for Linalg to cover decreasing cases #
2. Enter a brief description of the changes included in this update.
3. The first line is used as subject, next lines as comment.

Renamed variables, fixed the logic for dimsize 0, and fixed an invalid testcase.

[hanchung]

mlir/lib/Dialect/Linalg/IR/LinalgInterfaces.cpp

491–507

I think we can move this above the if-statement because you declare it right after use it.

491–508

I see, thanks for trying this out.

I think we can delete "affineMap\n". Having a new line is a bit weird to me, and you did not check the affine map in the test.

518

update the message? We should remove "or equal to"?

[• inho9606]

Uh, I think I found a case that this solution can't check, which does not have its maximum and minimum indices with the start and end indices. For example, if the affine_map is <(d0, d1) -> (d1 - d0)> and the ranges of d0 and d1 are 0 and 1, then this expression has
0 when d0 is 0 and d1 is 0,
1 when d0 is 0 and d1 is 1,
-1 when d0 is 1 and d1 is 0,
0 when d0 is 1 and d1 is 1.
I wanted to share this case.. And I think we should substitude
the maximum values for negative dims, and the minimum values for positive dims in order to get the real minimum indices. For the maximum indices, we need the minimum values for negative dims, and the maximum values for positive dims..

mlir/lib/Dialect/Linalg/IR/LinalgInterfaces.cpp

491–507

You are right, I missed the point. Thanks

491–508

Ah I see

518

Hmm, I think we should remain it because:
Let's say A is inferredSize, and B is shapedDimSize. Then,
A > B == B < A if statement (invalid case)
!(B < A) == B >= A Negation to Make the statement true
Am I correct?

[• inho9606]

1. Updating D101026: Update static bound checker for Linalg to cover decreasing cases #
2. Enter a brief description of the changes included in this update.
3. The first line is used as subject, next lines as comment.

Moved declaring a variable and updated the error message

[hanchung]

In D101026#2718549, @inho9606 wrote:

Uh, I think I found a case that this solution can't check, which does not have its maximum and minimum indices with the start and end indices. For example, if the affine_map is <(d0, d1) -> (d1 - d0)> and the ranges of d0 and d1 are 0 and 1, then this expression has
0 when d0 is 0 and d1 is 0,
1 when d0 is 0 and d1 is 1,
-1 when d0 is 1 and d1 is 0,
0 when d0 is 1 and d1 is 1.
I wanted to share this case.. And I think we should substitude
the maximum values for negative dims, and the minimum values for positive dims in order to get the real minimum indices. For the maximum indices, we need the minimum values for negative dims, and the maximum values for positive dims..

I never see this kind of statement before, and I highly suspect that this will be the case. For now, let's treat it as invalid. We can revert it if this is really the case in the future.

mlir/lib/Dialect/Linalg/IR/LinalgInterfaces.cpp

518

Yes, you're right. Sorry for the bad review comment.

[hanchung]

There are conflicts, could you rebase and fix it?

[• inho9606]

In D101026#2720142, @hanchung wrote:

There are conflicts, could you rebase and fix it?

Ah, I can't see the conflicts in my repository.. Rebase was successfully done. Could you tell me what files have conflicts?
Thanks

[hanchung]

In D101026#2721644, @inho9606 wrote:

In D101026#2720142, @hanchung wrote:

There are conflicts, could you rebase and fix it?

Ah, I can't see the conflicts in my repository.. Rebase was successfully done. Could you tell me what files have conflicts?
Thanks

I can not patch this, and the bot can not do it either. If you rebase successfully, you can update the patch. arc will ask you to provide some description and update the patch I think.

[• inho9606]

1. Updating D101026: Update static bound checker for Linalg to cover decreasing cases #
2. Enter a brief description of the changes included in this update.
3. The first line is used as subject, next lines as comment.

Rebased for merge?

[• inho9606]

In D101026#2721686, @hanchung wrote:

In D101026#2721644, @inho9606 wrote:

In D101026#2720142, @hanchung wrote:

There are conflicts, could you rebase and fix it?

Ah, I can't see the conflicts in my repository.. Rebase was successfully done. Could you tell me what files have conflicts?
Thanks

I can not patch this, and the bot can not do it either. If you rebase successfully, you can update the patch. arc will ask you to provide some description and update the patch I think.

I updated the patch with arc,, could you please check if it works again? Interesting..

[• inho9606]

In D101026#2719502, @hanchung wrote:

In D101026#2718549, @inho9606 wrote:

Uh, I think I found a case that this solution can't check, which does not have its maximum and minimum indices with the start and end indices. For example, if the affine_map is <(d0, d1) -> (d1 - d0)> and the ranges of d0 and d1 are 0 and 1, then this expression has
0 when d0 is 0 and d1 is 0,
1 when d0 is 0 and d1 is 1,
-1 when d0 is 1 and d1 is 0,
0 when d0 is 1 and d1 is 1.
I wanted to share this case.. And I think we should substitude
the maximum values for negative dims, and the minimum values for positive dims in order to get the real minimum indices. For the maximum indices, we need the minimum values for negative dims, and the maximum values for positive dims..

I never see this kind of statement before, and I highly suspect that this will be the case. For now, let's treat it as invalid. We can revert it if this is really the case in the future.

I think I can make the checker cover this interesting case as well using affineExpr to get maximum and minimum values. I'd like to try to push it more to make it as perfect as possible. Can I try to fix it more..?

[hanchung]

Hey Inho, the bot still could not apply the patch. The diff details show that it's failed. And I can't patch it locally either.

Could you try to run arc patch D1010260 on main branch?

And you will see

This diff is against commit a2c783f910b6034118f3d18dcd1519e9ff74f43f, but
    the commit is nowhere in the working copy. Try to apply it against the
    current working copy state? (a67a377014ceaaed55b2ba2259e080bc3fc42b43 \
    D101610)

I think I can make the checker cover this interesting case as well using affineExpr to get maximum and minimum values. I'd like to try to push it more to make it as perfect as possible. Can I try to fix it more..?

It's a rare case. If you'd like to push it more, I'd suggest to create another patch for it.

[• inho9606]

1. Updating D101026: Update static bound checker for Linalg to cover decreasing cases #
2. Enter a brief description of the changes included in this update.
3. The first line is used as subject, next lines as comment

#i
Try to fix the apply issue

mlir/lib/Dialect/Linalg/IR/LinalgInterfaces.cpp

for (auto resultIdx : llvm::seq<unsigned>(0, getNumOutputs())) {
     }
     reifiedReturnShapes.emplace_back(std::move(shapes));
   }
   return success();
 }
 
 LogicalResult mlir::linalg::detail::verifyStructuredOpInterface(Operation *op) {
   LinalgOp linalgOp = cast<LinalgOp>(op);
+
   // Expect at least one shaped operand.
   // This means an op that constructs a tensor out of indices cannot be a
   // LinalgOp at the moment. For now this will have to be a special op until we
   // have output shape operands that are not tensors.
   auto nShapedOperands = linalgOp.getNumShapedOperands();
   if (nShapedOperands == 0)
     return linalgOp.emitOpError("expected at least 1 Shaped operand");
   if (failed(OpTrait::impl::verifyAtLeastNOperands(op, nShapedOperands)))
if (std::get<0>(it).getElementType() != std::get<1>(it).getType())
       return op->emitError("expected type of bb argument #")
              << (idx + numBBIvs) << " (" << std::get<1>(it).getType() << ")"
              << " to match element type of corresponding shaped operand ("
              << std::get<0>(it).getElementType() << ")";
     ++idx;
   }
 
   // Check if given shapes match to inferred shapes.
-  Optional<SmallVector<int64_t, 4>> loopRanges = linalgOp.getStaticLoopRanges();
-  if (!loopRanges)
+  Optional<SmallVector<int64_t, 4>> endLoopRangeValues =
+      linalgOp.getStaticLoopRanges();
+  if (!endLoopRangeValues)
     return linalgOp.emitError("unable to find loop range for operation");
+  SmallVector<int64_t, 4> startLoopRangeValues((*endLoopRangeValues).size(), 0);
 
   // Verify only static cases since we can't get exact dimension sizes and loop
   // ranges for dynamic cases in this stage.
-  if (llvm::none_of(*loopRanges, [](int64_t &range) {
+  if (llvm::none_of(*endLoopRangeValues, [](int64_t &range) {
         return range == ShapedType::kDynamicSize;
       })) {
-    for (int64_t &range : *loopRanges)
+    for (int64_t &range : *endLoopRangeValues)
       range -= 1;
     for (const auto &en : llvm::enumerate(linalgOp.getShapedOperandTypes())) {
-      auto indices = indexingMaps[en.index()].compose(*loopRanges);
+      auto firstIndices =
+          indexingMaps[en.index()].compose(startLoopRangeValues);
+      auto lastIndices = indexingMaps[en.index()].compose(*endLoopRangeValues);
       for (auto j : llvm::seq<unsigned>(0, en.value().getRank())) {
 
-        // Ignore dynamic dimension or the case that the inferred last index is
-        // zero. The index is increasing or decreasing in Linalg, for example,
-        // the last index should be `0` or `size-1`. We only check the cases
-        // that are non-zero because most of cases are increasing and it is too
-        // expensive to find the shape of decreasing cases.
-        if (en.value().isDynamicDim(j) || indices[j] == 0)
+        // Ignore dynamic dimension
+        if (en.value().isDynamicDim(j))
           continue;
 
-        // The size of shaped operands and inferred dimension size should be
-        // same. But, for now we check if the inferred sizes are in boundary of
-        // shaped operands' size or not in case that Affine Expressions are
-        // complicated such as d0 * 3 + d1 since it is not easy to handle the
-        // issues.
-        auto inferredSize = indices[j] + 1;
+        // The first index or last index should be the maximum or the minimum in
+        // the inferred index ranges since the range is increasing or
+        // decreasing. The size of dimensions of shaped operands and the maximum
+        // value + 1 in the inferred range should be the same. But, for now we
+        // check if the inferred ranges are in boundary of shaped operands' size
+        // or not in case that Affine Expressions are complicated such as d0 * 3
+        // + d1 since it is not easy to handle the issues.
         auto shapedDimSize = en.value().getDimSize(j);
+        // if the dimensionsize is 0, then index should be -1, not 0.
+        if (shapedDimSize == 0)
+          firstIndices[j] = -1;
+        auto inferredDimSize = std::max(firstIndices[j], lastIndices[j]) + 1;
+        if (shapedDimSize > 0 &&
+            std::min(firstIndices[j], lastIndices[j]) < 0) {
+          std::string mapStr;
+          {
+            llvm::raw_string_ostream os(mapStr);
+            os << indexingMaps[en.index()];
+          }
+          return linalgOp.emitError(
+                     "unexpected result less than 0 at expression #")
+                 << j << " in affineMap\n"
+                 << mapStr;
+        }
         if (indexingMaps[en.index()].getResult(j).dyn_cast<AffineDimExpr>()) {
-          if (inferredSize != shapedDimSize) {
+          if (inferredDimSize != shapedDimSize) {
             return linalgOp.emitOpError("inferred shaped operand #")
                    << en.index() << " has shape's dimension #" << j << " to be "
-                   << inferredSize << ", but found " << shapedDimSize;
+                   << inferredDimSize << ", but found " << shapedDimSize;
           }
         } else {
-          if (inferredSize > shapedDimSize) {
+          if (inferredDimSize > shapedDimSize) {
             return linalgOp.emitOpError("inferred shaped operand #")
                    << en.index() << " has shape's dimension #" << j
-                   << " to be greater than or equal to " << inferredSize
+                   << " to be greater than or equal to " << inferredDimSize
                    << ", but found " << shapedDimSize;
           }
         }
       }
     }
   }
 
   return success();
 }

mlir/test/Dialect/Linalg/invalid.mlir

 
 func @yield_parent(%arg0: memref<?xf32, affine_map<(i)[off]->(off + i)>>) {
   // expected-error @+1 {{op expected parent op with LinalgOp interface}}
   linalg.yield %arg0: memref<?xf32, affine_map<(i)[off]->(off + i)>>
 }
 
 // -----
 
-func @index_parent() {
-  // expected-error @+1 {{op expected parent op with LinalgOp interface}}
-  linalg.index 0 : index
-}
-
-// -----
-
-func @index_dim_lower_than_number_of_loops(%arg0: memref<f32>) {
-  // expected-error @+6 {{op expected dim (2) to be lower than the number of loops (0) of the enclosing LinalgOp}}
-  linalg.generic {
-      indexing_maps =  [ affine_map<() -> ()> ],
-      iterator_types = []}
-      outs(%arg0 : memref<f32>) {
-    ^bb(%0: f32):
-      linalg.index 2 : index
-      linalg.yield %0 : f32
-  }
-}
-
-// -----
-
-func @index_dim_negative(%arg0: memref<f32>) {
-  // expected-error @+6 {{op attribute 'dim' failed to satisfy constraint: 64-bit signless integer attribute whose minimum value is 0}}
-  linalg.generic {
-      indexing_maps =  [ affine_map<() -> ()> ],
-      iterator_types = []}
-      outs(%arg0 : memref<f32>) {
-    ^bb(%0: f32):
-      linalg.index -1 : index
-      linalg.yield %0 : f32
-  }
-}
-
-// -----
-
 func @generic_no_region(%arg0: memref<f32>) {
   // expected-error @+5 {{expected '{' to begin a region}}
   linalg.generic {
     indexing_maps =  [ affine_map<() -> (0)> ],
     iterator_types = []
   } ins(%arg0 : memref<f32>)
 }
 
linalg.conv_2d_input_nhwc_filter_hwcf
     { dilations = dense<1> : tensor<2xi64>, strides = dense<1> : tensor<2xi64>}
     ins(%input, %filter : memref<1x3x4x2xf32>, memref<3x2x2x1xf32>)
     outs(%output : memref<1x2x3x1xf32>)
   return
 }
 
 // -----
 
-#map0 = affine_map<(d0) -> (24, -d0 + 192)>
-#map1 = affine_map<(d0, d1)[s0] -> (d0 * 192 + s0 + d1)>
-#map2 = affine_map<(d0) -> (16, -d0 + 192)>
-
-func private @foo(%A: memref<192x192xf32>, %B: memref<192x192xf32>,
-                  %C: memref<192x192xf32>) -> ()
-
-func @tiled_loop_incorrent_num_yield_operands(%A: memref<192x192xf32>,
-    %B: memref<192x192xf32>, %C: memref<192x192xf32>,
-    %C_tensor: tensor<192x192xf32>) {
-  %c24 = constant 24 : index
-  %c0 = constant 0 : index
-  %c192 = constant 192 : index
-  %0 = linalg.tiled_loop (%i, %j) = (%c0, %c0) to (%c192, %c192)
-      step (%c24, %c24)
-      ins (%A, %B: memref<192x192xf32>, memref<192x192xf32>)
-      outs (%C_tensor, %C :tensor<192x192xf32>, memref<192x192xf32>) {
-        call @foo(%A, %B, %C)
-          : (memref<192x192xf32>, memref<192x192xf32>, memref<192x192xf32>)-> ()
-    // expected-error @+1 {{expected number of tensor output args = 1 to match the number of yield operands = 0}}
-    linalg.yield
-  }
-  return
+#attrs = {
+  indexing_maps = [
+    affine_map<(i, j, k) -> (1-i, k)>,
+    affine_map<(i, j, k) -> (k, j)>,
+    affine_map<(i, j, k) -> (i, j)>
+  ],
+  iterator_types = ["parallel", "parallel", "reduction"]
 }
 
-// -----
-
-#map0 = affine_map<(d0) -> (24, -d0 + 192)>
-#map1 = affine_map<(d0, d1)[s0] -> (d0 * 192 + s0 + d1)>
-#map2 = affine_map<(d0) -> (16, -d0 + 192)>
-
-func private @foo(%A: memref<192x192xf32>, %B: memref<192x192xf32>,
-                  %C: memref<192x192xf32>) -> tensor<f32>
-
-func @tiled_loop_incorrent_yield_operand_type(%A: memref<192x192xf32>,
-    %B: memref<192x192xf32>, %C: memref<192x192xf32>,
-    %C_tensor: tensor<192x192xf32>) {
-  %c24 = constant 24 : index
-  %c0 = constant 0 : index
-  %c192 = constant 192 : index
-  %0 = linalg.tiled_loop (%i, %j) = (%c0, %c0) to (%c192, %c192)
-      step (%c24, %c24)
-      ins (%A, %B: memref<192x192xf32>, memref<192x192xf32>)
-      outs (%C_tensor, %C :tensor<192x192xf32>, memref<192x192xf32>) {
-        %1 = call @foo(%A, %B, %C)
-          : (memref<192x192xf32>, memref<192x192xf32>, memref<192x192xf32>)-> tensor<f32>
-    // expected-error @+1 {{expected yield operand 0 with type = 'tensor<f32>' to match output arg type = 'tensor<192x192xf32>}}
-    linalg.yield %1 : tensor<f32>
-  }
-  return
-}
+func @example(%A: memref<3x5xf32>, %B: memref<5x2xf32>, %C: memref<3x2xf32>) {
+  // expected-error @+1 {{unexpected result less than 0 at expression #0 in affineMap}}
+  linalg.generic #attrs ins(%A, %B: memref<3x5xf32>, memref<5x2xf32>) outs(%C: memref<3x2xf32>) {
+    ^bb0(%a: f32, %b: f32, %c: f32):
+      %d = mulf %a, %b : f32
+      %e = addf %c, %d : f32
+    linalg.yield %e : f32
+  } 
 
-// -----
-
-#map0 = affine_map<(d0) -> (24, -d0 + 192)>
-#map1 = affine_map<(d0, d1)[s0] -> (d0 * 192 + s0 + d1)>
-#map2 = affine_map<(d0) -> (16, -d0 + 192)>
-
-func private @foo(%A: memref<192x192xf32>, %B: memref<192x192xf32>,
-                  %C: memref<192x192xf32>) -> ()
-
-func @tiled_loop_incorrent_iterator_types_count(%A: memref<192x192xf32>,
-    %B: memref<192x192xf32>, %C: memref<192x192xf32>,
-    %C_tensor: tensor<192x192xf32>) {
-  %c24 = constant 24 : index
-  %c0 = constant 0 : index
-  %c192 = constant 192 : index
-  // expected-error @+1 {{expected iterator types array attribute size = 1 to match the number of loops = 2}}
-  %0 = "linalg.tiled_loop"(%c0, %c0, %c192, %c192, %c24, %c24, %A, %B, %C_tensor, %C) ( {
-    ^bb0(%arg4: index, %arg5: index):  // no predecessors
-      call @foo(%A, %B, %C)
-          : (memref<192x192xf32>, memref<192x192xf32>, memref<192x192xf32>)-> ()
-      linalg.yield %C_tensor : tensor<192x192xf32>
-    }) {
-      iterator_types = ["parallel"],
-      operand_segment_sizes = dense<2> : vector<5xi32>
-    } : (index, index, index, index, index, index, memref<192x192xf32>,
-      memref<192x192xf32>, tensor<192x192xf32>, memref<192x192xf32>
-    ) -> tensor<192x192xf32>
-  return
+  return
 }