<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/07/2015 06:42 PM, Adam Nemet
wrote:<br>
</div>
<blockquote
cite="mid:88BAEE4F-AABE-4CA1-BAA8-55D2BC2B991C@apple.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<br class="">
<div>
<blockquote type="cite" class=""><br>
<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><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>
</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>
<br>
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>
<blockquote
cite="mid:88BAEE4F-AABE-4CA1-BAA8-55D2BC2B991C@apple.com"
type="cite">
<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 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>
</body>
</html>