<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<blockquote style="border-left: 3px solid rgb(200, 200, 200); border-top-color: rgb(200, 200, 200); border-right-color: rgb(200, 200, 200); border-bottom-color: rgb(200, 200, 200); padding-left: 1ex; margin-left: 0.8ex; color: rgb(102, 102, 102);">
<div style="">
<div style="font-family: Calibri, Arial, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
</div>
<div>
<hr tabindex="-1" style="display:inline-block; width:98%">
<div id="divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" color="#000000" style="font-size:11pt"><b>From:</b> llvm-dev <llvm-dev-bounces@lists.llvm.org> on behalf of Mikael Holmén via llvm-dev <llvm-dev@lists.llvm.org><br>
<b>Sent:</b> Tuesday, May 5, 2020 8:25 AM<br>
<b>To:</b> llvm-dev@lists.llvm.org <llvm-dev@lists.llvm.org><br>
<b>Subject:</b> [llvm-dev] Missing vectorization of loop due to load late in the loop</font>
<div> </div>
</div>
<div class="BodyFragment"><font size="2"><span style="font-size:11pt">
<div class="PlainText">Hi,<br>
<br>
TL;DR: A loop doesn't get vectorized due to the interaction of loop-<br>
rotate, licm and instcombine. What to do about it?<br>
<br>
<br>
Full story:<br>
<br>
In the benchmarks for our out-of-tree target we have a case that we<br>
would like to get vectorized, but currently it isn't. I've done some<br>
digging to see why and have some kind of idea what prevents it, but I<br>
don't know what the best way to fix it would be so I thought I'd share<br>
a reduced version of it to see if anyone here have ideas.<br>
<br>
So, what happens can be reproduced on trunk with<br>
opt -O3 -S -o - bbi-39227-reduced.ll<br>
<br>
The input program consists of two nested loops where the inner loop<br>
loads a value and does some calculations and then the outer loop writes<br>
the calculated value somewhere.<br>
<br>
With<br>
-debug-only=loop-vectorize<br>
<br>
I see this printout from the vectorizer for the inner loop:<br>
LV: Not vectorizing: Found an unidentified PHI %h.15 = phi i32 [<br>
%h.11, %inner.cond.preheader ], [ %h.1, %inner.body ]<br>
<br>
When we run the vectorizer the inner loop looks like<br>
<br>
inner.body: ; preds =<br>
%inner.cond.preheader, %inner.body<br>
%h.15 = phi i32 [ %h.11, %inner.cond.preheader ], [ %h.1, %inner.body<br>
]<br>
%h.pn4 = phi i32* [ %h, %inner.cond.preheader ], [ %hp.1, %inner.body<br>
]<br>
%j.03 = phi i16 [ 0, %inner.cond.preheader ], [ %j.1, %inner.body ]<br>
%real.02 = phi i32 [ 0, %inner.cond.preheader ], [ %sub, %inner.body<br>
]<br>
%hp.1 = getelementptr inbounds i32, i32* %h.pn4, i64 1<br>
%0 = shl i32 %h.15, 16<br>
%conv7 = ashr exact i32 %0, 16<br>
%add = sub i32 %real.02, %h.15<br>
%sub = add i32 %add, %conv7<br>
%j.1 = add nuw nsw i16 %j.03, 1<br>
%h.1 = load i32, i32* %hp.1, align 1, !tbaa !4<br>
%cmp3 = icmp ult i16 %j.03, 99<br>
br i1 %cmp3, label %inner.body, label %inner.end, !llvm.loop !8<br>
<br>
And the vectorizer bails out since the load is placed "late" in the<br>
loop, so<br>
RecurrenceDescriptor::isFirstOrderRecurrence<br>
returns false.<br>
<br>
If we just move the load before the definition of %0 in the vectorizer<br>
input, then we instead get<br>
</div>
<div class="PlainText"> LV: We can vectorize this loop!<br>
</div>
</span></font></div>
</div>
</blockquote>
<div class="PlainText"><br>
</div>
<div class="PlainText">That just seems like a bug. Unless I'm missing something, the load depends only on %hp.1, there are no use-def or memory dependencies in between the load and the phi. The semantics are exactly the same between the two placements of the
load instruction. The order of independent SSA calculations should not affect whether or not the vectorizer is able to vectorize the loop.</div>
<div class="PlainText"><br>
</div>
<div class="PlainText"> -Hal</div>
<div class="PlainText"><br>
</div>
<div class="PlainText"><br>
</div>
<blockquote style="border-left: 3px solid rgb(200, 200, 200); border-top-color: rgb(200, 200, 200); border-right-color: rgb(200, 200, 200); border-bottom-color: rgb(200, 200, 200); padding-left: 1ex; margin-left: 0.8ex; color: rgb(102, 102, 102);">
<div>
<div class="BodyFragment"><font size="2"><span style="font-size:11pt">
<div class="PlainText"><br>
Originally the loop had two loads, and then one of them was actually<br>
placed early in the loop block. That was done by instcombine, by <br>
InstCombiner::FoldPHIArgLoadIntoPHI.<br>
<br>
The reason this doesn't happen for the load we see in the reduced<br>
example is because after loop rotation licm hoists the start value of<br>
the PHI, so when instcombine tries to do FoldPHIArgLoadIntoPHI, the<br>
start value isn't placed in the direct predecessor block of the PHI,<br>
and the folding is aborted.<br>
<br>
Therefore I tried to squeeze in an additional run of instcombine before<br>
the licm run that does that hoisting, and then instcombine does the<br>
folding and the load in the inner loop is done early instead of late in<br>
the loop. The vectorizer then is happy and accepts to vectorize the<br>
loop. I have no idea if inserting another run of instcombine is a good<br>
idea though and I see some mixed results in other benchmarks.<br>
<br>
So, the question is what really to do about this...<br>
<br>
Should the vectorizer vectorize the loop anyway in this case?<br>
<br>
Should licm not hoist the initial value of the PHI (but hoisting is in<br>
general nice, so...).<br>
<br>
Should instcombine realize it can do something about this case even if<br>
the initial value of the PHI is "far" from the PHI.<br>
<br>
Something completely different?<br>
<br>
Any ideas?<br>
<br>
Thanks,<br>
Mikael<br>
</div>
</span></font></div>
</div>
</blockquote>
<div>
<div class="BodyFragment"><font size="2"><span style="font-size:11pt">
<div class="PlainText"></div>
</span></font></div>
</div>
</body>
</html>