[LoopReroll] Run LICM before Loop Rerolling.

[jmolloy]

Summary

Loop rerolling bails out if any value is not used by any iteration. Make sure all invariant values are hoisted first.

[hfinkel]

Two thoughts:

1. Is it hard to teach the unroller to ignore loop-invariant values? [SE has a function for that].
2. Except under iteration from the CGSCC pass manager, we don't run LICM again after loop rerolling. If we're still finding loop invariant values in loops at that point in the pass sequence, it seems like we should run this again generically (regardless of whether we might reroll or not).

[jmolloy]

Hi Hal,

Hmm yeah, good questions. I can do (1). I hadn't remembered that SE had a function for this - I was trying to avoid implementing LICM myself!

But I'm not sure if I should do (1) because of (2). In my testcase, which is fairly difficult to reduce, we end up with a stray invariant multiply which is not the cheapest thing in the world. Perhaps adding another LICM regardless of Rerolling is the right way to go after all?

[hfinkel]

In D7674#124359, @jmolloy wrote:

Hi Hal,

Hmm yeah, good questions. I can do (1). I hadn't remembered that SE had a function for this - I was trying to avoid implementing LICM myself!

But I'm not sure if I should do (1) because of (2). In my testcase, which is fairly difficult to reduce,

This is not difficult to reduce ;) -- add an assert in the loop reroller, and let bugpoint do it. We need to understand where this comes from so we can sensibly talk about adjusting the pass manager configuration.

we end up with a stray invariant multiply which is not the cheapest thing in the world. Perhaps adding another LICM regardless of Rerolling is the right way to go after all?

I vote for both.

[jmolloy]

Hi Hal,

OK, I managed to track it down (bugpoint didn't help, but I strained my eyes over every pass until I'd worked it out :) ).

It comes from loop unrolling - we unroll part of a loop nest but don't run LICM afterwards to clean up. New patch adds it to the cleanup part of the scalar optimizer.

As this was a latent bug, I don't think we need to smarten up the reroller to handle this - we should be able to expect our input to be optimized. Do you agree with this?

Cheers,

James

[hfinkel]

In D7674#124383, @jmolloy wrote:

Hi Hal,

OK, I managed to track it down (bugpoint didn't help, but I strained my eyes over every pass until I'd worked it out :) ).

It comes from loop unrolling - we unroll part of a loop nest but don't run LICM afterwards to clean up. New patch adds it to the cleanup part of the scalar optimizer.

Okay, nice!

As this was a latent bug, I don't think we need to smarten up the reroller to handle this - we should be able to expect our input to be optimized. Do you agree with this?

Yea, that's why I didn't handle them in the first place.

Cheers,

James

[jmolloy]

Thanks Hal - committed in r229419.

lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::populateModulePassManager(
   MPM.add(createInstructionCombiningPass());
   addExtensionsToPM(EP_Peephole, MPM);
   MPM.add(createJumpThreadingPass());         // Thread jumps
   MPM.add(createCorrelatedValuePropagationPass());
   MPM.add(createDeadStoreEliminationPass());  // Delete dead stores
 
   addExtensionsToPM(EP_ScalarOptimizerLate, MPM);
 
-  if (RerollLoops)
+  if (RerollLoops) {
+    // Run LICM before loop rerolling, as rerolling cannot handle any
+    // loop-invariant values at all.
+    MPM.add(createLICMPass());
     MPM.add(createLoopRerollPass());
+  }
   if (!RunSLPAfterLoopVectorization) {
     if (SLPVectorize)
       MPM.add(createSLPVectorizerPass());   // Vectorize parallel scalar chains.
 
     if (BBVectorize) {
       MPM.add(createBBVectorizePass());
       MPM.add(createInstructionCombiningPass());
       addExtensionsToPM(EP_Peephole, MPM);