[llvm-dev] [RFC] Changing LoopUnrollAndJamPass to a function pass.

[Whitney T Tsang via llvm-dev]

I am happy to see positive feedback from multiple parties.
I will start working on my first NFCI patch which changes
LoopUnrollAndJamPass to a function pass, but keeps traversing the loops
from inner to outer.

Regards,
Whitney Tsang



From:	David Green <David.Green at arm.com>
To:	Whitney T Tsang <whitneyt at ca.ibm.com>,
            "llvm-dev at lists.llvm.org" <llvm-dev at lists.llvm.org>
Cc:	nd <nd at arm.com>
Date:	2020/01/03 08:42 AM
Subject:	[EXTERNAL] Re: [llvm-dev] [RFC] Changing LoopUnrollAndJamPass
            to a function pass.



Hello

Sounds interesting, and it would be great to see Unroll and Jam get some
love. I'm maybe being unimaginative, but I don't know of many cases
where Unroll-and-Jamming the outer loops would be more beneficial than
the code bloat it gave (a lot like normal unrolling). But making this a
function pass sounds useful anyway, it would avoid the awkward case of
accidentally unrolling the inner loop before the outer loop has been UnJ'd!

 > 3. Less remaining loops are needed if we consider the whole loop nest
together

This one is interesting. UnJ was written for things like matrix multiply
on microcontroller's without vectorization available. It helps quite a
lot there. In our experience, we often end up unroll-and-jamming the
middle(j) iteration, then unrolling the inner(k) one, creating a tile of
sorts. It can create quite large code, but that code is quick on these
little cpus.

Oh, and IIRC UnJ was written in a way that it would potentially be
expanded to handle multiple inner loops. Or maybe I just had the idea
that it could be expanded like that, providing that you can work out all
the control flow and dependencies correctly. This might help with
unroll-and-jamming vectorized code too (although if outer loop
vectorization and interleaving is something that can already be handled
in the vectorizer, it may be better to leave it to do that job and have
it included in all it's cost modelling. Reverse-engineering that the
runtime checks are loop-invariant doesn't sound very reliable. If the
vectorizer can already do Unroll and Jam, let it do it on its own).

I look forward to seeing patches!
Dave

On 02/01/2020 19:00, Whitney T Tsang via llvm-dev wrote:
> LoopUnrollAndJamPass is currently a loop pass. It is added in a LPM with
> only itself.
> `OptimizePM.addPass(createFunctionToLoopPassAdaptor(LoopUnrollAndJamPass
(Level)));`
> Notice that loops are traversed in an inner to outer order in a LPM.
>
> The current implementation of LoopUnrollAndJamPass supports only loop
> nest with one inner loop (L->getSubLoops().size() == 1).
> Consider the example below:
> Before loop unroll and jam:
> ```
> for i
>    for j
>      for k
>        A[I][j][k] = 0;
> ```
> After loop unroll and jam loop-j with a factor of 2:
> ```
> for i
>    for j += 2
>      for k
>        A[I][j][k] = 0;
>        A[I][j+1][k] = 0;
>    for j’=j
>      for k
>        A[I][j][k] = 0;
> ```
> Notice that LoopUnrollAndJamPass can no longer unroll and jam loop-i at
> the next invocation of LoopUnrollAndJamPass, since there exists two
> inner loops in loop-i.
> If LoopUnrollAndJamPass is a function pass, then it can control the
> order of the loops being considered. By doing the transformation from
> outer to inner, both loop-i and loop-j can be unroll and jammed.
>
> In conclusion, I propose to change LoopUnrollAndJamPass from loop to
> function pass, with the reasons below:
> 1. There is no obvious reason why LoopUnrollAndJamPass need to be a loop
> pass
> 2. More loops can be transformed by traversing in a outer to inter order
> 3. Less remaining loops are needed if we consider the whole loop nest
> together
> 4. Better cost model can be created by considering the whole loop nest
> together
>
> Regards,
> Whitney Tsang
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
>
https://urldefense.proofpoint.com/v2/url?u=https-3A__lists.llvm.org_cgi-2Dbin_mailman_listinfo_llvm-2Ddev&d=DwIF-g&c=jf_iaSHvJObTbx-siA1ZOg&r=p0DGcdtx8-l1bvwJTLSk1zBTXpb78Y1slqHKTsTpRTE&m=a_6w_QR2DwJjPBgugHgy00aautUSck-NjdyLUHSbc-E&s=WVb-88fLx3EZzSvSDVlrUrb48piebm6YPolmbobmuVk&e=

>



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200103/20e03fa1/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: graycol.gif
Type: image/gif
Size: 105 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200103/20e03fa1/attachment-0001.gif>