<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'><br><hr id="zwchr"><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><b>From: </b>"Chandler Carruth" <chandlerc@google.com><br><b>To: </b>"Hal Finkel" <hfinkel@anl.gov><br><b>Cc: </b>"Hyojin Sung" <hsung@us.ibm.com>, llvmdev@cs.uiuc.edu<br><b>Sent: </b>Thursday, July 16, 2015 1:06:03 AM<br><b>Subject: </b>Re: [LLVMdev] Improving loop vectorizer support for loops with a volatile iteration variable<br><br><div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Wed, Jul 15, 2015 at 6:36 PM Hal Finkel <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div><div style="font-family: arial,helvetica,sans-serif; font-size: 10pt; color: rgb(0, 0, 0);"><br><hr><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><b>From: </b>"Chandler Carruth" <<a href="mailto:chandlerc@google.com" target="_blank">chandlerc@google.com</a>><br><b>To: </b>"Hyojin Sung" <<a href="mailto:hsung@us.ibm.com" target="_blank">hsung@us.ibm.com</a>>, <a href="mailto:llvmdev@cs.uiuc.edu" target="_blank">llvmdev@cs.uiuc.edu</a><br><b>Sent: </b>Wednesday, July 15, 2015 7:34:54 PM<br><b>Subject: </b>Re: [LLVMdev] Improving loop vectorizer support for loops with a volatile iteration variable</blockquote></div></div><div><div style="font-family: arial,helvetica,sans-serif; font-size: 10pt; color: rgb(0, 0, 0);"><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><br><br><div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Wed, Jul 15, 2015 at 12:55 PM Hyojin Sung <<a href="mailto:hsung@us.ibm.com" target="_blank">hsung@us.ibm.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div>
<p><font size="2" face="Helvetica">Hi all,</font><br>
<br>
<font size="2" face="Helvetica">I would like to propose an improvement of the “almost dead” block elimination in Transforms/Local.cpp so that it will preserve the canonical loop form for loops with a volatile iteration variable.</font><br>
<br>
<font size="2" face="Helvetica">*** Problem statement</font><br>
<font size="2" face="Helvetica">Nested loops in LCALS Subset B (</font><a href="https://urldefense.proofpoint.com/v2/url?u=https-3A__codesign.llnl.gov_LCALS.php&d=AwMGaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=aWKfvN4c8lvUSvVn8J0Z2ajTctlBJf0198Au28epBr0&s=4d9dt5ODcDWHHatSrwu5ZYT9ebgVzNEtpOlIR87izCM&e=" target="_blank"><font size="2" face="Helvetica"><u>https://codesign.llnl.gov/LCALS.php</u></font></a><font size="2" face="Helvetica">) are not vectorized with LLVM -O3 because the LLVM loop vectorizer fails the test whether the loop latch and exiting block of a loop is the same. The loops are vectorizable, and get vectorized with LLVM -O2</font></p></div></blockquote><div>I would be interested to know why -O2 succeeds here.</div><div> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div><p><font size="2" face="Helvetica"> and also with other commercial compilers (icc, xlc). </font><br>
<br>
<font size="2" face="Helvetica">*** Details</font><br>
<font size="2" face="Helvetica">These loops ended up with different loop latch and exiting block after a series of optimizations including loop unswitching, jump threading, simplify-the-CFG, and loop simplify. The fundamental problem here is that the above optimizations cannot recognize a loop with a volatile iteration variable and do not preserve its canonical loop structure.</font></p></div></blockquote><div>Ok, meta-level question first:</div><div><br></div><div>Why do we care about performance of loops with a volatile iteration variable? </div></div></div></blockquote></div></div><div><div style="font-family: arial,helvetica,sans-serif; font-size: 10pt; color: rgb(0, 0, 0);"><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"></blockquote>I don't think we do, however, I think that misses the point. In this case, the volatile iteration variable is just an easy way to expose this problem that we have with nested loop canonicalization and the vectorizer. To be specific:<br><br>This we vectorizer just fine:<br><br>void foo1(float * restrict x, float * restrict y, float * restrict z) {<br> for (int i = 0; i < 1000; ++i) {<br> for (int j = 0; j < 1600; ++j) {<br> x[j] = y[j] + z[j];<br> }<br> }<br>}<br><br>And, indeed, this we don't (the only change is adding volatile on i):<br><br>void foo2(float * restrict x, float * restrict y, float * restrict z) {<br> for (volatile int i = 0; i < 1000; ++i) {<br> for (int j = 0; j < 1600; ++j) {<br> x[j] = y[j] + z[j];<br> }<br> }<br>}<br><br>However, this we don't either, and that's a big problem:<br><br>int done(float *x, float *y, float *z);<br>void foo3(float * restrict x, float * restrict y, float * restrict z) {<br> while (!done(x, y, z)) {<br> for (int j = 0; j < 1600; ++j) {<br> x[j] = y[j] + z[j];<br> }<br> }<br>}<br><br>And the underlying reason is the same. The IR at the point in time when the loop vectorizer runs looks like this:<br><br>define void @foo3(float* noalias %x, float* noalias %y, float* noalias %z) #0 {<br>entry:<br> %call.14 = tail call i32 @done(float* %x, float* %y, float* %z) #1<br> %lnot.15 = icmp eq i32 %call.14, 0<br> br i1 %lnot.15, label %for.body.preheader, label %while.end<br><br>for.body.preheader: ; preds = %entry<br> br label %for.body<br><br>while.cond.loopexit: ; preds = %for.body<br> %call = tail call i32 @done(float* %x, float* %y, float* %z) #1<br> %lnot = icmp eq i32 %call, 0<br> br i1 %lnot, label %for.body.backedge, label %while.end.loopexit<br><br>for.body: ; preds = %for.body.backedge, %for.body.preheader<br> %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %<a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__indvars.iv.be&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=OE36IJuCyZctA3s37X7WGup5iAkOM11AM2CnhP5TBUk&s=JDHk2pO2X8ONZI6T-EtaJWjtJLzbBdKTvULQ6Te-xGI&e=" target="_blank">indvars.iv.be</a>, %for.body.backedge ]<br> ...<br> %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1<br> %exitcond = icmp eq i64 %indvars.iv.next, 1600<br> br i1 %exitcond, label %while.cond.loopexit, label %for.body.backedge<br><br>for.body.backedge: ; preds = %for.body, %while.cond.loopexit<br> %<a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__indvars.iv.be&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=OE36IJuCyZctA3s37X7WGup5iAkOM11AM2CnhP5TBUk&s=JDHk2pO2X8ONZI6T-EtaJWjtJLzbBdKTvULQ6Te-xGI&e=" target="_blank">indvars.iv.be</a> = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %while.cond.loopexit ]<br> br label %for.body<br><br>while.end.loopexit: ; preds = %while.cond.loopexit<br> br label %while.end<br><br>while.end: ; preds = %while.end.loopexit, %entry<br> ret void<br>}<br><br>and we can currently only vectorize loops where the loop latch is also the loop's exiting block. In this case, as in the case with the volatile variable, vectorization is blocked by this constraint (here the backedge is from the terminator of %for.body.backedge, but the loop exiting block is %for.body). The check in the vectorizer is explicit:<br><br> // We only handle bottom-tested loops, i.e. loop in which the condition is<br> // checked at the end of each iteration. With that we can assume that all<br> // instructions in the loop are executed the same number of times.<br> if (TheLoop->getExitingBlock() != TheLoop->getLoopLatch()) {<br> ...<br></div></div></blockquote><div><br></div><div>Thanks for the detailed explanation. This makes much more sense why we need to handle it. I think its much better to look at nested loops of this form than anything to do with volatile -- the latter is too prone to other random optimizations turning off.</div><div><br></div><div>Regarding this problem, it would be interesting to know based on this explanation what the desired fix would be. I see at least these options:</div><div><br></div><div id="DWT29978">1) Canonicalize loops harder to make them look the way the vectorizer wants. If this can be done without causing significant problems, it seems likely the best approach.</div></div></div></blockquote>I agree. In this case, we could certainly fold the trivial %for.body.backedge block into %for.body, meaning transforming this:<br><br>for.body.backedge: ; preds = %while.cond.loopexit, %for.body<br> %indvars.iv.be = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %while.cond.loopexit ]<br> br label %for.body<br><br>for.body: ; preds = %for.body.backedge, %for.body.preheader<br> %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.be, %for.body.backedge ]<br> ...<br> %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1<br> %exitcond = icmp eq i64 %indvars.iv.next, 1600<br> br i1 %exitcond, label %while.cond.loopexit, label %for.body.backedge<br><br>into this:<br>
<br>
for.body: ; preds = %for.body.backedge, %for.body.preheader<br> %indvars.iv.be = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %while.cond.loopexit ]<br>
%indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.be, %for.body ]<br>
...<br>
%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1<br>
%exitcond = icmp eq i64 %indvars.iv.next, 1600<br>
br i1 %exitcond, label %while.cond.loopexit, label %for.body<br><br>and this seems pretty trivial when %for.body.backedge is completely empty (as in this case), but if it had non-PHI instructions in it on which the existing PHIs in %for.body depended, then maybe this becomes less trivial?<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><div dir="ltr"><div class="gmail_quote"><div></div><div><br></div><div id="DWT29977">2) Teach the vectorizer to vectorize without this constraint by instead establishing the actual invariant it cares about.</div></div></div></blockquote>It really cares that there's no code that comes in between the latch and the exit, because such code is not really part of the loop (it only runs once), or code in between the exit and the latch (because such code runs in one fewer iterations than the code before the exit). At least nothing with side effects I presume.<br><br> -Hal<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><div dir="ltr"><div class="gmail_quote"><div></div><div><br></div><div>Maybe there is another strategy? </div><div><br></div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div><div style="font-family: arial,helvetica,sans-serif; font-size: 10pt; color: rgb(0, 0, 0);"> -Hal<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"></blockquote></div></div><div><div style="font-family: arial,helvetica,sans-serif; font-size: 10pt; color: rgb(0, 0, 0);"><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><div dir="ltr"><div class="gmail_quote"><div>That seems both counter-intuitive and unlikely to be a useful goal. We simply don't optimize volatile operations well in *any* part of the optimizer, and I'm not sure why we need to start trying to fix that. This seems like an irreparably broken benchmark, but perhaps there is a motivation I don't yet see.</div><div><br></div><div><br></div><div>Assuming that sufficient motivation arises to try to fix this, see my comments below:</div><div> </div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"><div><p><br>
<br>
<font size="2" face="Helvetica">(1) Loop unswitching generates several empty placeholder BBs only with PHI nodes after separating out a shorter path with no inner loop execution from a standard path. </font><br>
<br>
<font size="2" face="Helvetica">(2) Jump threading and simplify-the-CFG passes independently calls TryToSimplifyUnconditionalBranchFromEmptyBlock() in Transforms/Utils/Local.cpp to get rid of almost empty BBs. </font><br>
<br>
<font size="2" face="Helvetica">(3) TryToSimplifyUnconditionalBranchFromEmtpyBlock() eliminates the placeholder BBs after loop unswitching and merges them into subsequent blocks including the header of the inner loop. Before eliminating the blocks, the function checks if the block is a loop header by looking at its PHI nodes so that it can be saved, but the test fails with the loops with a volatile iteration variable.</font></p></div></blockquote><div>Why does this fail for a volatile iteration variable but not for a non-volatile one? I think understanding that will be key to understanding how it should be fixed.</div></div></div>
<br></blockquote></div></div><div><div style="font-family: arial,helvetica,sans-serif; font-size: 10pt; color: rgb(0, 0, 0);"><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;">_______________________________________________<br>LLVM Developers mailing list<br><a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br></blockquote></div></div><div><div style="font-family: arial,helvetica,sans-serif; font-size: 10pt; color: rgb(0, 0, 0);"><br><br><br>-- <br><div><span></span>Hal Finkel<br>Assistant Computational Scientist<br>Leadership Computing Facility<br>Argonne National Laboratory<span></span><br></div></div></div></blockquote></div></div>
</blockquote><br><br><br>-- <br><div><span name="x"></span>Hal Finkel<br>Assistant Computational Scientist<br>Leadership Computing Facility<br>Argonne National Laboratory<span name="x"></span><br></div></div></body></html>