<html><body><p><font size="2">I am happy to see positive feedback from multiple parties. </font><br><font size="2">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.</font><br><br><font size="2">Regards,</font><br><font size="2">Whitney Tsang</font><br><br><img width="16" height="16" src="cid:1__=8FBB0E77DFDC962F8f9e8a93df938690918c8FB@" border="0" alt="Inactive hide details for David Green ---2020/01/03 08:42:17 AM---Hello Sounds interesting, and it would be great to see Unroll"><font size="2" color="#424282">David Green ---2020/01/03 08:42:17 AM---Hello Sounds interesting, and it would be great to see Unroll and Jam get some</font><br><br><font size="2" color="#5F5F5F">From: </font><font size="2">David Green <David.Green@arm.com></font><br><font size="2" color="#5F5F5F">To: </font><font size="2">Whitney T Tsang <whitneyt@ca.ibm.com>, "llvm-dev@lists.llvm.org" <llvm-dev@lists.llvm.org></font><br><font size="2" color="#5F5F5F">Cc: </font><font size="2">nd <nd@arm.com></font><br><font size="2" color="#5F5F5F">Date: </font><font size="2">2020/01/03 08:42 AM</font><br><font size="2" color="#5F5F5F">Subject: </font><font size="2">[EXTERNAL] Re: [llvm-dev] [RFC] Changing LoopUnrollAndJamPass to a function pass.</font><br><hr width="100%" size="2" align="left" noshade style="color:#8091A5; "><br><br><br><tt><font size="2">Hello<br><br>Sounds interesting, and it would be great to see Unroll and Jam get some <br>love. I'm maybe being unimaginative, but I don't know of many cases <br>where Unroll-and-Jamming the outer loops would be more beneficial than <br>the code bloat it gave (a lot like normal unrolling). But making this a <br>function pass sounds useful anyway, it would avoid the awkward case of <br>accidentally unrolling the inner loop before the outer loop has been UnJ'd!<br><br> > 3. Less remaining loops are needed if we consider the whole loop nest <br>together<br><br>This one is interesting. UnJ was written for things like matrix multiply <br>on microcontroller's without vectorization available. It helps quite a <br>lot there. In our experience, we often end up unroll-and-jamming the <br>middle(j) iteration, then unrolling the inner(k) one, creating a tile of <br>sorts. It can create quite large code, but that code is quick on these <br>little cpus.<br><br>Oh, and IIRC UnJ was written in a way that it would potentially be <br>expanded to handle multiple inner loops. Or maybe I just had the idea <br>that it could be expanded like that, providing that you can work out all <br>the control flow and dependencies correctly. This might help with <br>unroll-and-jamming vectorized code too (although if outer loop <br>vectorization and interleaving is something that can already be handled <br>in the vectorizer, it may be better to leave it to do that job and have <br>it included in all it's cost modelling. Reverse-engineering that the <br>runtime checks are loop-invariant doesn't sound very reliable. If the <br>vectorizer can already do Unroll and Jam, let it do it on its own).<br><br>I look forward to seeing patches!<br>Dave<br><br>On 02/01/2020 19:00, Whitney T Tsang via llvm-dev wrote:<br>> LoopUnrollAndJamPass is currently a loop pass. It is added in a LPM with <br>> only itself.<br>> `OptimizePM.addPass(createFunctionToLoopPassAdaptor(LoopUnrollAndJamPass(Level)));`<br>> Notice that loops are traversed in an inner to outer order in a LPM.<br>> <br>> The current implementation of LoopUnrollAndJamPass supports only loop <br>> nest with one inner loop (L->getSubLoops().size() == 1).<br>> Consider the example below:<br>> Before loop unroll and jam:<br>> ```<br>> for i<br>> for j<br>> for k<br>> A[I][j][k] = 0;<br>> ```<br>> After loop unroll and jam loop-j with a factor of 2:<br>> ```<br>> for i<br>> for j += 2<br>> for k<br>> A[I][j][k] = 0;<br>> A[I][j+1][k] = 0;<br>> for j’=j<br>> for k<br>> A[I][j][k] = 0;<br>> ```<br>> Notice that LoopUnrollAndJamPass can no longer unroll and jam loop-i at <br>> the next invocation of LoopUnrollAndJamPass, since there exists two <br>> inner loops in loop-i.<br>> If LoopUnrollAndJamPass is a function pass, then it can control the <br>> order of the loops being considered. By doing the transformation from <br>> outer to inner, both loop-i and loop-j can be unroll and jammed.<br>> <br>> In conclusion, I propose to change LoopUnrollAndJamPass from loop to <br>> function pass, with the reasons below:<br>> 1. There is no obvious reason why LoopUnrollAndJamPass need to be a loop <br>> pass<br>> 2. More loops can be transformed by traversing in a outer to inter order<br>> 3. Less remaining loops are needed if we consider the whole loop nest <br>> together<br>> 4. Better cost model can be created by considering the whole loop nest <br>> together<br>> <br>> Regards,<br>> Whitney Tsang<br>> <br>> <br>> _______________________________________________<br>> LLVM Developers mailing list<br>> llvm-dev@lists.llvm.org<br>> </font></tt><tt><font size="2"><a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a></font></tt><tt><font size="2"> <br>> <br><br></font></tt><br><br><BR>
</body></html>