This is an archive of the discontinued LLVM Phabricator instance.

[mlir] Normalize dynamic memrefs with a map of tiled-layout.
ClosedPublic

Authored by imaihal on Feb 28 2021, 6:47 PM.

Details

Summary

Steps for normalizing dynamic memrefs for tiled layout map

  1. Check if original map is tiled layout. Only tiled layout is supported.
  2. Create normalized memrefType. Dimensions that include dynamic dimensions in the map output will be dynamic dimensions.
  3. Create new maps to calculate each dimension size of new memref. In tiled layout, the dimension size can be calculated by replacing "floordiv <tile size>" with "ceildiv <tile size>" and "mod <tile size>" with "<tile size>".
  4. Create AffineApplyOp to apply the new maps. The output of AffineApplyOp is dynamicSizes for new AllocOp.
  5. Add the new dynamic sizes in new AllocOp.

This patch also set MemRefsNormalizable trant in CastOp and DimOp since
they used with dynamic memrefs.

Diff Detail

Event Timeline

imaihal created this revision.Feb 28 2021, 6:47 PM
imaihal requested review of this revision.Feb 28 2021, 6:47 PM
imaihal retitled this revision from Normalize dynamic memrefs with a map with tiled-layout. to Normalize dynamic memrefs with a map of tiled-layout..
imaihal updated this revision to Diff 327022.Feb 28 2021, 8:55 PM

Clean up.

imaihal retitled this revision from Normalize dynamic memrefs with a map of tiled-layout. to [mlir] Normalize dynamic memrefs with a map of tiled-layout..Feb 28 2021, 9:57 PM
bondhugula requested changes to this revision.Mar 1 2021, 12:58 AM
bondhugula added a reviewer: avarmapml.
bondhugula added inline comments.
mlir/lib/Transforms/Utils/Utils.cpp
440–441

Please use empty().

No need of the else below.

464–467

Triple /// comments here and everywhere below.

This revision now requires changes to proceed.Mar 1 2021, 12:58 AM

A few minor comments.

mlir/lib/Transforms/Utils/Utils.cpp
457–460

No need of the else.

533

Terminate the comment with fullstop.

546

Terminate the comment with fullstop.

609–611

else block should also have the braces since the then block has it.

bondhugula added inline comments.Mar 1 2021, 8:36 PM
mlir/lib/Transforms/Utils/Utils.cpp
421

Doc comment please.

423

is a tiled ...

424

This is really a useful utility to have - thanks!

452

tileCount - please expand it out for readability.

imaihal updated this revision to Diff 327436.Mar 2 2021, 6:31 AM
imaihal marked 9 inline comments as done.

Rebased and Reflected comments.

@bondhugula @avarmapml Thanks for your reviews! I reflected your comments.

mlir/lib/Transforms/Utils/Utils.cpp
421

Updated comments and moved them before createNewDynamicSizes()

imaihal updated this revision to Diff 328164.Mar 4 2021, 7:10 AM

Rebased.

@bondhugula @avarmapml Thanks for your review! I reflected your comments. Do you have any other comments on this?

bondhugula requested changes to this revision.Mar 13 2021, 3:44 AM

Some style related comments.

mlir/lib/Transforms/NormalizeMemRefs.cpp
40

It may be unclear why this comment is specific to dynamic memrefs here. You can just say that the affine.apply op is needed to normalize dynamic memrefs.

mlir/lib/Transforms/Utils/Utils.cpp
384

Doc comment please explaining the meaning of this enum and its values.

398

Instead of getKind() - please use isa<AffineConsta.... Likewise above and anywhere else.

412

const std::pair... &ts to avoid a copy.

437

You don't need to pass a builder - this method is not constructing IR. You only need the context which can be passed.

Also, please move the output argument to the end (inMemrefTypeDynDims).

mlir/test/Transforms/normalize-memrefs-ops-dynamic.mlir
14–20

These would be hard to maintain and the tests below would be less readable with all definitions here. Instead, please use -split-input-file and the ----- separator. The maps will be relative/local in that case and can be defined right above the function.

93

of not tiled layout -> that are not tiled layout maps

This revision now requires changes to proceed.Mar 13 2021, 3:44 AM
bondhugula added inline comments.Mar 13 2021, 3:50 AM
mlir/test/Transforms/normalize-memrefs-ops-dynamic.mlir
30–31

I assume these dim ops will still be around after this pass but they would disappear after a -canonicalize if the alloc op they were used in is erased.

imaihal updated this revision to Diff 331459.Mar 17 2021, 9:32 PM
imaihal marked 7 inline comments as done.

Reflected comments.

imaihal added inline comments.Mar 17 2021, 9:51 PM
mlir/test/Transforms/normalize-memrefs-ops-dynamic.mlir
30–31

@bondhugula Thanks for your comments!
I checked generated code after canonicalization. In this case, dim ops are still existed, but some affine_maps are erased. The code before canonicalization shows what I implemented. So, don't I have to update this output? Or, should I use the output after canonicalization?

  • Before canonicalization
#map0 = affine_map<(d0, d1, d2, d3) -> (d1)>
#map1 = affine_map<(d0, d1, d2, d3) -> (d2 ceildiv 32)>
#map2 = affine_map<(d0, d1, d2, d3) -> (32)>
module  {
  func @test_norm_dynamic12(%arg0: memref<1x?x?x1x?x64xf32>) {
    %c1 = constant 1 : index
    %c2 = constant 2 : index
    %0 = dim %arg0, %c1 : memref<1x?x?x1x?x64xf32>
    %1 = dim %arg0, %c2 : memref<1x?x?x1x?x64xf32>
    %c1_0 = constant 1 : index
    %c14 = constant 14 : index
    %2 = affine.apply #map0(%c1_0, %0, %1, %c14)
    %3 = affine.apply #map1(%c1_0, %0, %1, %c14)
    %4 = affine.apply #map2(%c1_0, %0, %1, %c14)
    %5 = alloc(%2, %3, %4) : memref<1x?x?x1x?x64xf32>
    "test.op_norm"(%arg0, %5) : (memref<1x?x?x1x?x64xf32>, memref<1x?x?x1x?x64xf32>) -> ()
    dealloc %5 : memref<1x?x?x1x?x64xf32>
    return
  }
}
  • After canonicalization
#map = affine_map<()[s0] -> (s0 ceildiv 32)>
module  {
  func @test_norm_dynamic12(%arg0: memref<1x?x?x1x?x64xf32>) {
    %c1 = constant 1 : index
    %c2 = constant 2 : index
    %0 = dim %arg0, %c1 : memref<1x?x?x1x?x64xf32>
    %1 = dim %arg0, %c2 : memref<1x?x?x1x?x64xf32>
    %2 = affine.apply #map()[%1]
    %3 = alloc(%0, %2) : memref<1x?x?x1x32x64xf32>
    %4 = memref_cast %3 : memref<1x?x?x1x32x64xf32> to memref<1x?x?x1x?x64xf32>
    "test.op_norm"(%arg0, %4) : (memref<1x?x?x1x?x64xf32>, memref<1x?x?x1x?x64xf32>) -> ()
    dealloc %3 : memref<1x?x?x1x32x64xf32>
    return
  }
}
imaihal updated this revision to Diff 331473.Mar 18 2021, 12:06 AM

Removed canonicalize.

@bondhugula @avarmapml Thanks for your review! I reflected your comments. Do you have additional comments?

imaihal marked an inline comment as done.Mar 29 2021, 6:47 AM

@bondhugula @avarmapml Sorry again, but I would like to use this patch in my use case. Could you merge this if you can approve?

bondhugula requested changes to this revision.Apr 1 2021, 8:32 PM
bondhugula added inline comments.
mlir/lib/Transforms/Utils/Utils.cpp
396

A tiled layout map has to be clearly defined here so that it's clear what the formal condition to check for is. Please see comment further below.

422

While this handles the common case, this method isn't sound in general: because you'd have to check that for each d_i floordiv t_s, there exists one and only one d_i mod t_s and the former comes before the latter? But even this part isn't clear because a tiled layout map isn't defined in the doc comment of this method - so it'd be ultimately unclear as to what the formal condition to check here is.

429–431

Nit: return tileCount == tileSizes.size();

This revision now requires changes to proceed.Apr 1 2021, 8:32 PM
imaihal updated this revision to Diff 335214.Apr 5 2021, 12:35 AM
imaihal marked 2 inline comments as done.

Rebased and reflected comments.

imaihal updated this revision to Diff 335215.Apr 5 2021, 1:26 AM

Fixed code that accidentally deleted a previous fix, and updated comments.

imaihal updated this revision to Diff 335217.Apr 5 2021, 1:33 AM

Fixed a comment.

@bondhugula Thanks for your review! I reflected your comments. Could you review again?

mlir/lib/Transforms/Utils/Utils.cpp
422

@bondhugula I used AffineExpr.walk here, but it was not correct. I removed it.

This isTiledLayoutMap works as follows in #map_tiled1 = affine_map<(d0, d1, d2, d3) -> (d0, d1, (d2 floordiv 4) floordiv 32, (d3 mod 8) floordiv 64, (d2 floordiv 4) mod 32, (d3 mod 8) mod 64)>,

  1. Finds "<AffineExpr> floordiv <AffineConstantExpr>".

In this example, they are (d2 floordiv 4) floordiv 32 and (d3 mod 8) floordiv 64. So, tileSizes includes {d0 floordiv 4, 32} and {d3 mod 8, 64}.

  1. Finds "<AffineExpr> mod <AffineConstantExpr>", and compares them with the tileSizes

In this example, they are (d2 floordiv 4) mod 32 and (d3 mod 8) mod 64, and the pair of {d2 floordive 4, 32} and {d3 mod 8, 64} exists in the tileSize. So it returns true.

bondhugula requested changes to this revision.Apr 7 2021, 10:16 PM
bondhugula added inline comments.
mlir/include/mlir/Dialect/MemRef/IR/MemRefOps.td
242

Please capture this change in the commit summary as well - thanks.

391

Likewise - please add a brief line on this in the commit summary.

mlir/lib/Transforms/Utils/Utils.cpp
397

But this condition is technically wrong - it's a necessary one but no where close to the sufficient condition. The number of floordiv's being equal to the number of mod's for a dim expression doesn't make the affine map a tiled layout map. It needs to have a specific structure.

This revision now requires changes to proceed.Apr 7 2021, 10:16 PM
imaihal updated this revision to Diff 337347.Apr 13 2021, 11:47 PM
imaihal marked 4 inline comments as done.

Updated condition of tiled-layout map used in isTiledLayoutMap()

imaihal edited the summary of this revision. (Show Details)Apr 13 2021, 11:48 PM
imaihal added inline comments.Apr 13 2021, 11:51 PM
mlir/lib/Transforms/Utils/Utils.cpp
397

@bondhugula Thanks for review again. I updated the condition for tiled-layout map. How do you think of it?

imaihal updated this revision to Diff 337594.Apr 14 2021, 6:03 PM

Updated to solve warning message in clang-tidy and rebased.

bondhugula requested changes to this revision.Apr 18 2021, 3:41 AM
bondhugula added inline comments.
mlir/lib/Transforms/Utils/Utils.cpp
408

I think this variable is misnamed - it should be modExprs?

409

Nit: you can use llvm::reverse(map.getResults()).

425–429

Shouldn't all the floordiv exprs come before mod's?

435

Range-based loop?

436–438

This can be written in one line using llvm::is_contained(floorDivs, ...).

This revision now requires changes to proceed.Apr 18 2021, 3:41 AM
imaihal updated this revision to Diff 338529.Apr 19 2021, 8:23 AM
imaihal marked 5 inline comments as done.

Reflected comments for isTiledLayoutMap().

imaihal added inline comments.Apr 19 2021, 8:37 AM
mlir/lib/Transforms/Utils/Utils.cpp
435

All of elements in modExprs need to be found in floorDivs. So, I think we need to check all of the elements.

bondhugula added inline comments.Apr 19 2021, 1:47 PM
mlir/lib/Transforms/Utils/Utils.cpp
434

Nit: avoid auto.

435

Yes, I was only asking for a switch to a range-based for loop from an iterator one. You could check all elements.

bondhugula requested changes to this revision.Apr 19 2021, 2:05 PM
bondhugula added inline comments.
mlir/lib/Transforms/Utils/Utils.cpp
398

I'm sorry but what you have here again is a necessary condition but not sufficient. For eg. the following is not the kind of tiled layout maps you want to detect:
d0 / 32, d1 / 32, d0 / 64, d1 mod 32)
The sufficient condition is actually much simpler - you need a specific k dimensions being floordiv'ed and then those same k dimensions appearing with a mod w.r.t the same tile sizes and nothing else (no other expressions) involving those dimensions. Also, this function should provide those tile sizes back to the call site (as an extra output argument) - since a user would in nearly all cases want those for further action.

519–521

But looks like you are assuming here that every floordiv has a corresponding mod which isn't the case given the check you have. Consider
d0 / 32, d1 / 32, d0 / 64, d0 mod 32, d1 mod 32 - will this work correctly?
I think isTiledLayoutMap should just return the tile sizes and the corresponding positions (since the tile-space ordering can be different from the intra-tile one), and you could use it here. This way you would unify the logic for createDimSizeExprForTiledLayout with isTiledLayoutMap?

602

Nit: is -> is a

This revision now requires changes to proceed.Apr 19 2021, 2:05 PM
imaihal added inline comments.Apr 19 2021, 7:56 PM
mlir/lib/Transforms/Utils/Utils.cpp
398

@bondhugula Thanks for your review. Sorry, I may be confused about tiled layout.

  • d0 / 32, d1 / 32, d0 / 64, d1 mod 32)

I implemented the function returns true for this map because d1 dimension meets tiled layout pattern (tiled in d1 dimension using tile size of 32, and not tiled in d0 dimension), but you suggested this is not true.
In this map, d0 dimension is floordived, but no mod for d0. Is this the reason why we can not say this is the tiled layout?

  • d0 / 32, d1 / 32, d0 / 64, d0 mod 32, d1 mod 32

In another comment, you showed this map. Can we say this is the tiled layout ? (tiled in d0 dimension using tile size of 32, and tiled in d1 dimension using tile size of 32?)

imaihal added inline comments.Apr 19 2021, 8:14 PM
mlir/lib/Transforms/Utils/Utils.cpp
519–521

@bondhugula

d0 / 32, d1 / 32, d0 / 64, d0 mod 32, d1 mod 32 - will this work correctly?

This does not work correctly in current implementation. I will update using the tile sizes and the positions.

imaihal updated this revision to Diff 339647.Apr 22 2021, 8:13 AM
imaihal marked 4 inline comments as done.

Updated check routine for a tiled layout. It checks dimensions being floordiv'ed and then those same dimensions appearing with a mod and no other expressions involving those dimensions. Also, the routine provides those tile sizes back to the call site.

imaihal updated this revision to Diff 339843.Apr 22 2021, 7:16 PM

Fixed errors in clang-tidy.

@bondhugula I updated the patch.

The sufficient condition is actually much simpler - you need a specific k dimensions being floordiv'ed and then those same k dimensions appearing with a mod w.r.t the same tile sizes and nothing else (no other expressions) involving those dimensions. Also, this function should provide those tile sizes back to the call site (as an extra output argument) - since a user would in nearly all cases want those for further action.

I implemented this and changed the function name from isTiledLayoutMap() to getTileSizePos(). I hope this meets your request.

imaihal updated this revision to Diff 342725.May 4 2021, 7:25 AM

Rebased.

Hi, @bondhugula , I updated this patch to reflect your suggestions. How do you think of this?

Hi, @bondhugula , I updated this patch to reflect your suggestions. How do you think of this?

Sorry about the delay. I should be able to review this (will hopefully be the final round) in the next one day.

mlir/lib/Transforms/Utils/Utils.cpp
401–402

Can you use an output parameter instead of returning? Sometimes RVO may not happen and will lead to an extra copy.

498

Nit: Can you add the output parameter as the last argument?

imaihal updated this revision to Diff 344051.May 10 2021, 7:16 AM

Used output parameters to reflect comments.

imaihal updated this revision to Diff 344307.May 11 2021, 1:04 AM

Rebased and removed unnecessary include file.

imaihal marked 2 inline comments as done.May 11 2021, 1:07 AM
bondhugula added inline comments.May 11 2021, 4:33 AM
mlir/lib/Transforms/NormalizeMemRefs.cpp
42

This can be instead specified in a single line in Passes.td.

mlir/lib/Transforms/Utils/Utils.cpp
397

Many typos here:
no other expression doesn't involve -> no other expression involves
are appeared -> appear
by a tile size <-- this is inaccurate since tile sizes can be different

-> by respective tile sizes
400

an empty vector is returned.

424

It's more readable to return an empty vector - does {} or SmallVector<...>{}/() work?

480

Why do you need a separate vector just to return empty? Does {} or SmallVector<...>{}/() work?

515

This isn't clear - which dimension size is being referred to here?

602

single -> single level ?

662

tileSizePos.empty() instead of size() == 0.

672–674

if shape[d] < 0, you are adding an invalid constraint here: 0 <= s <= -2

imaihal updated this revision to Diff 344820.May 12 2021, 7:23 AM

Reflected comments.

imaihal marked 8 inline comments as done.May 12 2021, 8:16 AM

@bondhugula Thanks for the review! I updated the code. Do you have any other comments?

mlir/lib/Transforms/Utils/Utils.cpp
515

This function checks if dim of normalized memref is dynamic using inMemrefTypeDynDims. Return true if dim is dynamic.

672–674

Changed to use the constraint only in static dimension.

bondhugula added inline comments.May 13 2021, 10:51 PM
mlir/lib/Transforms/Utils/Utils.cpp
519–521

You probably don't need to handle this unless there is a use case. So long as the form handled is documented, which I think you have, it should be fine.

This revision is now accepted and ready to land.May 13 2021, 10:51 PM
imaihal marked 2 inline comments as done.May 14 2021, 12:00 AM

@bondhugula Much appreciate your reviews!

I don't have commit access. Could you commit this patch?

imaihal updated this revision to Diff 346714.May 20 2021, 6:49 AM

Rebased.
Could you land this patch?

This revision was automatically updated to reflect the committed changes.