# \[RFC\] Add Linalg TileOp

**URL:** <https://discourse.llvm.org/t/rfc-add-linalg-tileop/2833>\
**Category:** MLIR\
**Created:** [February 16, 2021, 3:13pm UTC](https://discourse.llvm.org/t/rfc-add-linalg-tileop/2833 "2021-02-16T15:13:49Z")\
**Posts on this page:** 1\
**Showing post:** 8

<div class="post-metadata">

**Author:** ![nicolasvasilache](https://sea1.discourse-cdn.com/flex021/user_avatar/discourse.llvm.org/nicolasvasilache/32/131_2.png) [@nicolasvasilache](https://discourse.llvm.org/u/nicolasvasilache)\
**Post date:** [February 17, 2021, 11:09am UTC](https://discourse.llvm.org/t/rfc-add-linalg-tileop/2833/8 "2021-02-17T11:09:40Z")

</div>

Thanks Alex for pushing on this!

> [@pifon2a](#):
>
> Tiling for a Linalg operation on tensors results in a number of `subtensor` ops for the inputs and `subtensor_insert` ops for the outputs of the op, i.e. the elements of the output tensor are populated via destructive updates. Neither `scf.for` nor `scf.parallel` are suitable for containing `subtensor_insert` in their bodies.

`scf.for` with sequential semantics is actually fine (parallel is something else though). The destructive updates are a bit annoying to work with but still end up being a welcome simplifcation compared to `memref` + `load` + `store`. Basically in traditional polyhedral analysis, one would worry about all possible interleavings of possibly aliasing loads and stores in the context of the k-common surrounding loops. With scf.for + subtensor + subtensor\_insert + yield there is a lot more ordering and dealiasing thanks to SSA use-def chains. Still, we can indeed simplify things and make them nicer to work with with an abstraction like you propose.

> [@pifon2a](#):
>
> The `linalg.tile` operation represents a loop nest taking the usual lower bounds, upper bounds and steps arguments and the input/output tensor arguments like in `linalg.generic` .

There are some interesting details that are swept under the rug here and that are useful to unpack, esp. if we also think of this in the context of other data types than dense tensors and memrefs.  
Linalg ops that conforms to the structured op interface fully derive their iterator bounds from their operands and come with a number of [structural properties](https://mlir.llvm.org/docs/Dialects/Linalg/#payload-carrying-opsa-namepayload_opsa).  
Applying tiling and fusion on such ops introduces control-flow like `scf.for` and other ops to capture information that cannot be represented with the op semantics.

It would have been nice to keep similar structural properties in the op but this comes with a nasty inverse problem that we don’t think we want to have to solve.

Essentially:

```auto
%0 = scf.for %i = 0 to 42 step 5 iter_args(%arg0 = %C ) -> tensor<?x?xf32> {
  %tiledA = subtensor %A ... 
  %tiledB = subtensor %B ...
  %tiledC = subtensor %arg0 ...
  %tiledD = some_op_1(%tiledA, %tiledB) ...
  %tiledE = some_op_2(%tiledC, %tiledD) ...
  %res = subtensor_insert %tiledE into %arg0 ...
  scf.yield %res : tensor<?x?f32>
}

```

is really: `tile(some_op_2(some_op_1(%A, %B) ,%C), 5)`.

And we would like to express this as an op with a region that I’ll call “region after”-tiling:

```auto
linalg.some_fancy_op (%A, %B, %C) <some_extra_attributes_and_operands> {
^bb(%tiledA, %tiledB, %tiledC) {
  %tiledD = some_op_1(%tiledA, %tiledB) ...
  %tiledE = some_op_2(%tiledC, %tiledD) ...
  linalg.yield %tiledE ...
}}

```

Unfortunately, we could not find a good generic form for this that works in the general case as it raises some nasty inverse problems. The options we have discussed are:

1. explicitly represent subtensor / subtensor\_insert or some slightly re-spelled version in the body of the new nesting linalg op (current proposal).
2. keep a “region before”-tiling and a “region after” tiling + enough info to apply tiling to derive the subtensor / subtensor\_insert (leaning towards no).
3. pass whatever info is necessary to `<some_extra_attributes_and_operands>` to only keep the “region after”-tiling (abandonned).

The issue with 3. is that `<some_extra_attributes_and_operands>` will quickly grow and we don’t even know how to solve some cases (i.e. given the “region after”-tiling form with ops that have their own indexing maps and parallelism semantics + a bag of `<some_extra_attributes_and_operands>` it is unclear we can recover the subtensor / subtensor\_insert with their permutation in the general case). Additionally, it will not properly compose with other things (e.g. mapping to an SPMD model).

The issue with 1. is that the control of the op becomes “iteration-centric” (i.e. loop-like) as opposed to “data-centric” for the structured linalg ops. Longer-term things like tiling and distributing non-dense-strided-memref data types will not work on this abstraction (e.g. this only models hyperrectangular iteration spaces). Still we can make progress with it and reevaluate when more pieces are connected.

The issue with 2. is that it keeps around some old IR form and is generally counterintuitive.  
In the future we will likely reopen the work to extend the `linalg.range` abstractions so that we can have 2. without the inverse problem that would also work with other data types. This will take some time to get designed and discussed.

> [@pifon2a](#):
>
> ```auto
> linalg.subtensor_yield %C_subtensor into [offsets][sizes][strides],
> %D_subtensor into [offsets][sizes][strides]
> : type(%C_subtensor), type(%D_subtensor) 
> 
> ```

This will quickly grow to become unmanageable.  
I’d split that into multiple terminators or multiple ops + yields, something close to `subtensor_insert + yield`. This will require a little bit of non-local behavior for the validation and has a bit of an awkward semantic:

```auto
%rX = insert_like %x into %X[offsets][sizes][strides]: typeof(%x) into typeof(%X)
yield %rX : typeof(%rX) // But we actually really yield %x@[offsets][sizes][strides]

```

Would it be reasonable to have blocks with multiple terminators or is this something generally not worth exploring?

> [@MaheshRavishankar](#):
>
> It seems like this op might require an `iterator_types` attribute to designate what are dependences between the tiles.

+1, we will need that to remain closer in spirit to a “data-centric” abstraction.

> [@MaheshRavishankar](#):
>
> Apart from this, the spec looks good to me. I am really happy this will go a long way in killing `subtensor_insert` .

`subtensor_insert` is fine and if you look closer this proposal does not remove the abstraction but rather its interaction with `scf.for` for the parallel case. However we end up spelling this op and its version of subtensor\_insert that yields, the underlying tradeoff I wrote about at the top of the post still persists: in SSA-value land the destructive update pattern is useful, we use it for vector.transfer + scf.for + scf.yield hoisting too. This hides is a little more from the user but comes with non-trivial tradeoffs.

---

_[View the full topic](https://discourse.llvm.org/t/rfc-add-linalg-tileop/2833)._