<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">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. 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><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><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>