<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jan 23, 2015, at 2:20 PM, Michael Zolotukhin <<a href="mailto:mzolotukhin@apple.com" class="">mzolotukhin@apple.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div style="font-family: Helvetica; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><blockquote type="cite" class=""><div class=""><br class="Apple-interchange-newline">On Jan 23, 2015, at 1:27 PM, James Molloy <<a href="mailto:james@jamesmolloy.co.uk" class="">james@jamesmolloy.co.uk</a>> wrote:</div><br class="Apple-interchange-newline"><div class="">Hi Michael,<br class=""></div></blockquote>Hi James,<br class=""><blockquote type="cite" class=""><div class=""><br class=""><div class="">This looks very much like the inner loops from convolve() in Geekbench... ;)</div></div></blockquote>Yes, the original example was from Geekbench, but I wasn’t sure if I can copy it:)</div><div style="font-family: Helvetica; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><br class=""><blockquote type="cite" class=""><div class=""><div class="">Interestingly if we reroll that loop nest, the number of instructions inside goes down by a factor of 3 so we do decide to inline them all. But that is just luck / a hack. I completely agree that our current unrolling heuristics don't take the right things into account (our inlining heuristics are similar!).</div></div></blockquote><blockquote type="cite" class=""><div class=""><div class=""><br class="">When thinking about this previously, I've been worried that there's a slippery slope where you could end up implementing half of the rest of the compiler's analysis passes in the unroller/inliner to check for opportunities. Do you have any thoughts on that? How do we keep it under control?</div></div></blockquote>That’s a valid point. Theoretically, I think the best solution here would be to run remaining passes in ‘sand-box’ mode and decide what to do basing on what this run shows. But it’s hard to tell when to stop in these sand-box runs: Should we just run const-prop+InstCombine? Should we try other loop optimizations after that? Should we run all passes including backend (e.g. unrolling will have a huge impact on scheduling, so it could really be interesting)? And in any case, it would be quite compile-time expensive.</div><div style="font-family: Helvetica; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><br class=""></div><div style="font-family: Helvetica; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">So, right now it seems to me that the best solution is to model future optimizations by (hopefully simple) heuristics. I don’t think that we should worry much that the code reminds const-prop, or another simple pass. However, if we try to reimplement a vectorizer, or, say SROA, inside our heuristic, then probably something is wrong. As I said, we should either model such passes with simple heuristics, or we should think about interfaces in these passes that would allow to execute dry-runs.</div><div style="font-family: Helvetica; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><br class=""></div><div style="font-family: Helvetica; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">E.g. another possible heuristic for unroller would be the following: if after unrolling all loads/stores are consecutive, then it’s beneficial to unroll, because the code will be probably vectorized by SLP later. That’s a simple heuristic, and in some cases it will give a wrong advice. We can either accept it, or add an interface to SLP so that it'll answer whether it can vectorize an instructions sequence or not. That would be the second way, more accurate but more expensive.</div><div style="font-family: Helvetica; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><br class=""></div><div style="font-family: Helvetica; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">In some cases the first approach would be acceptable, in others - the second, and I think that should be decided on a case-by-case basis.</div><div style="font-family: Helvetica; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><br class=""></div><div style="font-family: Helvetica; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class="">Michael</div></div></blockquote><div><br class=""></div><div>There is no better short-term solution than experimenting with heuristics. But down the road we could think of orchestrating optimizations so that specific heuristics and their expected outcome (eg. #loads saved per loop) is recorded and a later phase un-does the optimization (eg. re-rolling the loop or even outlining) when the expected benefits have not been realized (or not been realized significantly enough). This would provide a more global optimization conscious approach that should protect from outlier cases when heuristics goes wrong. </div><br class=""><blockquote type="cite" class=""><div class=""><div style="font-family: Helvetica; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><br class=""></div><div style="font-family: Helvetica; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><blockquote type="cite" class=""><div class=""><div class=""><br class=""></div><div class="">cc'ing Kevin who has been doing a lot of work recently on the loop unroller.</div><div class=""><br class=""></div><div class="">Cheers,</div><div class=""><br class=""></div><div class="">James</div><br class=""><div class="gmail_quote">On Fri Jan 23 2015 at 8:52:30 PM Michael Zolotukhin <<a href="mailto:mzolotukhin@apple.com" class="">mzolotukhin@apple.com</a>> wrote:<br class=""><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;">Hi devs,<br class=""><br class="">Recently I came across an interesting testcase that LLVM failed to optimize well. The test does some image processing, and as a part of it, it traverses all the pixels and computes some value basing on the adjacent pixels. So, the hot part looks like this:<br class=""><br class="">for(y = 0..height) {<br class=""> for (x = 0..width) {<br class=""> val = 0<br class=""> for (j = 0..5) {<br class=""> for (i = 0..5) {<br class=""> val += img[x+i,y+j] * weight[i,j]<br class=""> }<br class=""> }<br class=""> }<br class="">}<br class=""><br class="">And ‘weight' is just a constant matrix with some coefficients.<br class=""><br class="">If we unroll the two internal loops (with tripcount 5), then we can replace weight[i,j] with concrete constant values. In this particular case, many of the coefficients are actually 0 or 1, which enables huge code simplifications later on. But currently we unroll only the innermost one, because unrolling both of them will exceed the threshold.<br class=""><br class="">When deciding whether to unroll or not, we currently look only at the instruction count of the loop. My proposal is to, on top of that, check if we can enable any later optimizations by unrolling - in this case by replacing a load with a constant. Similar to what we do in inlining heuristics, we can estimate how many instructions would be potentially eliminated after unrolling and adjust our threshold with this value.<br class=""><br class="">I can imagine that it might be also useful for computations, involving sparse constant matrixes (like identity matrix).<br class=""><br class="">The attached patch implements this feature, and with it we handle the original testcase well.<br class=""><br class=""><br class=""><br class="">Does it look good? Of course, any ideas, suggestions and other feedback are welcome!<br class=""><br class=""><br class="">Thanks,<br class="">Michael______________________________<u class=""></u>_________________<br class="">LLVM Developers mailing list<br class=""><a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank" class="">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu/" target="_blank" class="">http://llvm.cs.uiuc.edu</a><br class=""><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank" class="">http://lists.cs.uiuc.edu/<u class=""></u>mailman/listinfo/llvmdev</a><br class=""></blockquote></div></div></blockquote></div><br class="" style="font-family: Helvetica; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><span style="font-family: Helvetica; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">_______________________________________________</span><br style="font-family: Helvetica; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class="">LLVM Developers mailing list</span><br style="font-family: Helvetica; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class=""><a href="mailto:LLVMdev@cs.uiuc.edu" class="">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" class="">http://llvm.cs.uiuc.edu</a></span><br style="font-family: Helvetica; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><span style="font-family: Helvetica; font-size: 18px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; float: none; display: inline !important;" class=""><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" class="">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a></span></div></blockquote></div><br class=""></body></html>