<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jan 19, 2015 at 5:55 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/12/2015 08:28 PM, Xinliang David
Li wrote:<br>
</div>
</span><blockquote type="cite">
<div dir="ltr"><br>
<div class="gmail_extra"><br>
<div class="gmail_quote"><span class="">On Thu, Jan 8, 2015 at 12:33 PM,
Philip Reames <span dir="ltr"><<a href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.com</a>></span>
wrote:<br>
</span><span class=""><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"><span><br>
</span>Let's start with a toy example:<br>
while(c) {<br>
x = this->x;<br>
y = this->y;<br>
if (x == y) {<br>
rare();<br>
}<br>
}<br>
<br>
</blockquote>
<div><br>
</div>
<div>With profile info, speculative PRE can be performed for
memory access that are not downsafe:</div>
</span></div>
</div>
</div>
</blockquote>
Could you define the term "downsafe"? I think I know what you mean,
but just to be clear. <br></div></blockquote><div><br></div><div>see the SSAPRE paper: <a href="http://www.cse.unsw.edu.au/~cs4133/Papers/ssapre.toplas97.pdf">http://www.cse.unsw.edu.au/~cs4133/Papers/ssapre.toplas97.pdf</a> </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"><span class="">
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
<div>temp_c = c;</div>
<div>if (temp_c)</div>
<div>{</div>
<div> x = this->x;</div>
<div> y = this->y;</div>
<div>}</div>
<div>while (temp_c) {</div>
<div> if (x == y)</div>
<div> {</div>
<div> rare();</div>
<div> x = this->x;</div>
<div> y = this->y;</div>
<div> }</div>
<div> temp_c = c;</div>
<div>}</div>
<div><br>
</div>
<div>If you can prove this->x etc are safe control
speculative (e.g, seen a dominating memory access with the
same base and offset), it can be </div>
<div><br>
</div>
<div>x = this->x;</div>
<div>y = this->y;</div>
<div>while (c) {</div>
<div> if (x == y) {</div>
<div> rare();</div>
<div> x = this->x;</div>
<div> y = this->y;</div>
<div> }</div>
<div> }</div>
</div>
</div>
</div>
</blockquote></span>
Yep. In LLVM, this basically requires that this->FIELD be known
deferenceable. I filled one simple bug for this here:
<a href="http://llvm.org/bugs/show_bug.cgi?id=22266" target="_blank">http://llvm.org/bugs/show_bug.cgi?id=22266</a></div></blockquote><div><br></div><div>What you proposed in the bug is basically profitability heuristics for speculative PRE.</div><div> </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"><br>
<br>
I've also looked a more general rewrite of our PRE algorithm when a
pointer is known dereferenceable, but I haven't figured out to judge
profitability accurately (yet). The general approach was to just
take the cut provided by MDA, apply "obvious" improvements (i.e.
local merge points), the insert loads in all the unavailable blocks
if it looked profitable. <br></div></blockquote><div><br></div><div>See also paper "<strong style="color:rgb(0,0,0);font-family:Arial,Helvetica,sans-serif;font-size:1em">Register promotion by sparse partial redundancy elimination of loads and stores" for a simple way of evaluating speculation savings.</strong></div><div> </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">
<br>
The alternate approach did have the appeal of being "easy" in cases
where our current approach (work backwards from load) is "hard". <br>
<br>
One challenge is in making sure the two algorithms together generate
a stable final form. :)<br>
<br>
That last part is where I stalled. I'm trying to see what else I
can do with simpler things before returning to that approach. <br>
<br>
Nick Lewicky also pointed out that PHITranslation is problematic in
the current code. Oddly, I've never seen that in practice. We
clearly have different workloads, but I haven't figured out which
are the important different properties yet. <br><span class="">
<br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
<div><br>
</div>
<div> <br>
</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">If we'd
split this into a loop nest structure, we'd still have the
chain, but a) that's easier to control with a custom pass
order since LICM and LoopUnswitch are far cheaper than
GVN/PRE and b) having LICM do a bit of trivial loop
unswitch for the terminator of the header appears quite
tractable.<br>
</blockquote>
<div><br>
</div>
<div><br>
</div>
<div>if (c)</div>
<div>{</div>
<div> x = this->x;</div>
<div> if (!x) return;</div>
<div> y = this->y;</div>
<div> if (!y) return;</div>
<div>}</div>
<div>while (c) {</div>
<div> if (x == y) {</div>
<div> rare();</div>
<div> if (!x) return;</div>
<div> if (!y) return;</div>
<div> }</div>
<div>}</div>
<div><br>
</div>
<div>The 'branch PRE' (hoisting, sinking, assertion prop and
branch elimination) part is a little tricky to do though.</div>
</div>
</div>
</div>
</blockquote></span>
I think "a little tricky" might be an understatement here. <br></div></blockquote><div><br></div><div>agreed.</div><div> </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">
<br>
At least to start with, I'd probably try to handle simple cases.
Even just doing trivial loop unswitch in the loop with LoadPRE would
unlock a lot. (Right now, I'm just running LICM and Unswitch in a
loop. It's not that expensive, gets a lot of cases, but doesn't get
everything.)</div></blockquote><div><br></div><div>Have fun with it :)</div><div><br></div><div>David </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"><span class=""><font color="#888888"><br>
<br>
Philip<br>
</font></span></div>
</blockquote></div><br></div></div>