<html>
<head>
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<br>
<div class="moz-cite-prefix">On 01/12/2015 10:35 AM, Mehdi Amini
wrote:<br>
</div>
<blockquote
cite="mid:C1D28AEA-6208-475B-A2D1-C1F6F97CDD7C@apple.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=windows-1252">
<br class="">
<div>
<blockquote type="cite" class="">
<div class="">On Jan 12, 2015, at 10:08 AM, Philip Reames <<a
moz-do-not-send="true"
href="mailto:listmail@philipreames.com" class="">listmail@philipreames.com</a>>
wrote:</div>
<br class="Apple-interchange-newline">
<div class="">
<meta content="text/html; charset=windows-1252"
http-equiv="Content-Type" class="">
<div bgcolor="#FFFFFF" text="#000000" class=""> <br
class="">
<div class="moz-cite-prefix">On 01/11/2015 10:35 PM,
Daniel Berlin wrote:<br class="">
</div>
<blockquote
cite="mid:CAF4BwTXbAC7JiNy6J_DWOeoNiCV-YO+wCvsNUK+wFbyZAjomTA@mail.gmail.com"
type="cite" class="">
<div dir="ltr" class="">
<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" class="">
<div class="gmail_extra">
<div class="gmail_quote">
<div class=""><br class="">
</div>
<div class="">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 class=""><br class="">
</div>
<div class="">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 class="">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 class=""><br class="">
</div>
<div class="">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 class="">
<br class="">
* 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. </div>
</div>
</blockquote>
<div><br class="">
</div>
<div>Did you add some comments? It may save a few hours of
squinting to someone else in the future :)</div>
</div>
</blockquote>
Not yet, but yes, I plan to.<br>
<br>
Having said that, part of my trouble was that I didn't have the
background to understand what I was seeing at first. I had to go do
some literature search and then things made (slightly) more sense.
<br>
<blockquote
cite="mid:C1D28AEA-6208-475B-A2D1-C1F6F97CDD7C@apple.com"
type="cite">
<div>
<div><br class="">
</div>
<div>Mehdi</div>
<div><br class="">
</div>
<div><br class="">
</div>
<br class="">
<blockquote type="cite" class="">
<div class="">
<div bgcolor="#FFFFFF" text="#000000" class="">The
"available" part comes from MemoryDependenceAnalysis and
the forward dataflow algorithm based on those inputs.<br
class="">
<br class="">
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
class="">
<br class="">
(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 class="">
<br class="">
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 class="">
<blockquote
cite="mid:CAF4BwTXbAC7JiNy6J_DWOeoNiCV-YO+wCvsNUK+wFbyZAjomTA@mail.gmail.com"
type="cite" class="">
<div dir="ltr" class="">
<div class="gmail_extra">
<div class="gmail_quote">
<div class=""><br class="">
</div>
<div class="">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" class="">
<div dir="ltr" class="">
<div class="gmail_extra">
<div class="gmail_quote">
<div class=""><br class="">
</div>
<div class="">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 class="">
<blockquote
cite="mid:CAF4BwTXbAC7JiNy6J_DWOeoNiCV-YO+wCvsNUK+wFbyZAjomTA@mail.gmail.com"
type="cite" class="">
<div dir="ltr" class="">
<div class="gmail_extra">
<div class="gmail_quote">
<div class=""> </div>
<blockquote class="gmail_quote" style="margin:0 0
0 .8ex;border-left:1px #ccc
solid;padding-left:1ex">
<div dir="ltr" class="">
<div class="gmail_extra">
<div class="gmail_quote">
<div class="">It's certainly not requiring
special code duplication heuristics,
etc.</div>
<div class=""><br class="">
</div>
<div class="">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 class="">
</div>
</div>
</blockquote>
<br class="">
</div>
_______________________________________________<br class="">
LLVM Developers mailing list<br class="">
<a moz-do-not-send="true" href="mailto:LLVMdev@cs.uiuc.edu"
class="">LLVMdev@cs.uiuc.edu</a> <a
moz-do-not-send="true" href="http://llvm.cs.uiuc.edu"
class="">http://llvm.cs.uiuc.edu</a><br class="">
<a moz-do-not-send="true"
href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev"
class="">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br
class="">
</div>
</blockquote>
</div>
<br class="">
</blockquote>
<br>
</body>
</html>