This is an archive of the discontinued LLVM Phabricator instance.

Added static verification for Linalg Ops.
ClosedPublic

Authored by inho9606 on Mar 10 2021, 9:00 PM.

Details

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

Diff Detail

Event Timeline

inho9606 created this revision.Mar 10 2021, 9:00 PM
inho9606 requested review of this revision.Mar 10 2021, 9:00 PM
hanchung requested changes to this revision.Mar 11 2021, 2:49 AM
hanchung added inline comments.
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

This revision now requires changes to proceed.Mar 11 2021, 2:49 AM

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

mravishankar requested changes to this revision.Mar 11 2021, 12:00 PM

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.

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 added inline comments.Mar 11 2021, 12:51 PM
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 added inline comments.Mar 11 2021, 6:29 PM
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..

  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 added inline comments.Mar 11 2021, 11:29 PM
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 added inline comments.Mar 12 2021, 12:57 AM
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 requested changes to this revision.Mar 12 2021, 4:50 AM

@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.

  1. 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.

This revision now requires changes to proceed.Mar 12 2021, 4:50 AM
inho9606 added inline comments.Mar 12 2021, 7:45 AM
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 added inline comments.Mar 12 2021, 7:57 AM
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 added inline comments.Mar 12 2021, 10:59 AM
mlir/test/Dialect/Linalg/reshape_linearization_fusion.mlir
171–173

Oops, I meant to replace permultation with permutation.

  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

  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

  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 requested changes to this revision.Mar 16 2021, 5:39 AM

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.

This revision now requires changes to proceed.Mar 16 2021, 5:39 AM
  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.

  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

  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 requested changes to this revision.Mar 18 2021, 9:58 AM
hanchung added inline comments.
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.

This revision now requires changes to proceed.Mar 18 2021, 9:58 AM
  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 added inline comments.Mar 18 2021, 9:14 PM
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 requested changes to this revision.Mar 18 2021, 11:01 PM
hanchung added inline comments.
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.

This revision now requires changes to proceed.Mar 18 2021, 11:01 PM
hanchung added inline comments.Mar 18 2021, 11:05 PM
mlir/lib/Dialect/Linalg/IR/LinalgInterfaces.cpp
447–451

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

  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 added inline comments.Mar 19 2021, 2:08 AM
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?

  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 requested changes to this revision.Mar 23 2021, 11:12 AM
hanchung added inline comments.
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
}
  1. 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.

This revision now requires changes to proceed.Mar 23 2021, 11:12 AM
  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 added inline comments.Mar 23 2021, 8:50 PM
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 requested changes to this revision.Mar 25 2021, 12:06 AM
hanchung added inline comments.
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.

This revision now requires changes to proceed.Mar 25 2021, 12:06 AM
  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 added inline comments.Mar 25 2021, 3:53 AM
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!

  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 added a comment.EditedMar 25 2021, 6:05 AM

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?

  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

  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 accepted this revision.Mar 29 2021, 5:00 AM

Thanks!

This revision was not accepted when it landed; it landed in state Needs Review.Mar 30 2021, 7:11 AM
This revision was automatically updated to reflect the committed changes.