Added static verification for Linalg Ops.

[• inho9606]

Summary

This verification is to check if the indices for static shaped operands on linalgOps access out of bound memory or not. For dynamic shaped operands, we would be able to check it on runtime stage.
Found 3 memory violation testcases, and modified them

[hanchung]

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

435

Check the return value

436

The LLVM style is for (unsigned i = 0, e = ...; i < e; ...)

439–440

This can be getShapedOperandTypes()[i].
I think it is better to have a getShapedOperandType(i), could you add the interface method?

443

You should check if there are any symbols before calling compose method. Otherwise, it will hit an assertion in the method.

445

Why check with >=? Can we check if they are the same, ie with ==? You can know the exact shape if you have loop boundary.

mlir/test/Dialect/Linalg/reshape_linearization_fusion.mlir

170–173

Below is more straightforward to me:

#map2 = affine_map<(d0, d1, d2) -> (d2, d0, d1)>
#map3 = affine_map<(d0, d1, d2) -> (d0, d1, d2)>

Does it work?

171–173

please help fix this typo since you touch this section.

s/permultation/permutation

[hanchung]

@aartbik could you help check if the change in sparse_nd.mlir is correct?

[mravishankar]

Probably need a test that fails as well and verify the error message. You can use -verify-diagnostics on the command line, and match the error using // expected-error . See other tests that have this.

[hanchung]

In D98390#2620390, @mravishankar wrote:

Probably need a test that fails as well and verify the error message. You can use -verify-diagnostics on the command line, and match the error using // expected-error . See other tests that have this.

Yes, totally agree! Please add a test to test/Dialect/Linalg/invalid.mlir.

[mehdi_amini]

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

436

Alternatively, for (int i : llvm::seq<int>(0, (*loopRanges).size())

But even better any time you don't need the index:

for (int64_t &range : *loopRanges) range -= 1;

Also good to know the alternative when you need the index but iterate over a range:

for (auto &indexedRange : llvm::enumerate(*loopRanges)) {
    // indexedRange.index() for the index
   // indexedRange.value() for the value

[• inho9606]

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

436

Wow It's very helpful! Thanks for sharing the tips

443

I think it was already checked in line 327 when constructing indexingMaps,, isn't it?

445

Could you give me more hint? I thought we should check the upper bound of loops and the size of shaped operands since we have to detect access out of boundary. Or do you mean the size and loop range should be same?

mlir/test/Dialect/Linalg/reshape_linearization_fusion.mlir

170–173

With your suggestion, the indices are less than the sizes, but it is not match. I mean 3x35 shape matches 3x18 loop range, and 5x7x3 shape matches 4x2x2 loop range..
Refering to the case of reshaping 3x35 to 5x3x7 below, map2 matches input shape and map3 matches output. In fact, if I modify map2, then it does not work.. E.G., 3x35 -> 3x44..

[• inho9606]

1. Updating D98390: Added static verification for Linalg Ops. #
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 small code styles

[hanchung]

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

445

Yes, they should be the same. It does not make sense to me if one is larger. Otherwise the behavior is undefined.

Say that both affine_map is (d0) -> (d0). One shape is [10], and another is [20]. It can raise the issue or not raise issue based on how you infer the shape. If you get the upper bound from the first operand, then the check passes. If you get the upper bound from the second operand, then the check fails. Does it make sense?

mlir/test/Dialect/Linalg/reshape_linearization_fusion.mlir

170–173

I do not understand what the issue is here. d0, d1, d2 will map to three numbers. This is just like what symbol maps to what value. I don't see the difference if you swap d1 and d2.

I actually don't understand what you are saying like 3x18 loop range and 4x2x2 loop range. Could you explain more? What is the IR if you go with the suggestion?

[• inho9606]

mlir/test/Dialect/Linalg/reshape_linearization_fusion.mlir

170–173

Okay, I removed 'range -=1 statement' according to your comment above (not committed yet), and printed out each rank's size of the shapes and loop ranges. Here is IR with the suggestion.

inhoseo@inho:~/llvm-project/build/bin$ ./mlir-opt linalg_test.mlir -linalg-fold-reshape-ops-by-linearization -verify-diagnostics
shaped 3 index 3
shaped 5 index 5
shaped 7 index 7
shaped 5 index 5
shaped 7 index 7
shaped 3 index 3
shaped 3 index 3
shaped 35 index 26
shaped 5 index 5
shaped 7 index 3
shaped 3 index 3
#map0 = affine_map<(d0, d1, d2) -> (d1, d0 + d2 * 7)>
#map1 = affine_map<(d0, d1, d2) -> (d0, d1, d2)>
module {

func @generic_op_120_permultation_reshape_producer_fusion(%arg0: tensor<3x35xf32>) -> tensor<5x7x3xf32> {
  %0 = linalg.init_tensor [5, 7, 3] : tensor<5x7x3xf32>
  %1 = linalg.generic {indexing_maps = [#map0, #map1], iterator_types = ["parallel", "parallel", "parallel"]} ins(%arg0 : tensor<3x35xf32>) outs(%0 : tensor<5x7x3xf32>) {
  ^bb0(%arg1: f32, %arg2: f32):  // no predecessors
    linalg.yield %arg1 : f32
  } -> tensor<5x7x3xf32>
  return %1 : tensor<5x7x3xf32>
}

}

-convert-linalg-to-loops does not work with other options here..

[hanchung]

@inho9606, please add invalid ops to test/Dialect/Linalg/invalid.mlir

mlir/test/Dialect/Linalg/reshape_linearization_fusion.mlir

170–173

Okay, I removed 'range -=1 statement' according to your comment above (not committed yet), and printed out each rank's size of the shapes and loop ranges. Here is IR with the suggestion.

I don't get the reason to remove 'range -=` statement'. But this seems unrelated, I will take a look once you upload the patch.

---

inhoseo@inho:~/llvm-project/build/bin$ ./mlir-opt linalg_test.mlir -linalg-fold-reshape-ops-by-linearization -verify-diagnostics
shaped 3 index 3
shaped 5 index 5
shaped 7 index 7
shaped 5 index 5
shaped 7 index 7
shaped 3 index 3
shaped 3 index 3
shaped 35 index 26
shaped 5 index 5
shaped 7 index 3
shaped 3 index 3
#map0 = affine_map<(d0, d1, d2) -> (d1, d0 + d2 * 7)>
#map1 = affine_map<(d0, d1, d2) -> (d0, d1, d2)>
module {

func @generic_op_120_permultation_reshape_producer_fusion(%arg0: tensor<3x35xf32>) -> tensor<5x7x3xf32> {
  %0 = linalg.init_tensor [5, 7, 3] : tensor<5x7x3xf32>
  %1 = linalg.generic {indexing_maps = [#map0, #map1], iterator_types = ["parallel", "parallel", "parallel"]} ins(%arg0 : tensor<3x35xf32>) outs(%0 : tensor<5x7x3xf32>) {
  ^bb0(%arg1: f32, %arg2: f32):  // no predecessors
    linalg.yield %arg1 : f32
  } -> tensor<5x7x3xf32>
  return %1 : tensor<5x7x3xf32>
}

}

-convert-linalg-to-loops does not work with other options here..

I think there are two issues.

1. The input IR is not valid, if I read correctly.

#map2 = affine_map<(d0, d1, d2) -> (d1, d2, d0)>
#map3 = affine_map<(d0, d1, d2) -> (d0, d1, d2)>

  %2 = linalg.generic
    {indexing_maps = [#map2, #map3],
     iterator_types = ["parallel", "parallel", "parallel"]}
    ins(%0 : tensor<3x5x7xf32>) outs(%1 : tensor<5x7x3xf32>) {
    ^bb0(%arg2: f32, %arg3: f32):  // no predecessors
      linalg.yield %arg2 : f32
    } -> tensor<5x7x3xf32>

The indexing maps for the generic op should be

#map2 = affine_map<(d0, d1, d2) -> (d2, d0, d1)>
#map3 = affine_map<(d0, d1, d2) -> (d0, d1, d2)>

The indexing maps that you provide is also correct. This is just the order of loops problem.

2. There is probably a bug in the pass.

The indexing maps in the output are

#map0 = affine_map<(d0, d1, d2) -> (d1, d0 + d2 * 7)>
#map1 = affine_map<(d0, d1, d2) -> (d0, d1, d2)>

%1 = linalg.generic {indexing_maps = [#map0, #map1], iterator_types = ["parallel", "parallel", "parallel"]} ins(%arg0 : tensor<3x35xf32>) outs(%0 : tensor<5x7x3xf32>) {
  ^bb0(%arg1: f32, %arg2: f32):  // no predecessors
    linalg.yield %arg1 : f32
  } -> tensor<5x7x3xf32>

while I think they should be

#map0 = affine_map<(d0, d1, d2) -> (d2, d1 + d0 * 7)>
#map1 = affine_map<(d0, d1, d2) -> (d0, d1, d2)>

With your fix, you are hiding the issue in (2). I think we can go with your fix. Then Mahesh or I will fix the bug and add one more test for it.

@mravishankar fyi, the input of the test case was wrong I think.

[• inho9606]

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

445

Yes, if d0 matched (10) already and d0 tries to match (20), then it should fail.
Here my understand is that elements of indices and elements of shapedOperand.getDimSize() are 1:1 match. So indices[j] accesses shapedOperand.getDimSize(j). And usually the valid range of indices is from 0 to size-1. That's why I thought we could pass if indices[j] < shapedOperand.getDimSize(j).
+ Yes you are right, we still need 'range -= 1' statement. It is to get the exact indices by compose method. So it is not related to this discussion. I misunderstood..

mlir/test/Dialect/Linalg/reshape_linearization_fusion.mlir

171–173

Could you give me more detail what you meant by 's/permultation/permutation'?

[• inho9606]

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

445

Yes, if d0 matched (10) already and d0 tries to match (20), then it should fail.
Here my understand is that elements of indices and elements of shapedOperand.getDimSize() are 1:1 match. So indices[j] accesses shapedOperand.getDimSize(j). And usually the valid range of indices is from 0 to size-1. That's why I thought we could pass if indices[j] < shapedOperand.getDimSize(j).
+ Yes you are right, we still need 'range -= 1' statement. It is to get the exact indices by compose method. So it is not related to the discussion about the test. I misunderstood..

[hanchung]

mlir/test/Dialect/Linalg/reshape_linearization_fusion.mlir

171–173

Oops, I meant to replace permultation with permutation.

[• inho9606]

1. Updating D98390: Added static verification for Linalg Ops. #
2. Enter a brief description of the changes included in this update.
3. The first line is used as subject, next lines as comment.

Added invalid op in invalid.mlir

[• inho9606]

1. Updating D98390: Added static verification for Linalg Ops. #
2. Enter a brief description of the changes included in this update.
3. The first line is used as subject, next lines as comment.

Updated verification condition, and fixed some more testcases

[• inho9606]

1. Updating D98390: Added static verification for Linalg Ops. #
2. Enter a brief description of the changes included in this update.
3. The first line is used as subject, next lines as comment.

Removed comments and changed variable names

[hanchung]

Inho and I had an offline discussion today, and we found that this doesn't work in some cases. E.g., if there is an affine_map is affine_map<(i) -> (10 - i)>. I will wait for Inho's fix and review it later.

[• inho9606]

1. Updating D98390: Added static verification for Linalg Ops. #
2. Enter a brief description of the changes included in this update.
3. The first line is used as subject, next lines as comment.

Added ignoring case that has zero as it's laast inferred accessing index.

[• inho9606]

1. Updating D98390: Added static verification for Linalg Ops. #
2. Enter a brief description of the changes included in this update.
3. The first line is used as subject, next lines as comment.

Applied clang-format to LinalgInterfaces.cpp

[• inho9606]

1. Updating D98390: Added static verification for Linalg Ops. #
2. Enter a brief description of the changes included in this update.
3. The first line is used as subject, next lines as comment.

Applied rebase to top

[hanchung]

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

435

nit: rename it to hasDynamicRange?

439–445

The logic is mixed in this loop. You can use llvm::any_of and it's better to have a comment on why you subtract loop ranges. E.g.,

bool hasDynamicRange = llvm::any_of(...)
for (auto ...) range -= 1;

The second line can even put to the body of if-statement. And in this case, we can write something like:

if (llvm::any_of(...)) {
  for (auto ...) range -= 1;
  ...
}

446

Add a comment on why? We actually can verify the below snippet right?

linalg.matmul ins(%A, %B: memref<2x?xf32>, memref<?x4xf32>)
                     outs(%C: memref<2x4xf32>)

Is the reason that this is too expensive to check?

447–451

Let's follow LLVM style, use llvm::enumerate(inalgOp.getShapedOperandTypes()).

452

style nit:

for (auto j : llvm:seq<unsigned>(0, shapedOperand.getRank()))

453–456

I feel we should have a more detailed description because this is not well-defined yet. How about:

Ignore the case that the inferred last index is zero. The indexing is either increasing or decreasing in Linalg, ie, the last index will 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.

459–465

How about:

inferred XXX shaped operand shape's dimension XXX to be XXX but found XXX

This looks shorter and cleaner to me.

[• inho9606]

1. Updating D98390: Added static verification for Linalg Ops. #
2. Enter a brief description of the changes included in this update.
3. The first line is used as subject, next lines as comment.

Updated some comments and code styles

[• inho9606]

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

439–445

Thanks for the useful feature. I think none-of would be more clear to read, so used it instead of any_of. But please let me know if I made something wrong please since it was my first time to use this.

447–451

I think we still need index i to compare loop ranges and shaped sizes, and to indicate which operand has an error in debug messages. So I just made this line like what you suggested for index j below instead.

[hanchung]

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

447–451

llvm::enumerate will return the index and the object.

for (auto &en : llvm::enumerate(linalgOp.getShapedOperandTypes())) {
   // en.index() for the index
   // en.value() for the value

In this case en.value() will be i.

455

461–462

It is weird to me that start with "Detected Invalid shaped operand.". I don't see other verify methods have this kind of things. Can we delete it?

And they are supposed to be sentence fragments. Errors reported via emitError or emitOpError should start with lower case.

[hanchung]

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

447–451

typo... I meant en.index will be i.

[• inho9606]

1. Updating D98390: Added static verification for Linalg Ops. #
2. Enter a brief description of the changes included in this update.
3. The first line is used as subject, next lines as comment.

Applied LLVM style and fixed comments

[• inho9606]

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

447–451

Oh I didn't know if it has en.index(). thanks!

455

Sorry, I didn't catch what you wanted to mean because my screen reader does not recognize your comment. I think it might be because of starting with //.. Could you add the comment again?

[• inho9606]

1. Updating D98390: Added static verification for Linalg Ops. #
2. Enter a brief description of the changes included in this update.
3. The first line is used as subject, next lines as comment.

Check complicated cases; pass if indices are in-of-bound of shapes.

[hanchung]

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

446

I don't think the comment explains my example. You will skip the check when some dims are dynamic and some dims are static. My example can be checked. Is there a reason for not checking it?

446

We don't intend to modify any values right? Let's use const auto &en.

450

Let's use auto j. LLVM style says that use auto with initializers like cast<Foo>(...) or other places where the type is already obvious from the context. llvm::seq already spells the type.

https://llvm.org/docs/CodingStandards.html#use-auto-type-deduction-to-make-code-more-readable

452

type: Replace inffered with inferred.

455

I actually don't know the English of this symbol. It is probably a grave accent. You can type it with the key above Tab key. It is also on the left hand side of 1.

461–466

The walk is not needed here. I think it is a tree-based structure. If the kind of an Affine expression is DimId, it won't have any children. If it is not, it is "complicated" in this case. There are couple ways to do it:

1. you can try to dyn_cast it to AffineDimExpr e.g.,

if (dyn_cast<AffineDimExpr>(expr)) {
  // not complicated case
} else {
  // complicated case
}

2. Just check if the kind is a DimID by expr.getKind().isa<>(mlir::AffineExprKind::DimId).

The first way is more common I think.

467–481

Couple issues.

1. 0-base is more common. Let's not go with 1-base.
2. Add comments. People won't understand why checking it this way.
3. It's better to have a variable for indices[j] + 1, maybe inferredSize?

mlir/test/Dialect/Linalg/invalid.mlir

707–714

Add one more invalid test case for another case.

[• inho9606]

1. Updating D98390: Added static verification for Linalg Ops. #
2. Enter a brief description of the changes included in this update.
3. The first line is used as subject, next lines as comment.

Updated code style and comments..
Added an invalid testcase.

[• inho9606]

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

455

Oh grabe is correct! Actually the screen reader says '>' as 'grater than', and says '`' as grabe. It is similar, so my ears thought of them as same things.. LOL

[hanchung]

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

465–479

There are four en.value().getDimSize(j), maybe have a variable for it?

473–476

The error message is not reasonable, please fix it. should it be greater than?

mlir/test/Dialect/Linalg/invalid.mlir

719

This error message is weird.

xxx be less than or equal to 4 but found 3. Doesn't 3 less than 4?

mlir/test/Dialect/Linalg/tile-indexed-generic.mlir

86 ↗

(On Diff #332858)

accidental change? please revert it.

[• inho9606]

1. Updating D98390: Added static verification for Linalg Ops. #
2. Enter a brief description of the changes included in this update.
3. The first line is used as subject, next lines as comment.

Fixed wierd comment.. and fixed minor style

[• inho9606]

mlir/test/Dialect/Linalg/invalid.mlir

719

Oops it is definitely my fault.. Thanks

mlir/test/Dialect/Linalg/tile-indexed-generic.mlir

86 ↗

(On Diff #332858)

Ah,, I often use tab key to explore the screen, but sometimes it is typed as character and I miss it easily.. I need to be more careful. Anyway thanks for letting me know!

[• inho9606]

1. Updating D98390: Added static verification for Linalg Ops. #
2. Enter a brief description of the changes included in this update.
3. The first line is used as subject, next lines as comment.

Fixed clang-format issue

[hanchung]

It looks like there is a failure in tile-and-fuse-tensors.mlir. Could you check the file/test, so we can make bots happy?

[• inho9606]

1. Updating D98390: Added static verification for Linalg Ops. #
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 the patch to the top of tree, and fixed one test in tile-and-fuse-tensors

[• inho9606]

1. Updating D98390: Added static verification for Linalg Ops. #
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 think this version is more reasonable comparing to other cases

[hanchung]

Thanks!

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

for (auto it : llvm::zip(linalgOp.getShapedOperandTypes(),
     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 shapes are valid
+  Optional<SmallVector<int64_t, 4>> loopRanges = linalgOp.getStaticLoopRanges();
+  if (!loopRanges)
+    return linalgOp.emitError("unable to find loop range for operation");
+  for (int64_t &range : *loopRanges)
+    range -= 1;
+  for (unsigned i = 0; i < nShapedOperands; i++) {
+    auto shapedOperand = linalgOp.getShapedOperandTypes()[i];
+    if (!shapedOperand.hasStaticShape())
+      continue;
+    auto indices = indexingMaps[i].compose(*loopRanges);
+    for (unsigned j = 0; j < shapedOperand.getRank(); j++) {
+      if (indices[j] >= shapedOperand.getDimSize(j)) {
+        return linalgOp.emitOpError("Out-of-bound memory access in operand #")
+               << i + 1 << ". The range of it's rank #" << j + 1
+               << " is from 0 through " << shapedOperand.getDimSize(j) - 1
+               << ", but the operand tries to access index #" << indices[j];
+      }
+    }
+  }
+
   return success();
 }

mlir/test/Dialect/Linalg/generalize-named-ops.mlir

 // RUN: mlir-opt %s -split-input-file -linalg-generalize-named-ops | FileCheck %s
 
-func @generalize_conv(%input : memref<1x225x225x3xf32>, %filter: memref<3x3x3x32xf32>, %output: memref<1x112x112x32xf32>) {
-  linalg.conv(%filter, %input, %output) {dilations = [2, 3], strides = [4, 5]} : memref<3x3x3x32xf32>, memref<1x225x225x3xf32>, memref<1x112x112x32xf32>
+func @generalize_conv(%input : memref<1x449x562x3xf32>, %filter: memref<3x3x3x32xf32>, %output: memref<1x112x112x32xf32>) {
+  linalg.conv(%filter, %input, %output) {dilations = [2, 3], strides = [4, 5]} : memref<3x3x3x32xf32>, memref<1x449x562x3xf32>, memref<1x112x112x32xf32>
   return
 }
 
 // CHECK: #[[FILTER_MAP:.+]] = affine_map<(d0, d1, d2, d3, d4, d5, d6) -> (d5, d6, d4, d3)>
 // CHECK:  #[[INPUT_MAP:.+]] = affine_map<(d0, d1, d2, d3, d4, d5, d6) -> (d0, d1 * 4 + d5 * 2, d2 * 5 + d6 * 3, d4)>
 // CHECK: #[[OUTPUT_MAP:.+]] = affine_map<(d0, d1, d2, d3, d4, d5, d6) -> (d0, d1, d2, d3)>
 
 // CHECK: func @generalize_conv
-// CHECK-SAME:  %[[INPUT:.+]]: memref<1x225x225x3xf32>
+// CHECK-SAME:  %[[INPUT:.+]]: memref<1x449x562x3xf32>
 // CHECK-SAME: %[[FILTER:.+]]: memref<3x3x3x32xf32>
 // CHECK-SAME: %[[OUTPUT:.+]]: memref<1x112x112x32xf32>
 
 // CHECK: linalg.generic
 // CHECK-SAME: indexing_maps = [#[[FILTER_MAP]], #[[INPUT_MAP]], #[[OUTPUT_MAP]]]
 // CHECK-SAME: iterator_types = ["parallel", "parallel", "parallel", "parallel", "reduction", "window", "window"]
 // CHECK-SAME:  ins(%[[FILTER]], %[[INPUT]]
 // CHECK-SAME: outs(%[[OUTPUT]]

mlir/test/Dialect/Linalg/invalid.mlir

 
 func @illegal_fill_tensor_with_memref_return
   (%arg0 : tensor<?x?xf32>, %arg1 : f32) -> memref<?x?xf32>
 {
   // expected-error @+1 {{expected type of operand #0 ('tensor<?x?xf32>') to match type of corresponding result ('memref<?x?xf32>')}}
   %0 = linalg.fill(%arg0, %arg1) : tensor<?x?xf32>, f32 -> memref<?x?xf32>
   return %0 : memref<?x?xf32>
 }
+
+// -----
+
+func @static_out_of_bound_access(%arg0: memref<2x4xf32>, %arg1: memref<3x4xf32>, %arg2: memref<2x4xf32>) {
+  // expected-error @+1 {{Out-of-bound memory access in operand #2. The range of it's rank #1 is from 0 through 2, but the operand tries to access index #3}}
+  linalg.matmul ins(%arg0, %arg1 : memref<2x4xf32>, memref<3x4xf32>)
+                      outs(%arg2 :memref<2x4xf32>)
+  return
+}

mlir/test/Dialect/Linalg/reshape_linearization_fusion.mlir

 //       CHECK: func @generic_op_021_permultation_reshape_producer_fusion
 //   CHECK-NOT:   linalg.tensor_reshape
 //       CHECK:   linalg.generic
 //  CHECK-SAME:     indexing_maps = [#[[MAP0]], #[[MAP1]]]
 
 // -----
 
 #map0 = affine_map<(d0, d1, d2) -> (d0)>
 #map1 = affine_map<(d0, d1, d2) -> (d1, d2)>
-#map2 = affine_map<(d0, d1, d2) -> (d1, d2, d0)>
-#map3 = affine_map<(d0, d1, d2) -> (d0, d1, d2)>
-func @generic_op_120_permultation_reshape_producer_fusion(%arg0 : tensor<3x35xf32>) -> tensor<5x7x3xf32> {
+#map2 = affine_map<(d0, d1, d2) -> (d1, d0, d2)>
+#map3 = affine_map<(d0, d1, d2) -> (d0, d2, d1)>
+func @generic_op_120_permutation_reshape_producer_fusion(%arg0 : tensor<3x35xf32>) -> tensor<5x7x3xf32> {
   %0 = linalg.tensor_reshape %arg0 [#map0, #map1] : tensor<3x35xf32> into tensor<3x5x7xf32>
   %1 = linalg.init_tensor [5, 7, 3] : tensor<5x7x3xf32>
   %2 = linalg.generic
     {indexing_maps = [#map2, #map3],
      iterator_types = ["parallel", "parallel", "parallel"]}
     ins(%0 : tensor<3x5x7xf32>) outs(%1 : tensor<5x7x3xf32>) {
     ^bb0(%arg2: f32, %arg3: f32):  // no predecessors
       linalg.yield %arg2 : f32
     } -> tensor<5x7x3xf32>
     return %2 : tensor<5x7x3xf32>
 }
 
-//   CHECK-DAG: #[[MAP0:.+]] = affine_map<(d0, d1, d2) -> (d2, d0 * 7 + d1)>
-//   CHECK-DAG: #[[MAP1:.+]] = affine_map<(d0, d1, d2) -> (d0, d1, d2)>
-//       CHECK: func @generic_op_120_permultation_reshape_producer_fusion
+//   CHECK-DAG: #[[MAP0:.+]] = affine_map<(d0, d1, d2) -> (d1, d0 * 7 + d2)>
+//   CHECK-DAG: #[[MAP1:.+]] = affine_map<(d0, d1, d2) -> (d0, d2, d1)>
+//       CHECK: func @generic_op_120_permutation_reshape_producer_fusion
 //   CHECK-NOT:   linalg.tensor_reshape
 //       CHECK:   linalg.generic
 //  CHECK-SAME:     indexing_maps = [#[[MAP0]], #[[MAP1]]]
 
 // -----
 
 #map0 = affine_map<(d0, d1, d2) -> (d0)>
 #map1 = affine_map<(d0, d1, d2) -> (d1, d2)>

mlir/test/Dialect/Linalg/sparse_nd.mlir

#trait_mul = {
   ],
   iterator_types = ["parallel", "parallel", "parallel", "parallel",
                     "parallel", "parallel", "parallel", "parallel"],
   doc = "X(i,j,k,l,m,n,o,p) = A(i,j,k,l,m,n,o,p)  * B(p,o,n,m,l,k,j,i)"
 }
 
 // CHECK-LABEL:   func @mul(
 // CHECK-SAME:              %[[VAL_0:.*0]]: tensor<10x20x30x40x50x60x70x80xf32>,
-// CHECK-SAME:              %[[VAL_1:.*1]]: tensor<10x20x30x40x50x60x70x80xf32>,
+// CHECK-SAME:              %[[VAL_1:.*1]]: tensor<80x70x60x50x40x30x20x10xf32>,
 // CHECK-SAME:              %[[VAL_2:.*2]]: tensor<10x20x30x40x50x60x70x80xf32>) -> tensor<10x20x30x40x50x60x70x80xf32> {
 // CHECK:           %[[VAL_3:.*]] = constant 3 : index
 // CHECK:           %[[VAL_4:.*]] = constant 4 : index
 // CHECK:           %[[VAL_5:.*]] = constant 10 : index
 // CHECK:           %[[VAL_6:.*]] = constant 20 : index
 // CHECK:           %[[VAL_7:.*]] = constant 30 : index
 // CHECK:           %[[VAL_8:.*]] = constant 60 : index
 // CHECK:           %[[VAL_9:.*]] = constant 70 : index
 // CHECK:           %[[VAL_10:.*]] = constant 80 : index
 // CHECK:           %[[VAL_11:.*]] = constant 0 : index
 // CHECK:           %[[VAL_12:.*]] = constant 1 : index
 // CHECK:           %[[VAL_13:.*]] = tensor_to_memref %[[VAL_0]] : memref<10x20x30x40x50x60x70x80xf32>
-// CHECK:           %[[VAL_14:.*]] = linalg.sparse_pointers %[[VAL_1]], %[[VAL_3]] : tensor<10x20x30x40x50x60x70x80xf32> to memref<?xindex>
-// CHECK:           %[[VAL_15:.*]] = linalg.sparse_indices %[[VAL_1]], %[[VAL_3]] : tensor<10x20x30x40x50x60x70x80xf32> to memref<?xindex>
-// CHECK:           %[[VAL_16:.*]] = linalg.sparse_pointers %[[VAL_1]], %[[VAL_4]] : tensor<10x20x30x40x50x60x70x80xf32> to memref<?xindex>
-// CHECK:           %[[VAL_17:.*]] = linalg.sparse_indices %[[VAL_1]], %[[VAL_4]] : tensor<10x20x30x40x50x60x70x80xf32> to memref<?xindex>
-// CHECK:           %[[VAL_18:.*]] = linalg.sparse_values %[[VAL_1]] : tensor<10x20x30x40x50x60x70x80xf32> to memref<?xf32>
+// CHECK:           %[[VAL_14:.*]] = linalg.sparse_pointers %[[VAL_1]], %[[VAL_3]] : tensor<80x70x60x50x40x30x20x10xf32> to memref<?xindex>
+// CHECK:           %[[VAL_15:.*]] = linalg.sparse_indices %[[VAL_1]], %[[VAL_3]] : tensor<80x70x60x50x40x30x20x10xf32> to memref<?xindex>
+// CHECK:           %[[VAL_16:.*]] = linalg.sparse_pointers %[[VAL_1]], %[[VAL_4]] : tensor<80x70x60x50x40x30x20x10xf32> to memref<?xindex>
+// CHECK:           %[[VAL_17:.*]] = linalg.sparse_indices %[[VAL_1]], %[[VAL_4]] : tensor<80x70x60x50x40x30x20x10xf32> to memref<?xindex>
+// CHECK:           %[[VAL_18:.*]] = linalg.sparse_values %[[VAL_1]] : tensor<80x70x60x50x40x30x20x10xf32> to memref<?xf32>
 // CHECK:           %[[VAL_19:.*]] = tensor_to_memref %[[VAL_2]] : memref<10x20x30x40x50x60x70x80xf32>
 // CHECK:           %[[VAL_20:.*]] = alloc() : memref<10x20x30x40x50x60x70x80xf32>
 // CHECK:           linalg.copy(%[[VAL_19]], %[[VAL_20]]) : memref<10x20x30x40x50x60x70x80xf32>, memref<10x20x30x40x50x60x70x80xf32>
 // CHECK:           scf.for %[[VAL_21:.*]] = %[[VAL_11]] to %[[VAL_10]] step %[[VAL_12]] {
 // CHECK:             scf.for %[[VAL_22:.*]] = %[[VAL_11]] to %[[VAL_9]] step %[[VAL_12]] {
 // CHECK:               %[[VAL_23:.*]] = muli %[[VAL_21]], %[[VAL_9]] : index
 // CHECK:               %[[VAL_24:.*]] = addi %[[VAL_23]], %[[VAL_22]] : index
 // CHECK:               scf.for %[[VAL_25:.*]] = %[[VAL_11]] to %[[VAL_8]] step %[[VAL_12]] {

 // CHECK:                 }
 // CHECK:               }
 // CHECK:             }
 // CHECK:           }
 // CHECK:           %[[VAL_50:.*]] = tensor_load %[[VAL_20]] : memref<10x20x30x40x50x60x70x80xf32>
 // CHECK:           return %[[VAL_50]] : tensor<10x20x30x40x50x60x70x80xf32>
 // CHECK:         }
 func @mul(%arga: tensor<10x20x30x40x50x60x70x80xf32>,
-          %argb: tensor<10x20x30x40x50x60x70x80xf32>,
+          %argb: tensor<80x70x60x50x40x30x20x10xf32>,
           %argx: tensor<10x20x30x40x50x60x70x80xf32>)
         -> tensor<10x20x30x40x50x60x70x80xf32> {
   %0 = linalg.generic #trait_mul
     ins(%arga, %argb: tensor<10x20x30x40x50x60x70x80xf32>,
-                      tensor<10x20x30x40x50x60x70x80xf32>)
+                      tensor<80x70x60x50x40x30x20x10xf32>)
     outs(%argx: tensor<10x20x30x40x50x60x70x80xf32>) {
       ^bb(%a: f32, %b: f32, %x: f32):
         %0 = mulf %a, %b : f32
         linalg.yield %0 : f32
     }      -> tensor<10x20x30x40x50x60x70x80xf32>
   return %0 : tensor<10x20x30x40x50x60x70x80xf32>
 }