<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/111830>111830</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [mlir][linalg] Tiling: wrong offset computed when modulo operations are present in access maps
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            mlir
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          cferry-AMD
      </td>
    </tr>
</table>

<pre>
    On tiling `linalg` ops using the tiling interface, we create `extract_slice` ops that retrieve a slice of the input tensors. These correspond to the footprint of one tile of iterations on the tensor. These slices are defined by an offset, a side and strides. 

When tiling the following op with `scf::tileConsumerAndFuseProducersUsingSCF` and a tile size of 1x16:
```mlir
#map1 = affine_map<(d0, d1) -> ((d0 - 1) mod 3, d1)>
#map2 = affine_map<(d0, d1) -> (d0, d1)>
module {
  func.func @forward(%arg1: tensor<3x128xf32>) -> tensor<4x128xf32> attributes {plhw.toplevel} {
    %1 = tensor.empty() : tensor<4x128xf32>
    %2 = linalg.generic {indexing_maps = [#map1, #map2], iterator_types = ["parallel", "parallel"]} 
        ins(%arg1 : tensor<3x128xf32>) outs(%1 : tensor<4x128xf32>) {
    ^bb0(%in: f32, %out: f32):
 linalg.yield %in : f32
    } -> tensor<4x128xf32>
    return %2 : tensor<4x128xf32>
  }
}
```
we obtain this:
```mlir
#map = affine_map<(d0) -> (d0 - ((d0 - 1) floordiv 3) * 3 - 1)>
#map1 = affine_map<(d0, d1) -> ((d0 - 1) mod 3, d1)>
#map2 = affine_map<(d0, d1) -> (d0, d1)>
module {
  func.func @forward(%arg0: tensor<3x128xf32>) -> tensor<4x128xf32> attributes {plhw.toplevel} {
    %c16 = arith.constant 16 : index
    %c1 = arith.constant 1 : index
    %c128 = arith.constant 128 : index
    %c4 = arith.constant 4 : index
    %c0 = arith.constant 0 : index
    %0 = tensor.empty() : tensor<4x128xf32>
 %1 = scf.for %arg1 = %c0 to %c4 step %c1 iter_args(%arg2 = %0) -> (tensor<4x128xf32>) {
      %2 = scf.for %arg3 = %c0 to %c128 step %c16 iter_args(%arg4 = %arg2) -> (tensor<4x128xf32>) {
        %3 = affine.apply #map(%arg1)
        %extracted_slice = tensor.extract_slice %arg0[%3, %arg3] [3, 16] [1, 1] : tensor<3x128xf32> to tensor<3x16xf32>
 %extracted_slice_0 = tensor.extract_slice %arg4[%arg1, %arg3] [1, 16] [1, 1] : tensor<4x128xf32> to tensor<1x16xf32>
        %4 = linalg.generic {indexing_maps = [#map1, #map2], iterator_types = ["parallel", "parallel"]} ins(%extracted_slice : tensor<3x16xf32>) outs(%extracted_slice_0 : tensor<1x16xf32>) {
        ^bb0(%in: f32, %out: f32):
          linalg.yield %in : f32
        } -> tensor<1x16xf32>
        %inserted_slice = tensor.insert_slice %4 into %arg4[%arg1, %arg3] [1, 16] [1, 1] : tensor<1x16xf32> into tensor<4x128xf32>
        scf.yield %inserted_slice : tensor<4x128xf32>
      }
      scf.yield %2 : tensor<4x128xf32>
 }
    return %1 : tensor<4x128xf32>
  }
}
```

Notably, the offset for `%extract_slice` is computed as such:
```mlir
#map = affine_map<(d0) -> (d0 - ((d0 - 1) floordiv 3) * 3 - 1)> // (d0 - 1) mod 3
%5 = affine.apply #map(%arg5)
%extracted_slice = tensor.extract_slice %arg0[%3, %arg3] [3, 16] [1, 1] : tensor<3x128xf32> to tensor<3x16xf32>
```
which, when `%arg5 = 0`, gives `%5 = 2`, and with a slice of size 3 of a tensor of slice 3, turns out to be out of bounds.

The problem lies in mlir/lib/Dialect/Linalg/Utils/Utils.cpp:633: we apply the access map to the lower bound of the iteration domain of the tile to get the offset, however this assumes that lower bound is the argmin of the access map for that dimension. For quasi-affine maps containing `mod` operations like the one in this example, this is not true.

One way to solve this would be to compute the lexmin of the image of one tile by the affine map, and the size could be computed with the lexmax (provided the difference with the lexmin is a constant or is at least bounded). Note that although this would hopefully make the code generated correct, it would also over-approximate the amount of data actually needed from a tensor and so reduce the locality benefit of tiling.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzUWF-T66oN_zTkRbMZG9vZzUMecjYnT-29nem508cdbOSYFoMLOH_66TuA7Ti72T-90-npzexkA0jiJyEJCWatOCjEDSm-kWK3YL1rtNlUNRpzedj-ebcoNb9sflXghBTqAGSVSKGYPJBVArqz0Fs_7RocKYRyaGpWIaHPcEKoDDKHnhHPzrDKvVgpKhz5XcMcGHRG4BGBQVgEXQeRQnW9A4fKamOX8KNBi1BpY9B2WnFwOpDVWrvOCOU8n1YBSpAhHBrmhFYWtIogg6xRVNjMAjMIHGuhkEN5AaZA17VF5zVgYAVHYIqDdUZwtEsgyY4k2_j9twYn40QsUuqTH-kOTsI1XnNb1STbkmzrgT1rZfsWzVbxfW_xL0bzvkJjf_OW_Ovz3lvGb8eiGlb8K-iSntOVFxL3XiXxr5XCDFM0a1mXAsl2wGqvzEvLOpI9E_rEE68KTwldwwPJvgOhT2EaHiBMtppDNtGQ7PtcJv2yzNncJKPVvJcI5PFbHAPUvaqW_gtIntTanJjhAVDBzCEl2XY4JZI9Z-eUPp3rjHpx40bTaj5bBeacEWXv0Pq9Otmclk53Eo8oyeNuvj8AoUU01OAO2HbuEiCs4Wb_-Q437NEmMRSWB1RoROX3EIrjWaiDt5MNND6y4tF42wwWJcXOj6J_avPiLh3OyGnHDJMSJaE0ct3MFLug0YTHf4SyVxvCh0bUvRto0w-09aa4sVnxvSyTyCeU5_OEAVyhezdNrCcnHc1zESg5BDYYya5iH3cfnOqVzqDrjRpN_8kRkcfd4MDTjzFg4vCEoEvHhE8Kwn4eVu9GwNz34eFNXNVSa8PF0QfXGgjdQjYsvYqxP3zcJv-juK3SVVTLCNcsK62sY8pBmN1CCL9X9HfJ36WmT3fpw_Rdjvweff4edXKPOnmHOvm9OWrKb7aql7U2cM0LuwGG0wN667AbDOXT0Qszh2smoSPHjat_LWHM8uQtjOwtDG_fK5DVHST5yORR_R4wAU42C4kl6zp5GTLy7P6h6zdsQ-WCPNYuN8cyL2pgjAWfxItsyI5eZVKE1B6m0tUwCjdCGgbvBU8ocWYLqzcH_QrbS_IZujyii7q-Bph-BWD-HsD0DcCrDfOff2NOd-Tb89zet_LNbXnP0tv7yt91v__8Ap0-X7lJ79-mHx2JUBbNXa-OK1e3yX1Zr_9rDjQDFQV_cvn7j88hM_1fIf-0ZpsVBXfkfV5T3HBfi5GPKqivFiPx-xftWCkv3mC-j4gdCISsuUqu3nftnoSFSrdd75ADs2D7qvlJhQwQuid0D3dKk2Hrovg08RZT4v0_Trivy8hGVE3oc30XGM_JqxLwBjL6DAdx9JkqLMYVOqz4Li-0iLO2N7R7mf_FBhxhNiwHZbznWZ-VPNISwy9dQ6l7xe1y7lE_GoTO6FJiC1KgBaEg-APdS1ESut8JJrFyhO7_FHt6uv_NCWnH_8uq60i2XWWZN9cJIR6cd09WVWgteI8amnCpT2gijKl9H9tv4Lr1xfYwH_pap-GAbubrXrlGn_CIJlTlwKzvk4cngrl4YSMGc2ivQmeIfNAEJi5aVFZotYS9NvDPnlnxEJ0QwnVTaeW7gOFlo9U8PktMrwZS_AMjRIUwdAuAZ9Z2EmOkCuvhKO3AmR5v7P-rQjixi9fUannESH3SveT-4Jwe4zfaD88zbUTLDnjznFEOhp_Qjx7kZ4PXVKPkKS0E5xqFs7MP0M7oo-AY2bioazSoKrwlFcorxWCqULUJEw4kMuviMSAndL2EX3RQgDlg0jW6PzRzPRvdYd1LeYGWDaasNEcIBQDzGMNzTuXi5T5wMWk16COaB9Z1Rp9FywYrsVb38Z2HM8eAVa5nXrpC9ErVRrfXwAmPNhoM8r4ajKwrJoW7QIkKaxEExceb5YJvMr7O1myBm_SRPhWr_DFJFs1mjWVOyyzjlBZrltUl1rQqaV3mj-s8z3AhNjSheZqkSUqLNE-WSVrnZVpVnJZ8XRUVyRNsmZBLKY_tUpvDQljb4yZN06csWUhWorSbWMfEAPUVy8JsPP1D2R8syRMprLNXCU44GZ7tAkOxI8W34WGu2MGPoFIIWqPVYbxMrn7h01Vo8PTc25nxCQMtKued_RpRdtEbuWmc60KvHLL9QbimL5eVbn0-kcfx30Nn9N9jVgla-mwyKHrc0H8HAAD__-azAr8">