<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<p><br>
</p>
<br>
<div class="moz-cite-prefix">On 12/21/2017 12:24 PM, Ariel
Ben-Yehuda via llvm-dev wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CAJrJsjf+oMidcQYntShUguF2_cuq9cfJbKL1mSGuZE4vaLLgJA@mail.gmail.com">
<div dir="ltr">
<div>
<div>
<div>Hi,<br>
<br>
</div>
This is Ariel from the Rust team again.<br>
<br>
</div>
I am having another pass ordering issue. Looking at the pass
manager at <a
href="https://github.com/llvm-mirror/llvm/blob/7034870f30320d6fbc74effff539d946018cd00a/lib/Transforms/IPO/PassManagerBuilder.cpp"
moz-do-not-send="true">https://github.com/llvm-mirror/llvm/blob/7034870f30320d6fbc74effff539d946018cd00a/lib/Transforms/IPO/PassManagerBuilder.cpp</a>
(the early SimplifyCfg now doesn't sink stores anymore! I
can't wait until I can get to use that in rustc!) I find that
the loop optimization group does not run after GVN:<br>
<br>
<span style="font-family:monospace,monospace"> // Rotate Loop
- disable header duplication at -Oz<br>
MPM.add(createLoopRotatePass(SizeLevel == 2 ? 0 : -1));<br>
MPM.add(createLICMPass()); // Hoist loop
invariants<br>
if (EnableSimpleLoopUnswitch)<br>
MPM.add(createSimpleLoopUnswitchLegacyPass());<br>
else<br>
MPM.add(createLoopUnswitchPass(SizeLevel || OptLevel
< 3, DivergentTarget));<br>
MPM.add(createCFGSimplificationPass());<br>
addInstructionCombiningPass(MPM);<br>
MPM.add(createIndVarSimplifyPass()); //
Canonicalize indvars<br>
</span></div>
<div><span style="font-family:monospace,monospace"> // <I
probably want to add some SimplifyCfg pass here, but<br>
</span></div>
<div><span style="font-family:monospace,monospace"> // that's a
separate issue><br>
</span></div>
<div><span style="font-family:monospace,monospace">
MPM.add(createLoopIdiomPass()); // Recognize
idioms like memset.<br>
addExtensionsToPM(EP_LateLoopOptimizations, MPM);<br>
MPM.add(createLoopDeletionPass()); // Delete dead
loops<br>
if (EnableLoopInterchange) {<br>
MPM.add(createLoopInterchangePass()); // Interchange
loops<br>
MPM.add(createCFGSimplificationPass());<br>
}<br>
if (!DisableUnrollLoops)<br>
MPM.add(createSimpleLoopUnrollPass()); // Unroll
small loops<br>
addExtensionsToPM(EP_LoopOptimizerEnd, MPM);<br>
<br>
</span></div>
<span style="font-family:monospace,monospace"> // <GVN is
now immediately after loop optimizatons<br>
</span>
<div>
<div><span style="font-family:monospace,monospace"><br>
if (OptLevel > 1) {<br>
MPM.add(createMergedLoadStoreMotionPass()); // Merge
ld/st in diamonds<br>
MPM.add(NewGVN ? createNewGVNPass()<br>
: createGVNPass(DisableGVNLoadPRE)); //
Remove redundancies<br>
}<br>
<br>
</span></div>
<div><span style="font-family:monospace,monospace"><font
face="arial,helvetica,sans-serif">This causes a problem,
because GVN appears to be the only pass that can merge
loads across basic blocks. </font></span></div>
</div>
</div>
</blockquote>
<font face="arial,helvetica,sans-serif">Aside: EarlyCSE also does
this in simple cases with no merges in the CFG between the two
loads.</font><br>
<blockquote type="cite"
cite="mid:CAJrJsjf+oMidcQYntShUguF2_cuq9cfJbKL1mSGuZE4vaLLgJA@mail.gmail.com">
<div dir="ltr">
<div>
<div><span style="font-family:monospace,monospace"><font
face="arial,helvetica,sans-serif">This means that if a
loop index only appears behind a pointer, LLVM will not
be able to optimize out bounds checks depending on it.<br>
<br>
</font></span></div>
<div><span style="font-family:monospace,monospace"><font
face="arial,helvetica,sans-serif">The "canonical"
example is this Rust function (or the similar C code):<br>
<br>
</font>#![crate_type="rlib"]<br>
pub fn f(length: &usize) -> u64 {<br>
let mut sum = 0;<br>
let len_1 = *length;<br>
let mut i = 0;<br>
while i < len_1 {<br>
let len_2 = *length;<br>
assert!(i < len_2);<br>
i += 1;<br>
}<br>
sum<br>
}<font face="arial,helvetica,sans-serif"><br>
<br>
</font></span></div>
<div><span style="font-family:monospace,monospace"><font
face="arial,helvetica,sans-serif">One would expect the
assertion (which in a real example is a bounds check) to
be optimized out. However, IndVarSimplify is the
optimization that is supposed to do that, and it only
runs *before* GVN, so it "sees" 2 separate loads of the
length and can't do anything.<br>
<br>
</font></span></div>
<div><span style="font-family:monospace,monospace"><font
face="arial,helvetica,sans-serif">Changing the pass
ordering to put GVN before the loop optimizations
(reversing the 2 blocks in my excerpt above) fixes this
example, so I'm trying to figure out whether that
destroys something important. I'll note that rustc has
another GVN pass "downstream" (before the
DeadStoreElimination pass) which might help alleviate
some worries.<br>
</font></span></div>
</div>
</div>
</blockquote>
<font face="arial,helvetica,sans-serif">I think you've discovered
the practical reality that your frontend should have it's own pass
order. Our Java frontend specifically runs multiple iterations of
these passes to avoid scenarios like this. Getting this changed
in the standard pipeline will be slow going at best; you're
probably better off versioning one which works for you.<br>
<br>
Also, since you care about range checks, I strongly suggest you
take a loop at LoopPredication and InductiveRangeCheckElimination.
<br>
</font>
<blockquote type="cite"
cite="mid:CAJrJsjf+oMidcQYntShUguF2_cuq9cfJbKL1mSGuZE4vaLLgJA@mail.gmail.com">
<div dir="ltr">
<div>
<div><span style="font-family:monospace,monospace"><font
face="arial,helvetica,sans-serif"><br>
I could not find any good documentation or tests for why
the passes are in the order they are - the order seems
to have been preserved from clang in 2009. If you have
some good testing infrastructure, it would be nice if
there was a way we could use it to check whether the
pass reordering would hurt anything important.<br>
</font></span></div>
</div>
</div>
</blockquote>
<font face="arial,helvetica,sans-serif">The reality is that pass
ordering is a mostly experimental science. We try something,
measure, and see what goes wrong. You can also look to improve
frequently run passes to handle the simple cases. <br>
<br>
</font><font face="arial,helvetica,sans-serif">In your particular
example, I'd look to see why LICM wasn't hoisting "</font><font
face="arial,helvetica,sans-serif"><span
style="font-family:monospace,monospace">let len_2 = *length;".
Once that's done, EarlyCSE should be able to common the loads
exposing the range check for indvarsimplify. I<font
face="arial,helvetica,sans-serif">RCE would also handle this
case.</font></span></font><br>
<font face="arial,helvetica,sans-serif"><span
style="font-family:monospace,monospace"></span></font>
<blockquote type="cite"
cite="mid:CAJrJsjf+oMidcQYntShUguF2_cuq9cfJbKL1mSGuZE4vaLLgJA@mail.gmail.com">
<div dir="ltr">
<div>
<div><span style="font-family:monospace,monospace"><font
face="arial,helvetica,sans-serif"><br>
</font></span></div>
<div><span style="font-family:monospace,monospace"><font
face="arial,helvetica,sans-serif">And in any case, I
keep seeing weird optimization misses caused by pass
ordering. It would be nice if there was some better
knowledge of this situation.<br>
<br>
</font></span></div>
<div><span style="font-family:monospace,monospace"><font
face="arial,helvetica,sans-serif">Regards,<br>
</font></span></div>
<div><span style="font-family:monospace,monospace"><font
face="arial,helvetica,sans-serif"> - Ariel<br>
</font></span></div>
</div>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
</body>
</html>