Page MenuHomePhabricator

The final update of static checker for linalg operations with the maximum and minimum indices

Authored by inho9606 on May 11 2021, 9:23 PM.



This version takes the real maximum and minimum indices of each affine expressions binding to each dims. So, we can check if the index ranges are valid or not.

Diff Detail

Event Timeline

inho9606 created this revision.May 11 2021, 9:23 PM
inho9606 requested review of this revision.May 11 2021, 9:23 PM

This version can check if the index ranges are in bound of the sizes of dimensions using getStaticMaximumIndex and getStaticMinimumIndex methods. The methods get the appropriate dims and substitude them to Affine Expressions using AffineMap.compose method. For example, if we have (-d0 + d1) and d0 and d1 are from 0 to 1, then the maximum index method has 0 for d0 and 1 for d1 because the negative values get larger as its absolute values are smaller. And, the minimum index method has 1 for d0 and 0 for d1.
This version uses AffineMap.compose to get each affine expressions' constant value, but the map.compose method returns all results of expressions of the map. I tried to make a new compose method returning only the result of the given expression, but it seemed I still need AffineMap.. Is there any way to get the only target expression's value? I tried to use getAffineConstantExpr method, but it did not return the exact result..

hanchung added inline comments.May 13 2021, 9:09 PM

We usually pass SmallVectorImpl as function argument.


I don't get the idea easily, maybe need some more comments? Do you have any assumption here?

inho9606 added inline comments.May 14 2021, 5:09 AM

Ah, like this?
SmallVectorImpl<SmallVector<int64_t, 4>>?


My idea is something like this:
The goal is to get the maximum index and minimum index in the range (result of the given affine expression). For example, let's say we have affine_map<(d0, d1) -> (d0, d1, -d0 + d1)> binding to memref<3x3x3xf32>.
According to the createLoopRanges method, we can get d0 = 3 and d1 = 3, which is 0 <= d0 < 3 and 0 <= d1 < 3.
To maximize the expression -d0 + d1, we need 0 for d0 and 2 for d1, 0 + 2 = 2. To minimize the expression, we need 2 for d0 and 0 for d1, (-2 + 0 = -2), which is an invalid index.
So, if the affine expression has dims multiplied by a negative constant, then we should substitude appropriate values (0 or range) to the dims in order to get the maximum or minimum value. And I found affine expression writes dims * constant even if the given expression is constant * dim. For example, affine_map<(d0) -> (-d0)> is written (d0 * -1).
AffineExpr.walk method allows me to check the AffineExprKinds of its AffineExpr. So, if it is 'd0 * -1', then I can get its result step by step.
d0 == AffineExprKind::DimID --> d0
-1 == AffineExprKind::constant --> -1
'* == AffineExprKind::mul --> d0 * -1 (Please remove ', it automatically makes lists starting with *..)
So, to get the kind of operator (add or multiply), I had to keep two operands before reaching out the operator using variables named a and b (I know the names are not clear,, could you suggest me better one?). I tried to find dividing cases in tests, but couldn't find them. So it only works with add and multiplication.. Is it fine? Please let me know if I missed something..

hanchung added inline comments.May 17 2021, 11:19 AM

I meant SmallVectorImpl<int64_t>.


I'd like to point out this again. They are rare cases. I don't see any use cases of this before. This increases overheads in verifying operations. However, we don't see any such case, which means that we are just adding overheads in verification. I also suspect we won't see them in the near future. Can we add the check when this is really a case?

Other concerns on my side:

  1. The example is very trivial. I'm afraid that we miss many cases.
  2. There are other kinds of AffineExpr, like Mod, FloorDiv, etc. What happened in those cases is undefined in your implementation.
  3. Some affine expression won't be simplified during parsing, e.g., affine_map<(d0, d1) -> (-(d0 + d1))>. Maybe simplifyAffineExpr would work for this case.
hkim15 added a subscriber: hkim15.May 18 2021, 1:33 AM
hkim15 added inline comments.

Logically, en.value().getDimSize() makes sense only when en.value().isDynamicDim(j) is false. If so, I recommend checking en.value().isDynamicDim(j) before calling en.value().getDimSize().

hkim15 added inline comments.May 18 2021, 2:01 AM

If shapedDimSize == 0, any access to this tensor is invalid since # of elements in this tensor is 0. I think we should report an error instead of ignoring this and "continue" to the next dimension.

  1. Updating D102305: The final update of static checker for linalg operations with the maximum and minimum indices #
  2. Enter a brief description of the changes included in this update.
  3. The first line is used as subject, next lines as comment.

Rebase for sync

inho9606 added inline comments.May 18 2021, 7:45 AM

I see. Thanks for letting me the concerns. I just found the case that the startIndices and endIndices might not detect, and wanted to try making the checker as perfect as possible. But my implementation might have other issues as you said.. I thought the parser could simplify all affine expressions, and mod or floordiv might not be used here because I couldn't find such testcases..
Then, can I close this revision after discussing other suggestions with @hkim15?


Yes, I think it can still be checked as the invalid one even although we don't check if the shapedDimSize == 0 here because of line number 494 of the original code, or line number 530-531 of the current patch. If the DimSize is 0, then the index would be -1, so the conditions would detect it and generate the error message. But, @hanchung and I found a testcase using 0xf32 tensor, so we had to choose to modify the testcase or ignore the case.

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>


@hanchung What do you think about this?

hanchung added inline comments.May 18 2021, 10:46 AM

the parser could simplify all affine expressions

Some could be simplified, but some could not. I looked into some tests of AffineMap and realized it.

mod or floordiv might not be used here because I couldn't find such testcases.

They are not well defined I think. We can have them, but we don't recommend it. Actually the case you're trying to check can't be found in the repo right?

can I close this revision after discussing other suggestions with @hkim15

Sure thing, feel free to close it.


They were come from

I don't have much context about it, but there are some reasons to having it.

inho9606 marked an inline comment as not done.May 18 2021, 5:50 PM
inho9606 abandoned this revision.May 21 2021, 12:47 AM