<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/12/2015 08:28 PM, Xinliang David
Li wrote:<br>
</div>
<blockquote
cite="mid:CALRgJCP+fNZe+YTxx3fNAAmy4mMg_46e1xBWESy12166_ZAp5A@mail.gmail.com"
type="cite">
<div dir="ltr"><br>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Thu, Jan 8, 2015 at 12:33 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"><span
class=""><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>
</div>
</div>
</div>
</blockquote>
Could you define the term "downsafe"? I think I know what you mean,
but just to be clear. <br>
<blockquote
cite="mid:CALRgJCP+fNZe+YTxx3fNAAmy4mMg_46e1xBWESy12166_ZAp5A@mail.gmail.com"
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>
Yep. In LLVM, this basically requires that this->FIELD be known
deferenceable. I filled one simple bug for this here:
<a class="moz-txt-link-freetext" href="http://llvm.org/bugs/show_bug.cgi?id=22266">http://llvm.org/bugs/show_bug.cgi?id=22266</a><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>
<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>
<br>
<br>
<blockquote
cite="mid:CALRgJCP+fNZe+YTxx3fNAAmy4mMg_46e1xBWESy12166_ZAp5A@mail.gmail.com"
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:0 0 0
.8ex;border-left:1px #ccc 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>
I think "a little tricky" might be an understatement here. <br>
<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.)<br>
<br>
Philip<br>
</body>
</html>