<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
I agree this approach is possible. I even have an (ancient,
abandoned) patch which started down that path.
<a class="moz-txt-link-freetext" href="https://reviews.llvm.org/D7061">https://reviews.llvm.org/D7061</a><br>
<br>
I view this as being also useful, not a reason not to do the
transform in LICM. We've already spent all the analysis cost, we
might as well use it. <br>
<br>
(Lest it's not clear, I'm assuming that if we did do a separate
LoopPRE pass that we'd have to separate out a AliasSetTrackAnalysis
and handle invalidation properly though the loop pass pipeline.
i.e. not recompute the AST)<br>
<br>
<div class="moz-cite-prefix">On 09/14/2018 04:56 AM, John Brawn
wrote:<br>
</div>
<blockquote type="cite"
cite="mid:DB7PR08MB327322C7692EBAF2B8EF02B08E190@DB7PR08MB3273.eurprd08.prod.outlook.com">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 14 (filtered
medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Tahoma;
panose-1:2 11 6 4 3 5 4 4 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p
{mso-style-priority:99;
mso-margin-top-alt:auto;
margin-right:0cm;
mso-margin-bottom-alt:auto;
margin-left:0cm;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
span.EmailStyle18
{mso-style-type:personal-reply;
font-family:"Calibri","sans-serif";
color:#1F497D;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri","sans-serif";
mso-fareast-language:EN-US;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:615599737;
mso-list-template-ids:-1886478414;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
<div class="WordSection1">
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">For
doing PRE on the load, it looks like there’s only two things
stopping GVN PRE from doing it:<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">*
GVN::PerformLoadPRE doesn’t hoist loads that are
conditional. Probably this can be overcome with some kind of<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">
heuristic that allows it to happen in loops when the blocks
where a load would have to be inserted are outside<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">
the loop.<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">*
IsFullyAvailableInBlock goes around the loop and
double-counts the entry-edge into the loop as unavailable.
I’m<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">
pretty sure this can be easily fixed by marking the block
that PerformLoadPRE calls IsFullyAvailableInBlock on as<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">
FullyAvailable, so it stops there when following the
back-edge.<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">I
did a quick experiment (solving the first problem by just
commenting out that check) and this worked for a simple<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">test
case of<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span
style="font-size:11.0pt;font-family:"Courier
New";mso-fareast-language:EN-US">int x;<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span
style="font-size:11.0pt;font-family:"Courier
New";mso-fareast-language:EN-US">int arr[32];<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span
style="font-size:11.0pt;font-family:"Courier
New";mso-fareast-language:EN-US">void fn(int n) {<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span
style="font-size:11.0pt;font-family:"Courier
New";mso-fareast-language:EN-US"> for (int i = 0; i
< n; i++) {<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span
style="font-size:11.0pt;font-family:"Courier
New";mso-fareast-language:EN-US"> if (arr[i]) {<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span
style="font-size:11.0pt;font-family:"Courier
New";mso-fareast-language:EN-US"> x++;<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span
style="font-size:11.0pt;font-family:"Courier
New";mso-fareast-language:EN-US"> }<o:p></o:p></span></p>
<p class="MsoNormal" style="text-autospace:none"><span
style="font-size:11.0pt;font-family:"Courier
New";mso-fareast-language:EN-US"> }<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Courier
New";mso-fareast-language:EN-US">}</span><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">So
perhaps the load PRE half can be done without a separate
pass.<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D">John<o:p></o:p></span></p>
<p class="MsoNormal"><span
style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1F497D"><o:p> </o:p></span></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0cm
0cm 0cm 4.0pt">
<div>
<div style="border:none;border-top:solid #B5C4DF
1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b><span
style="font-size:10.0pt;font-family:"Tahoma","sans-serif""
lang="EN-US">From:</span></b><span
style="font-size:10.0pt;font-family:"Tahoma","sans-serif""
lang="EN-US"> llvm-dev
[<a class="moz-txt-link-freetext" href="mailto:llvm-dev-bounces@lists.llvm.org">mailto:llvm-dev-bounces@lists.llvm.org</a>]
<b>On Behalf Of </b>Alina Sbirlea via llvm-dev<br>
<b>Sent:</b> 13 September 2018 22:01<br>
<b>To:</b> <a class="moz-txt-link-abbreviated" href="mailto:listmail@philipreames.com">listmail@philipreames.com</a><br>
<b>Cc:</b> <a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<b>Subject:</b> Re: [llvm-dev] Generalizing load/store
promotion in LICM<o:p></o:p></span></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<p class="MsoNormal">For context, I've been looking into
replacing the use of AST (AliasSetTracker) with MemorySSA
in LICM. This works great for sinking/hoisting but does
not apply well for promotion, and one of the solutions I
considered is precisely ripping out the promotion part and
replacing its functionality with a separate PRE pass +
possibly store sinking. FWIW I think that's the right way
to go.<o:p></o:p></p>
<div>
<p class="MsoNormal">I did not get deep enough into
working on the solution but I would gladly have a
detailed discussion to move this forward.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Reading into detail now.<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
<div>
<p class="MsoNormal">Thanks,<o:p></o:p></p>
</div>
<div>
<p class="MsoNormal">Alina<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div>
<p class="MsoNormal">On Thu, Sep 13, 2018 at 1:43 PM
Philip Reames <<a
href="mailto:listmail@philipreames.com"
moz-do-not-send="true">listmail@philipreames.com</a>>
wrote:<o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid #CCCCCC
1.0pt;padding:0cm 0cm 0cm
6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<p class="MsoNormal">(minor inline additions)<br>
<br>
On 09/13/2018 01:51 AM, Chandler Carruth wrote:<br>
<br>
<o:p></o:p></p>
<div>
<p class="MsoNormal">Haven't had time to dig into
this, but wanted to add <a
href="mailto:asbirlea@google.com" target="_blank"
id="m_-2310710337215009520IloFPc-1"
moz-do-not-send="true">+Alina Sbirlea</a> to the
thread as she has been working on promotion and
other aspects of LICM for a long time here.<o:p></o:p></p>
</div>
<p class="MsoNormal">Thanks!<br>
<br>
<o:p></o:p></p>
<div>
<div>
<p class="MsoNormal">On Wed, Sep 12, 2018 at 11:41
PM Philip Reames <<a
href="mailto:listmail@philipreames.com"
target="_blank" moz-do-not-send="true">listmail@philipreames.com</a>>
wrote:<o:p></o:p></p>
</div>
<blockquote style="border:none;border-left:solid
#CCCCCC 1.0pt;padding:0cm 0cm 0cm
6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<p>I'm thinking about making some semi radical
changes to load store promotion works in LICM,
and figured it would be a good idea to get buy
in before I actually started writing code. :)<o:p></o:p></p>
<p>TLDR: legality of sinking stores to exits is
hard, can we separate load handling into a super
aggressive form of PRE, and use predicated
stores to avoid solving legality question?<o:p></o:p></p>
<p><o:p> </o:p></p>
<p>Background<o:p></o:p></p>
<p>We've been seeing an interesting class of
problems recently that looks roughly like this:<o:p></o:p></p>
<p>for (int = 0; i < N; i++)<br>
if (a[i] == 0) // some data dependent check<br>
g_count++; // conditional load and store to
shared location<o:p></o:p></p>
<p>The critical detail in this example is that
g_count is a global location which may be
accessed concurrently* by multiple threads. The
challenge here is that we don't know whether the
store ever executes, and we're not allowed to
insert a store along any path that didn't
originally contain them. Said differently, if
all elements in "a" are non-zero, we're not
allowed to store to g_count. We do know that
the g_count location is dereferenceable though.
<o:p></o:p></p>
<p>(*Please, let's avoid the memory model
derailment here. I'm simplifying and C++
language rules aren't real useful for my Java
language frontend anyways. In practice, all the
access are atomic, but unordered, but we'll
leave that out of discussion otherwise.)<o:p></o:p></p>
<p>I have two approaches I'm considering here.
These are orthogonal, but I suspect we'll want
to implement both.<o:p></o:p></p>
<p><o:p> </o:p></p>
<p>Proposal A - Use predicated stores in loop
exits<o:p></o:p></p>
<p>The basic idea is that we don't worry about
solving the legality question above, and just
insert a store which is predicated on a
condition which is true exactly when the
original store ran. In pseudo code, this looks
something like:<o:p></o:p></p>
<p>bool StoreLegal = false;<br>
int LocalCount = g_count;<br>
for (int = 0; i < N; i++)<br>
if (a[i] == 0) {<br>
LocalCount++;<br>
StoreLegal = true;<br>
}<br>
if (StoreLegal) g_count = LocalCount; <o:p></o:p></p>
<p>There are two obvious concerns here:<o:p></o:p></p>
<ol start="1" type="1">
<li class="MsoNormal"
style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l0
level1 lfo1">
The predicated store might be expensive in
practice - true for most current
architectures.<o:p></o:p></li>
<li class="MsoNormal"
style="mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;mso-list:l0
level1 lfo1">
We''re introducing an extra boolean phi cycle
around the loop. <o:p></o:p></li>
</ol>
<p>Talking to a couple of folks offline at the
socials over the last few months, the former
seems to be the main objection. I think we can
control this by restricting this transform to
when the loop is believed to have a high trip
count and the conditional path is taken with
some frequency. Getting feedback on this
particular point is one of my main reasons for
writing this mail.
<o:p></o:p></p>
<p>The second objection can frequently be resolved
by finding other expressions which evaluate to
the same boolean. (In this case, if LocalCount
!= LocalCountOrig assuming i doesn't overflow.)
We already have a framework with SCEV to do
these replacements. Though, from some quick
testing, it would definitely need
strengthening. However, SCEV can't remove the
extra phi in all cases, so we have to be okay
with the extra phi cycle in the general case.
This seems worthwhile to me, but thoughts?<o:p></o:p></p>
<p><o:p> </o:p></p>
<p>Proposal B - Separate load and store handling
into distinct transforms<o:p></o:p></p>
<p>(For folks I've discussed this with before,
this part is all new.)<o:p></o:p></p>
<p>Thinking about the problem, it finally occurred
to me that we can decompose the original example
into two steps: getting the loads out of the
loop, and sinking the stores out of the loop.
If we can accomplish the former, but not the
later, we've still made meaningful progress. <o:p></o:p></p>
<p>So, what'd we'd essentially have is a load only
transformation which produces this:<br>
int LocalCount = g_count;<br>
for (int = 0; i < N; i++)<br>
if (a[i] == 0) {<br>
LocalCount++;<br>
g_count = LocalCount;<br>
}<o:p></o:p></p>
<p>At this point, we've reduced memory traffic by
half, and opened up the possibility that other
parts of the optimizer can exploit the
simplified form. The last point is particular
interesting since we generally try to
canonicalize loads out of loops, and much of the
optimizer is tuned for a form with as much as
possible being loop invariant. As one example,
completely by accident, there's some work going
on in the LoopVectorizer right now to handle
such stores to loop invariant addresses during
vectorization. Putting the two pieces together
would let us fully vectorize this loop without
needing to sink the stores at all.
<o:p></o:p></p>
<p>In practice, the existing implementation in
LICM would cleanly split along these lines with
little problem.
<o:p></o:p></p>
<p>One way of looking at this load specific
transform is as an extreme form of PRE (partial
redundancy elimination). Our current PRE
implementation doesn't handle cases this
complicated.
<o:p></o:p></p>
</div>
</blockquote>
</div>
<p class="MsoNormal">It occurred to my later that simply
framing the new transform as a separate pass (LoopPRE)
and using the same AST + SSA construction approach
would be straight forward. So, if folks think that
having an aggressive form of load PRE in LICM is going
a bit too far, it'd be easy to represent as an
optional separate pass. I'd still prefer having LICM
contain the logic though.
<br>
<br>
<o:p></o:p></p>
<div>
<blockquote style="border:none;border-left:solid
#CCCCCC 1.0pt;padding:0cm 0cm 0cm
6.0pt;margin-left:4.8pt;margin-right:0cm">
<div>
<p>Thoughts?<o:p></o:p></p>
</div>
<div>
<p>Philip<o:p></o:p></p>
</div>
</blockquote>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</blockquote>
</div>
</div>
</div>
</blockquote>
<br>
</body>
</html>