<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/11/2015 10:35 PM, Daniel Berlin
wrote:<br>
</div>
<blockquote
cite="mid:CAF4BwTXbAC7JiNy6J_DWOeoNiCV-YO+wCvsNUK+wFbyZAjomTA@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 dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
<div>Looking at what LLVM does, the failing on the
PRE side is that our PRE/GVN models are not strong
enough to handle this. I'm not sure at all why we
think anything else is necessary. </div>
</div>
</div>
</div>
</blockquote>
<div><br>
</div>
<div>By this i mean we don't actually perform real PRE for
loads. It's a known deficiency and one that does not
require any duplicate heuristics to solve.</div>
<div>Right now we perform some availability based removal
that happens be willing to do an insertion here or there
to try to move a load in some cases (it will only do a
single insertion). It's not also based on real
availability, but on finding nearest dependencies of loads
and squinting at them (which is not even really the same
as finding where a load stops being available) funny.</div>
<div><br>
</div>
<div>It's also not real PRE, just some code that is willing
to insert one load to move a load.</div>
</div>
</div>
</div>
</blockquote>
Er, I think we have a terminology problem here. From what I can
gather, our current implementation *is* an implementation of classic
PRE. It's more or less directly organized around the classic
"available" and "anticipated" concepts from the literature. The
*implementation* has some limitations, but the conceptual framework
is there*. One of the key invariants in classic PRE is that you do
not change program behaviour on any path. As a result, moving (or
at most duplicating) loads is pretty much all that happens.<br>
<br>
* It took me a few hours of squinting at the code to recognize that
weird backwards walk as being an implementation of "anctipated", but
it is. The "available" part comes from MemoryDependenceAnalysis and
the forward dataflow algorithm based on those inputs.<br>
<br>
If you want to start inserting loads on paths which didn't
previously have them - for example the loop preheader in your
example in the previous email - this is not classic PRE as I'm
familiar with it. It can be very profitable and worthwhile, but is
not classic PRE. I'm not sure what this variant is known as in the
literature. <br>
<br>
(If I'm being overly pedantic here, or just flat out wrong, please
say so. I'm still exploring related material and am trying to
categorize things in my own head.)<br>
<br>
I think we actually in reasonable agreement that we do need to move
beyond 'classic PRE' as I called it above. If you have specific
suggestions, positive or negative examples, or other thoughts to
share, I'd very much value the input. <br>
<blockquote
cite="mid:CAF4BwTXbAC7JiNy6J_DWOeoNiCV-YO+wCvsNUK+wFbyZAjomTA@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
<div>If you want this case to work, what you need is a real
Load PRE implementation, not one based on simple memdep
based load moving.</div>
</div>
</div>
</div>
</blockquote>
<blockquote
cite="mid:CAF4BwTXbAC7JiNy6J_DWOeoNiCV-YO+wCvsNUK+wFbyZAjomTA@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
<div>Trying to hack this one up with profile guided code
duplication, etc, to get it to kinda sorta work seems to
me to be a bad idea.</div>
</div>
</div>
</div>
</blockquote>
Not sure I really agree here, but I'm open to pushing as far as we
can with static heuristics first. I suspect that's likely to be
more stable w.r.t. optimization effect and applicable to more
cases. <br>
<blockquote
cite="mid:CAF4BwTXbAC7JiNy6J_DWOeoNiCV-YO+wCvsNUK+wFbyZAjomTA@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 dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div>It's certainly not requiring special code
duplication heuristics, etc.</div>
<div><br>
</div>
<div>So either you are thinking of a case that is
different from the above, or I am seriously
confused :)</div>
</div>
</div>
</div>
</blockquote>
</div>
<br>
</div>
</div>
</blockquote>
<br>
</body>
</html>