<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 05:33 PM, Chandler
Carruth wrote:<br>
</div>
<blockquote
cite="mid:CAGCO0Kj=brN28yWvH-5yQCQ9-Wa0i1rFX_2eu9S2H8Rbeu6PUg@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra"><br>
<div class="gmail_quote">On Wed, Jan 7, 2015 at 5:19 PM,
Philip Reames <span dir="ltr"><<a moz-do-not-send="true"
href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">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. <br>
<br>
The primary case I'm concerned about looks something
like this C example:<br>
while( some_condition )<br>
//do lots of work here<br>
if (!some_rare_condition) { <-- This is loop
variant<br>
helper();<br>
}<br>
}<br>
<br>
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. <br>
<br>
The approach I've been playing with would create this
loop structure:<br>
goto inner<br>
while (true) {<br>
outer:<br>
helper();<br>
inner:<br>
while( some_condition )<br>
//do lots of work here<br>
if (!some_rare_condition) { <-- This is loop
variant<br>
goto outer;<br>
}<br>
}<br>
}<br>
<br>
(Excuse the psuedo-C. Hopefully the idea is clear.)<br>
</div>
</blockquote>
<div><br>
</div>
<div>Yep.</div>
<div><br>
</div>
<div>I've not thought about this a lot, but I have two
initial questions that maybe you can answer:</div>
<div><br>
</div>
<div>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>
</blockquote>
I'm not aware of any literature that covers the specific transform
I'm suggesting here. This is probably a lack of awareness on my
part, not a lack of literature though. While I have some basic
background in the area, I can't claim to have made an extensive
study of loop optimization techniques. *Particularly* profile
guided ones. <br>
<br>
w.r.t. the tradoffs in practice, I'm going to answer this in a
separate response just to keep this one short. I've been playing
with both approaches and there appears to be appeal in both. I'm
currently leaning towards a mixture of both approaches. <br>
<br>
<blockquote
cite="mid:CAGCO0Kj=brN28yWvH-5yQCQ9-Wa0i1rFX_2eu9S2H8Rbeu6PUg@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div> </div>
<div><br>
</div>
<div>Some of your points I have quick feedback on:</div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>
<div>
<p>Points for discussion:</p>
<ul>
<li>Is using profile information for this purpose
even a reasonable thing to do?</li>
</ul>
</div>
</div>
</div>
</blockquote>
<div>Yes!</div>
<div> </div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>
<div>
<ul>
<li>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>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>
</div>
</div>
</div>
</blockquote>
Let me ask a basic question: what do BlockFrequency and
BranchProbability compute and roughly what mental cost model should
I have? Once I have a BlockFrequency, what does it mean? Some of
this is documented in BlockFrequencyImpl.h, but the high level bits
are mostly missing. Particularly for BranchProbability. <br>
<br>
I chose to write a custom analysis in large part because I didn't
understand the existing analysis and my (possibly completely wrong)
perception is that they're overly precise/expensive for what I
need. I wanted to focus on the writing the transform since that's
the point I actually wanted to discuss. :)<br>
<br>
<blockquote
cite="mid:CAGCO0Kj=brN28yWvH-5yQCQ9-Wa0i1rFX_2eu9S2H8Rbeu6PUg@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>
<div>
<ul>
<li>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>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>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>
</div>
</div>
</blockquote>
I get why you find this a useful mental model, but the transform is
far harder to express this way in the couple of cases I've looked
at. It's much easier to start with a latch, reason about it's
hotness, and then let the generic loop code construct the cold
"region".<br>
<br>
Then again, if you were to ask for the set of latches which were
dominated by blocks in the cold-with-hot-predecessors list, that
might be interesting. But again, I'd really like to start from the
latches since that's what controls the legality/profitability of the
transform. Hm, we could walk back along the dom tree from the latch
looking for such a cwhp block... This might be a better way to think
about the profitability of the transform, even starting from the
latch. Is that what you were trying to get at to start with? Or
were you looking for something more general?<br>
<br>
<blockquote
cite="mid:CAGCO0Kj=brN28yWvH-5yQCQ9-Wa0i1rFX_2eu9S2H8Rbeu6PUg@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div> </div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>
<div>
<ul>
<li>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>I'm somewhat concerned about this, but want to think
more about the fundamental transformation.</div>
<div> </div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>
<div>
<ul>
<li>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>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>
</div>
</div>
</blockquote>
You're welcome. :)<br>
<br>
This might be an area where it's profitable to talk in person, are
you going to be at the social tonight?<br>
<br>
Philip<br>
<br>
</body>
</html>