<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<br>
<div class="moz-cite-prefix">On 01/15/2015 09:59 AM, Adam Nemet
wrote:<br>
</div>
<blockquote
cite="mid:182E1AE1-A848-491C-8E63-6DF2B4E84B02@apple.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<br class="">
<div>
<blockquote type="cite" class="">
<div class="">On Jan 8, 2015, at 12:37 PM, Philip Reames <<a
moz-do-not-send="true"
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>
</blockquote>
That's exactly what I was thinking of. <br>
<blockquote
cite="mid:182E1AE1-A848-491C-8E63-6DF2B4E84B02@apple.com"
type="cite">
<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="">
</blockquote>
<br>
</body>
</html>