tree 3839cfd34dadcee5c37e09d4b3126259782d838d
parent 1f7762d884d26cbc2faf435bb393651c559518f1
author Max191 <44243577+Max191@users.noreply.github.com> 1755702609 -0700
committer GitHub <noreply@github.com> 1755702609 -0700
gpgsig -----BEGIN PGP SIGNATURE-----
 
 wsFcBAABCAAQBQJopeVRCRC1aQ7uu5UhlAAAnk4QACT9DN3Dx25o8mxzVJRnlRL7
 FufJ4836R0J0YVKGZRRHx7oNP0jaZWq7o2NbMdnvcNXQqXLz+sP36UN9S37nhJDu
 F6aYzEkMHljl1V6Bhc15FDcQZCRPIVv2pRuK1wWM6CqMYHpJ+fWHwHeHBNYJO1Sj
 J+6fSoFVhNHD0qwxn4OOVAF4N90FYbTEIVi1eTvClB5zgYt5WCuM9zGbxQaLUEkG
 6WpkoMw8ay9mThOkYupV/soJViWn+B0689vJDxbuZPALQNC2kKg351lLRZ0FcV81
 d8fI6A/QhQ3m0tx8VQxzkyTzsCXI4Tfwc8OzbDhO3cSwzM2Sw3sS6sxm4+o5GTrN
 bEsiOJxOZUBQZFcp3TJ4U/3CIxfRTNtjlwzNLphfnBTWm5qsoN3EkrVKmhyqimIC
 PaJT5Jww8QjV66dNEYvrwaDY24geuDx/FUEiXSnLYTdQS0Xi64OyZZoO9VUFs0CA
 GqPonah8nLsMeNF9qKvE9JwAcNaTfNdI4gxTF5X+wx24amd6SuspS6y5Es8mQqht
 EDuJuy+wi7bseJJHEf4b+H6dE7NLp0Y2ifie4HdafHYtdDcyI8ep0WCBwU0CMrLH
 yXdMK7kqB5WfiS+fTPnwYWuUUfjSE+DeadDPVps5Gc2IU5y4tuHpLXbAz34sjSUI
 w/hD/p8j0HcZ/Lz3XFeV
 =Tdv5
 -----END PGP SIGNATURE-----
 

[Codegen] Improve early bufferized padding codegen (#21694)

The current way we handle padding in CombineLayoutTransformation (the
early bufferization path) turns out to be very inefficient in some
cases, because we spend a lot of time spinning on indexing computation
while iterating over the output buffer. This PR updates the way we
generate the IR for writing padding values to avoid iterating over the
non-padded parts of the output buffer. The old and new methods are
described below:

### Old method ###

For a given tensor with padding, we would simply iterate over the entire
tensor, and write padding values when the indices fell within the padded
part of the output buffer. Visually this looks like the following:
```
          1st (only) loop (`x` == masked off)
         |———————————————————————————————————| 
                            |
                            v
         +———————————————————————————————————+
         | . . . . . . . . . . . . . . . . . |
         | . +———————————————————————+ . . . |
         | . | x x x x x x x x x x x | . . . |
         | . | x x x x x x x x x x x | . . . |
         | . | x x x x x x x x x x x | . . . |
         | . | x x x x x x x x x x x | . . . |
         | . +———————————————————————+ . . . |
         | . . . . . . . . . . . . . . . . . |
         +———————————————————————————————————+
```
### New method ###

There are multiple distributed loops, each loop performing the padding
for a hyperplane spanning the low or high pad of a corresponding
dimension, and fully spanning all other dimensions of the tensor. This
means that there is some overlap on the intersection of high and low
padding for each dimension.

```
 1st loop (low pad d0)        2nd loop (high pad d0)
        |———|                       |———————|
          |                             |
          v                             v
        +———+———————————————————————+———————+     ———
        | . | . . . . . . . . . . . | . . . | <--  |  3rd loop (low pad d1)
        +———+———————————————————————+———————+     ———
        | . | . . . . . . . . . . . | . . . |
        | . | . . . . . . . . . . . | . . . |
        | . | . . . . . . . . . . . | . . . |
        | . | . . . . . . . . . . . | . . . |
        +———+———————————————————————+———————+     ———
        | . | . . . . . . . . . . . | . . . | <--  |  4th loop (high pad d1)
        +———+———————————————————————+———————+     ———
```

With the new method, there is some overlap between loops, but the
overall padding computation is much cheaper because padding is expected
to be small relative to the output buffer size.

---------

Signed-off-by: Max Dawkins <max.dawkins@gmail.com>