[LTO] Add a run of LoopUnroll

[jmolloy]

Summary

Loop trip counts can often be resolved during LTO. We should obviously be unrolling small loops once those trip counts have been resolved, but we weren't.

This causes no change in a -flto run of the test-suite for me, but the nature of fully unrolling loops is that when they trigger, they cause massive changes in runtime. We observe this on third party test suites.

[mehdi_amini]

lib/Transforms/IPO/PassManagerBuilder.cpp

576

Note: it is inserted before LoopInterchangePass in the regular pipeline?

Also there is a comment before another insertion // BBVectorize may have significantly shortened a loop body; unroll again.. Could this be valid for the Loop and SLP vectorizers that are inserted below?

[hfinkel]

lib/Transforms/IPO/PassManagerBuilder.cpp

576

Also there is a comment before another insertion // BBVectorize may have significantly shortened a loop body; unroll again.. Could this be valid for the Loop and SLP vectorizers that are inserted below?

Yes, although for the loop vectorizer there is a competing effect: The loop vectorizer does not vectorize loops with known constant trip counts below some threshold (TinyTripCountVectorThreshold - 16 by default).

[jmolloy]

Hi Mehdi,

Note: it is inserted before LoopInterchangePass in the regular pipeline?

In the regular pipeline there are many runs of loop unrolling. This extra unroll will only unroll loops completely - it'll never do partial unrolling. So the ideal place to do this is when loops are most countable and when trivial loops have been deleted. That's why I put this after LoopDeletion.

I agree that a cleanup Unroll after Vectorize seems a good idea. I'll add that.

James

[jmolloy]

Mehdi accepted this on IRC with the condition that the first unroll invocation was swapped with LoopInterchange to be identical to the non-LTO pipeline.

[jmolloy]

r257767

lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::addLTOOptimizationPasses(legacy::PassManagerBase &PM) {
   PM.add(createMemCpyOptPass());            // Remove dead memcpys.
 
   // Nuke dead stores.
   PM.add(createDeadStoreEliminationPass());
 
   // More loops are countable; try to optimize them.
   PM.add(createIndVarSimplifyPass());
   PM.add(createLoopDeletionPass());
+  if (!DisableUnrollLoops)
+    PM.add(createSimpleLoopUnrollPass());   // Unroll small loops
   if (EnableLoopInterchange)
     PM.add(createLoopInterchangePass());
 
   PM.add(createLoopVectorizePass(true, LoopVectorize));
+  // The vectorizer may have significantly shortened a loop body; unroll again.
+  if (!DisableUnrollLoops)
+    PM.add(createLoopUnrollPass());
 
   // Now that we've optimized loops (in particular loop induction variables),
   // we may have exposed more scalar opportunities. Run parts of the scalar
   // optimizer again at this point.
   PM.add(createInstructionCombiningPass()); // Initial cleanup
   PM.add(createCFGSimplificationPass()); // if-convert
   PM.add(createSCCPPass()); // Propagate exposed constants
   PM.add(createInstructionCombiningPass()); // Clean up again