<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 7, 2015, at 5:33 PM, Chandler Carruth <<a href="mailto:chandlerc@google.com" class="">chandlerc@google.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" style="font-family: Helvetica; font-size: 12px; 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=""><div class="gmail_extra"><div class="gmail_quote"><br class="Apple-interchange-newline">On Wed, Jan 7, 2015 at 5:19 PM, Philip Reames<span class="Apple-converted-space"> </span><span dir="ltr" class=""><<a href="mailto:listmail@philipreames.com" target="_blank" class="">listmail@philipreames.com</a>></span><span class="Apple-converted-space"> </span>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;"><div bgcolor="#FFFFFF" text="#000000" class="">I've been playing with approaches to getting better optimization of loops which contain infrequently executed slow paths. I've gotten as far as throwing together a proof of concept implementation of a profile guided optimization to separate a single loop with multiple latches into a loop nest, but I want to get feedback from interested parties before investing much more effort. <span class="Apple-converted-space"> </span><br class=""><br class="">The primary case I'm concerned about looks something like this C example:<br class="">while( some_condition )<br class=""> <span class="Apple-converted-space"> </span>//do lots of work here<br class=""> <span class="Apple-converted-space"> </span>if (!some_rare_condition) { <-- This is loop variant<br class=""> <span class="Apple-converted-space"> </span>helper();<br class=""> <span class="Apple-converted-space"> </span>}<br class="">}<br class=""><br class="">The key point here is that the 'do lots of work' section contains things we could lift out of the loop, but our knowledge of memory gets completely destoryed by the 'helper' call which doesn't get inlined. This ends up crippling LICM in particular, and GVN to a lessor degree. <span class="Apple-converted-space"> </span><br class=""><br class="">The approach I've been playing with would create this loop structure:<br class="">goto inner<br class="">while (true) {<br class=""> <span class="Apple-converted-space"> </span>outer:<br class=""> <span class="Apple-converted-space"> </span>helper();<br class=""> <span class="Apple-converted-space"> </span>inner:<br class=""> <span class="Apple-converted-space"> </span>while( some_condition )<br class=""> <span class="Apple-converted-space"> </span>//do lots of work here<br class=""> <span class="Apple-converted-space"> </span>if (!some_rare_condition) { <-- This is loop variant<br class=""> <span class="Apple-converted-space"> </span>goto outer;<br class=""> <span class="Apple-converted-space"> </span>}<br class=""> <span class="Apple-converted-space"> </span>}<br class="">}<br class=""><br class="">(Excuse the psuedo-C. Hopefully the idea is clear.)<br class=""></div></blockquote><div class=""><br class=""></div><div class="">Yep.</div><div class=""><br class=""></div><div class="">I've not thought about this a lot, but I have two initial questions that maybe you can answer:</div><div class=""><br class=""></div><div class="">How does this compare with classical approaches of loop peeling, partitioning, fission, or whatever you might call it? Is there any literature behind this approach or some literature it should be compared with? (I genuinely don't know this area that well, so I'm of little help here…)</div></div></div></div></div></blockquote><div><br class=""></div><div>I think it’s pretty different from loop distribution/fission. In loop distribution, in order to split the loop into multiple consecutive loops, you need to reason about the memory references so having a function call makes that difficult/impossible. Phillip’s idea works around this exact issue.</div><div><br class=""></div><div>I explored this space quite a bit recently because we’re working on a proposal to add loop distribution to LLVM. I hope to send out the proposal this week.</div><div><br class=""></div><div>So I see no issue with trying to handle loops with low-probablity function calls with this and fully self-contained loops with classical loop distribution.</div><div><br class=""></div><div>Thanks,</div><div>Adam</div><div><br class=""></div><blockquote type="cite" class=""><div dir="ltr" style="font-family: Helvetica; font-size: 12px; 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=""><div class="gmail_extra"><div class="gmail_quote"><div class="">Some of your points I have quick feedback on:</div><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;"><div bgcolor="#FFFFFF" text="#000000" class=""><div class=""><div class=""><p class="">Points for discussion:</p><ul class=""><li class="">Is using profile information for this purpose even a reasonable thing to do?</li></ul></div></div></div></blockquote><div class="">Yes!</div><div class=""> </div><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;"><div bgcolor="#FFFFFF" text="#000000" class=""><div class=""><div class=""><ul class=""><li class="">I chose to implement this without relying on the existing block frequency analysis. My reasoning was that a) this is a rarely taken case and adding an expensive analysis dependency probably wasn't worthwhile and b) that block frequency analysis was more expensive/precise than I really needed. Is this reasonable?</li></ul></div></div></div></blockquote><div class="">I think we should always use the analyses. Either BlockFrequency or BranchProbability. I think probably both in the common joint usage (frequency of the loop header combined with probability of the cold region).</div><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;"><div bgcolor="#FFFFFF" text="#000000" class=""><div class=""><div class=""><ul class=""><li class="">If so, is the notion of 'rareness' of a loop block something that's worth extracting out on it's own and reusing? Are there other similar uses anyone can think of?</li><li class="">Currently, I'm only supporting a fairly small set of controlling conditions. Are there important cases I'm not considering?</li></ul></div></div></div></blockquote><div class="">To both of these, I think the general combination to use is to identify the set of blocks dominated by a block which is in the loop body of a hot loop, and is cold relative to the other successors of its predecessor(s). These form cold "regions" as I think of them without requiring the complexity of the region analysis.</div><div class=""> </div><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;"><div bgcolor="#FFFFFF" text="#000000" class=""><div class=""><div class=""><ul class=""><li class="">Since the rarest latch is often deep in a loop - with other "if (X) continue;" (i.e. latches) before it - this tends to create loops with multiple exiting blocks. Some of the existing passes might not deal with this well, is that a major concern? Suggestions for how to analysis and validate?</li></ul></div></div></div></blockquote><div class="">I'm somewhat concerned about this, but want to think more about the fundamental transformation.</div><div class=""> </div><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;"><div bgcolor="#FFFFFF" text="#000000" class=""><div class=""><div class=""><ul class=""><li class="">Currently, I've structured this as pulling off the rarest latch as an outer iteration. I could also pull off the most popular latch as an inner iteration. This might give different tradeoffs; thoughts?</li></ul><p class="">Generally, any thoughts anyone have on the problem or approach are welcome. I'm not particular attached to the particular approach laid out here and if there's a more advantageous approach, all the better.</p></div></div></div></blockquote></div>Thanks for pushing on this! ;] Now I need to go and ponder a lot so i can reply more deeply on the actual transform.<br class=""><br class=""></div></div><span style="font-family: Helvetica; font-size: 12px; 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: 12px; 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: 12px; 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: 12px; 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=""><a href="mailto:LLVMdev@cs.uiuc.edu" style="font-family: Helvetica; font-size: 12px; 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="">LLVMdev@cs.uiuc.edu</a><span style="font-family: Helvetica; font-size: 12px; 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 class="Apple-converted-space"> </span> </span><a href="http://llvm.cs.uiuc.edu/" style="font-family: Helvetica; font-size: 12px; 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="">http://llvm.cs.uiuc.edu</a><br style="font-family: Helvetica; font-size: 12px; 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=""><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" style="font-family: Helvetica; font-size: 12px; 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="">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a></blockquote></div><br class=""></body></html>