<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jan 8, 2015 at 2:37 PM, Philip Reames <span dir="ltr"><<a href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>></span> wrote:<br><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"><span class="">
<br>
<div>On 01/07/2015 05:33 PM, Chandler
Carruth wrote:<br>
</div>
<blockquote 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 href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>></span>
wrote:<br>
<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">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></span>
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. </div></blockquote><div><br></div><div><a href="http://webdocs.cs.ualberta.ca/~amaral/papers/BartonCC05.pdf">http://webdocs.cs.ualberta.ca/~amaral/papers/BartonCC05.pdf</a></div><div><br></div><div>This is essentially index set splitting with the goal of it being an enabling optimization for LICM.</div></div><br></div><div class="gmail_extra">(At least, as i've seen it implemented in other compilers)<br><br></div></div>