This is an archive of the discontinued LLVM Phabricator instance.

[mlir] Added support for symbols inside linalg.generic and map concatenation
ClosedPublic

Authored by limo1996 on Jul 4 2020, 6:38 AM.

Details

Summary

This commit adds functionality needed for implementation of convolutions with
linalg.generic op. Since linalg.generic right now expects indexing maps to be
just permutations, offset indexing needed in convolutions is not possible.
Therefore in this commit we address the issue by adding support for symbols inside
indexing maps which enables more advanced indexing. The upcoming commit will
solve the problem of computing loop bounds from such maps.

This commit is a fold of these commits:

[mlir] Added support for symbols inside linalg.generic indexing maps


[mlir] Added support for the shift of the symbols inside AffineExpr


[mlir] Added support for symbols in map concatenation

Diff Detail

Event Timeline

limo1996 created this revision.Jul 4 2020, 6:38 AM
Herald added a project: Restricted Project. · View Herald Transcript
limo1996 updated this revision to Diff 275503.Jul 4 2020, 8:45 AM

Fixed clang-tidy warning

ftynse requested changes to this revision.Jul 6 2020, 5:45 AM

Thanks, a couple of comments

mlir/lib/Dialect/Linalg/Transforms/Loops.cpp
39

Please don't commit commented-out code

173

Please don't use auto unless if it improves readability (e.g. for very long types such as iterators, or when the type is already mentioned in the same statement such as getAttrOfType).

177

Call .reserve to allocate space in the vector before calling push_back in a loop.

178

Can you just do for (unsigned i = 0, e = shapedType.getRank(); i < e; ++i) instead of enumerating the shape and using only the indices?

mlir/test/Dialect/Linalg/loops.mlir
17

Nit: the expression doesn't seem to correspond to a _strided_ convolution

ftynse added inline comments.Jul 6 2020, 5:45 AM
mlir/test/Dialect/Linalg/loops.mlir
949

Please don't pattern-match on SSA value names (%c0), they are not guaranteed to be stable.

953

Hmm, would it be possible to put this operation before the loops (actually, there is one already, many we can just reuse its value)?

This revision now requires changes to proceed.Jul 6 2020, 5:45 AM
limo1996 updated this revision to Diff 275737.Jul 6 2020, 9:33 AM

Most of the comments incorporated

ftynse added inline comments.Jul 7 2020, 1:32 AM
mlir/lib/IR/AffineMap.cpp
394

This function is still not supposed to work for maps with symbols IIUC

410

Is this change necessary?

422–425

There are more of these, I only commented on the first occurrence.

limo1996 marked 6 inline comments as done.Jul 7 2020, 1:56 AM
limo1996 added inline comments.
mlir/lib/IR/AffineMap.cpp
410

When numSymbols == 0 then numDims == numInputs but yeah no need for the change..

limo1996 updated this revision to Diff 275953.Jul 7 2020, 2:18 AM
limo1996 marked 6 inline comments as done.

removed commented code

limo1996 marked an inline comment as done.Jul 7 2020, 2:21 AM
limo1996 added inline comments.
mlir/lib/IR/AffineMap.cpp
394

At this point it should. The next diff introduces function that bypasses inversePermutation call

410

Actually at this point there is a need for it. I will revert it in the next commit..

mlir/test/Dialect/Linalg/loops.mlir
949

Hmm I saw them in other tests so I just used them.. When naming convention changes other tests will need changes as well..

953

Hmm I think --cse solves it right?

ftynse requested changes to this revision.Jul 7 2020, 3:38 AM
ftynse added inline comments.
mlir/lib/IR/AffineMap.cpp
394

I see two bad practices here:

  • trying to commit commented-out code: if the assertion is no longer necessary, remove it completely, add a test that exercises the new behavior, and update the doc;
  • commits are not self-contained: if this change is only required for the next commit, it should be included in that commit and removed from this one.
mlir/test/Dialect/Linalg/loops.mlir
949

The fact that other tests currently contradict the testing guide https://mlir.llvm.org/getting_started/TestingGuide/ because of legacy (they likely existed before the current convention was adopted) does not mean you are allowed to commit new code that also contradicts the testing guide. If you notice such tests, the proper hygiene is to update them as well, in a separate commit.

There is _no_ naming convention for SSA names. The only convention is that SSA names can change at any time without any warning, that's why tests should not rely on them. If you disagree with the guide, feel free to start a discussion on the forum.

MLIR currently has ~400 test input files totalling ~70k LoC. Updating matches for SSA names in all of them would be extremely painful, will likely take days or weeks even with automation and require multiple rounds because other commits will be editing tests concurrently. This sounds like extremely poor use of engineering time, compared to several minutes spent writing the proper match conditions for each new commit.

953

If it is simple to do in your code, you should do it instead of expecting the caller to run CSE after the fact. Otherwise, we risk getting into a situation where each pass requires five other cleanup passes to run, each of which also require five other cleanup passes and so on. If doing so feels like you start reimplementing a generic CSE, then you shouldn't do it. It's a trade-off that must be considered rather than shrugged off.

This revision now requires changes to proceed.Jul 7 2020, 3:38 AM
nicolasvasilache requested changes to this revision.Jul 7 2020, 5:14 AM
nicolasvasilache added inline comments.
mlir/include/mlir/Dialect/Linalg/IR/LinalgStructuredOps.td
560

Can we increase the description and add IR examples ?
In particular, if symbol_source is specified, it seems we need a symbol for every single dim of the corresponding operand?

What happens if the operand is partially static?
Atm it seems we add symbols for everything.
Will partially static operands break something down the line? (If so please at least add a TODO).

Additionally, it seems like symbol_source should be a proper ODS Optional Attribute this way some of the code you write would be auto generated?

mlir/lib/Dialect/Linalg/IR/LinalgOps.cpp
267

I think most of this could go away with a proper confined integer attr (e.g. https://github.com/llvm/llvm-project/blob/master/mlir/include/mlir/Dialect/StandardOps/IR/Ops.td#L1983)

272

It seems the logic behind this targetRank and its usage should be hidden behind a op.getNumSymbolsPerOperand() that would return a SmallVector<unsigned> where each operand index has the number of symbols.
This would also be somewhat future proof if we decided we wanted to turn the the symbol source into an ArrayAttr

283–285

this seems incorrect as all indexing maps could have the number of symbols of operand X.
If you had the helper above you could check m.getNumSymbols() != 0 && m.getNumSymbols() != op.getNumSymbolsPerOperand()[idx]

mlir/lib/IR/AffineExpr.cpp
101

Drop dims above and make this

return replaceDimsAndSymbols({}, symbols);

?

mlir/lib/IR/AffineMap.cpp
394

I don't see how this is correct.
Bypassing a caller has no incidence on potential other callers and the code would be bugged.

Let's revert the 2 changes to this function please.

410

If it is not necessary let's revert is now, I don't see value in making a change that is reversed in a subsequent commit without a solid justification.

limo1996 updated this revision to Diff 276401.Jul 8 2020, 6:11 AM

Changed static addressing of constants in tests. shiftSymbols function modified as Nicolas suggested.

limo1996 marked 3 inline comments as done.Jul 8 2020, 6:14 AM
limo1996 updated this revision to Diff 276669.Jul 9 2020, 2:10 AM

Documentation for symbol_source attribute extended

limo1996 marked 2 inline comments as done.Jul 9 2020, 2:26 AM
limo1996 added inline comments.
mlir/include/mlir/Dialect/Linalg/IR/LinalgStructuredOps.td
560

Documentation updated..

In particular, if symbol_source is specified, it seems we need a symbol for every single dim of the corresponding operand?

Yes we do.

What happens if the operand is partially static?

It behaves the same as if it was dynamic. Do you think it should behave differently? i.e. to not require a symbol for static dimension?

Will partially static operands break something down the line?

I don't think so

Additionally, it seems like symbol_source should be a proper ODS Optional Attribute this way some of the code you write would be auto generated?

Yes there is a separate WIP revision for that. Once it is approaved I will merge it into this one.

limo1996 updated this revision to Diff 276730.Jul 9 2020, 6:59 AM
limo1996 marked an inline comment as done.

problem with commented code inside inversePermutation solved

limo1996 marked 3 inline comments as done.Jul 9 2020, 7:05 AM
limo1996 marked 3 inline comments as done.Jul 10 2020, 1:46 AM
limo1996 added inline comments.
mlir/test/Dialect/Linalg/loops.mlir
953

I will do it in the follow up commit

limo1996 updated this revision to Diff 277002.Jul 10 2020, 5:40 AM
limo1996 marked an inline comment as done.

revision D83378 merged: [mlir][WIP] symbol_source attr in linalg.generic proposal

limo1996 marked 3 inline comments as done.Jul 10 2020, 8:44 AM
limo1996 added inline comments.
mlir/lib/Dialect/Linalg/IR/LinalgOps.cpp
249

@nicolasvasilache @ftynse I found the function name misleading as not only GenericOp and IndexedGenericOp are passed but also LinalgStructuredOps which does not allow me to call functions defined in GenericOpBase. Should I circumvent it somehow or just avoid functions I defined in GenericOpBase?

272

If we turn symbol source into ArrayAttr then we must either pass dimensions from all operands specified in the symbol source into the maps as symbols or we will pass only dimensions of the corresponding operand which is really limited and does not support our case when we need dimensions of the operand in the map that does not correspond to it.

283–285

Yes, all maps can have the number of symbols of operand X. Is it wrong?

If you had the helper above you could check m.getNumSymbols() != 0 && m.getNumSymbols() != op.getNumSymbolsPerOperand()[idx]

This condition basically allows only map at index equal to symbol_source to have symbols which is not correct as in our scenario we want to have symbols in the map corresponding to the input view and not the kernel view.

ftynse added inline comments.Jul 10 2020, 9:26 AM
mlir/lib/Dialect/Linalg/IR/LinalgOps.cpp
249

If you can avoid new ops, just do that. Possibly you can have a verifier in the GenericOp that calls this function, and then does some additional things. Otherwise, it's template-parameterized by the actual OpType, so it should be possible to use template specialization to work around missing functions
.

272

A helper function looks reasonable from the code complexity perspective regardless of the further evolution. ArrayAttr discussion is irrelevant for the current patch.

ftynse added inline comments.Jul 16 2020, 4:27 AM
mlir/lib/Dialect/Linalg/IR/LinalgOps.cpp
298–299

Please don't put usernames after TODO in LLVM codebase.

mlir/lib/Dialect/Linalg/Transforms/Loops.cpp
471

Please use full sentences in comments: start with a capital letter and terminate with a period, https://llvm.org/docs/CodingStandards.html#commenting.

ftynse accepted this revision.Jul 16 2020, 5:57 AM

Works for me after the last comments are addressed.

Very sorry for the delay, thanks Jakub!

One more question inline re the dropping of symbols that seems to look a bit fishy.

Thanks for pushing this!

mlir/include/mlir/Dialect/Linalg/IR/LinalgStructuredOps.td
489

thanks!

560

sounds good, thanks!

mlir/lib/Dialect/Linalg/IR/LinalgOps.cpp
249

This is mostly related to better OpInterface definition.
This is good for now, I'll refactor and cleanup a bit at some later time, thanks!

272

The comment was about code hygiene, not suggesting we should discuss this extension right now.
Basically l 264-272 is an implementation detail that should be hidden away in a helper function today.
If tomorrow the logic grows this new helper function will be the right place to impl this.

283–285
this seems incorrect as all indexing maps could have the number of symbols of operand X.

I was thinking about the case where we have >1 operands that want to propagate their symbols.
This falls into the extension to ArrayAttr that is better disregarded for now.

283–285
This condition basically allows only map at index equal to symbol_source to have symbols which is not correct as in our scenario we want to have symbols in the map corresponding to the input view and not the kernel view.

Ah I see, thanks for explaining, the symbols of the kernel are indeed used in the input.
Then I'd recommend making things homogeneous from the get go.
Instead of

#conv_1d_accesses = [
  affine_map<(m, n)[s0] -> (m + n - s0 floordiv 2)>, // in
  affine_map<(m, n) -> (n)>, // filter
  affine_map<(m, n) -> (m)> // out
]

let's use:

#conv_1d_accesses = [
  affine_map<(m, n)[s0] -> (m + n - s0 floordiv 2)>, // in
  affine_map<(m, n)[s0] -> (n)>, // filter
  affine_map<(m, n)[s0] -> (m)> // out
]

?

The fact that only the first operand map had [s0] had me think that s0 corresponds to the operand 0 (even though it clearly says 1).

<don't consider for now>
and so in the future, when we want symbols from multiple operands, we can just concatenate them all and still remain homogeneous.
</don't consider for now>

mlir/lib/Dialect/Linalg/Transforms/Loops.cpp
473

This looks quite unsafe to me.
It seems the proper way to drop symbols would be to replace them all with 0.

Is this just a temporary thing that needs to be fixed in the next CL and the state of the codebase is that incorrect code may be generated?

ftynse added inline comments.Jul 16 2020, 6:29 AM
mlir/lib/Dialect/Linalg/Transforms/Loops.cpp
473

Good point. Can we just return {} to signify failure in presence of symbols? The tests for generated loops can go into the following commit where the loop bound computation is added. Here, we can just keep the "roundtripping" test that makes sure we print back what we parsed.

limo1996 marked 3 inline comments as done and an inline comment as not done.Jul 16 2020, 11:39 PM
limo1996 marked 16 inline comments as done.Jul 17 2020, 7:59 AM

All comments resolved

mlir/lib/Dialect/Linalg/IR/LinalgOps.cpp
249

Ok let me know once it's refactored so I can simplify my code as well. Thanks :)

Code starting at line 264 can then be simplified to:

auto symSrc = op.getSymbolSource();
if (symSrc.hasValue() && symSrc.getValue() >= op.getNumOperands())
  return op.emitOpError("symbol_source index out of range");
272

I think in the future once this function is refactored such that it takes only GenericOp and IndexedGenericOp we can introduce op.getNumSymbols() that would return sum of ranks of operands specified in symbol_source and lines 264-269 can be refactored like this:

auto symSrc = op.getSymbolSource();
if (symSrc.hasValue() && symSrc.getValue() >= op.getNumOperands())
  return op.emitOpError("symbol_source index out of range");

For now I refactored only line 271.

283–285

Yeah exactly, we are on the same page. I added s0 to every map to make it less confusing and also I enforce it now. Thanks for the feedback!

limo1996 updated this revision to Diff 278770.Jul 17 2020, 8:00 AM
limo1996 marked 3 inline comments as done.

All comments resolved

nicolasvasilache accepted this revision.Jul 17 2020, 8:27 AM
nicolasvasilache added inline comments.
mlir/include/mlir/Dialect/Linalg/Utils/Utils.h
123 ↗(On Diff #278770)

you should be able to just do:

linalgOp.indexing_maps().template getAsRange<AffineMapAttr, AffineMap>()

and drop the extra function.

mlir/lib/Dialect/Linalg/IR/LinalgOps.cpp
272

Ok I see how the fact that it is use on Generic, IndexedGeneric and on the op interface makes it less attractive to refactor now.
I'll fix, thanks!

283–285

Looks great, thanks!

This revision is now accepted and ready to land.Jul 17 2020, 8:27 AM
limo1996 marked 2 inline comments as done.Jul 17 2020, 9:17 AM
limo1996 updated this revision to Diff 279274.Jul 20 2020, 9:19 AM

Last comment of Nicolas resolved + found out one test is not passing which was caused by quite significant bug so fixed that as well

limo1996 marked an inline comment as done.Jul 20 2020, 9:21 AM
This revision was automatically updated to reflect the committed changes.