<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 8, 2015, at 12:37 PM, Philip Reames <<a href="mailto:listmail@philipreames.com" class="">listmail@philipreames.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class="">
<meta content="text/html; charset=utf-8" http-equiv="Content-Type" class="">
<div bgcolor="#FFFFFF" text="#000000" class="">
<br class="">
<div class="moz-cite-prefix">On 01/07/2015 06:42 PM, Adam Nemet
wrote:<br class="">
</div>
<blockquote cite="mid:88BAEE4F-AABE-4CA1-BAA8-55D2BC2B991C@apple.com" type="cite" class="">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" class="">
<br class="">
<div class="">
<blockquote type="cite" class=""><br class="">
<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">
<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 class=""><br class="">
</div>
<div class="">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 class=""><br class="">
</div>
<div class="">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>
</blockquote>
Just to note, I'm going to be very interested in seeing this. I
have concerns about profitability, but having a mechanism is clearly
a good thing. :)<br class=""></div></div></blockquote><blockquote type="cite" class=""><div bgcolor="#FFFFFF" text="#000000" class="">Are you also looking at loop fusion? I've seen that come up in
practice for a few cases where it would *really* help. Generally,
filter/reduce patterns implemented by hand. Nowhere near the top of
my priority list, but if you happened to be working on it, I'm happy
to help review and brainstorm. <br class=""></div></blockquote><div><br class=""></div><div>Yes, we’re planning to look at fusion next. Thanks for all your feedback so far!</div><div><br class=""></div><div>As to your example, do you mean chain of operations functional-programming style? E.g. with OO syntax:</div><div><br class=""></div><div>list.map(func1).map(func2).filter(func3).reduce(func4), where these could be squashed into one loop.</div><div><br class=""></div><div>Thanks,</div><div>Adam</div><div><br class=""></div><blockquote type="cite" class=""><div bgcolor="#FFFFFF" text="#000000" class="">
<blockquote cite="mid:88BAEE4F-AABE-4CA1-BAA8-55D2BC2B991C@apple.com" type="cite" class="">
<div class="">
<div class="">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 class=""><br class="">
</div>
<div class="">Thanks,</div>
<div class="">Adam</div>
<div class=""><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 moz-do-not-send="true" 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 moz-do-not-send="true" 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 moz-do-not-send="true" 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="">
</blockquote>
<br class="">
</div>
</blockquote></div><br class=""></body></html>