Add CFG Simplification pass after Loop Unswitching.

[mzolotukhin]

Summary

Loop unswitching produces conditional branches with constant condition,
and it's beneficial for later passes to clean this up with simplify-cfg.
We do this after the second invocation of loop-unswitch, but not after
the first one. Not doing so might cause problem for passes like
LoopUnroll, whose estimate of loop body size would be less accurate.

[hfinkel]

What's the overall change to the pass/analysis schedule? I'd tend to think that putting it after InstCombine would be better so it would not need to recompute DT again for InstCombine.

[mzolotukhin]

Hi Hal,

What's the overall change to the pass/analysis schedule? I'd tend to think that putting it after InstCombine would be better so it would not need to recompute DT again for InstCombine.

That shouldn't matter because InstCombine preserves DominatorTree - so we'll rebuild it after SimplifyCFG only once. If we run SimplifyCFG after InstCombine, we invoke Basic Alias Analysis (stateless AA impl) twice (, but as far as I understand it's almost free.

Michael

PS: The structures of passes are the following:
(Disclaimer: it's only readable in phabricator)

Original structure	SimplifyCFG before InstCombine	SimplifyCFG after InstCombine
...	...	...
Unswitch loops	Unswitch loops	Unswitch loops
	Simplify the CFG
Basic Alias Analysis (stateless AA impl)	Basic Alias Analysis (stateless AA impl)	Basic Alias Analysis (stateless AA impl)
Function Alias Analysis Results	Function Alias Analysis Results	Function Alias Analysis Results
	Dominator Tree Construction
Combine redundant instructions	Combine redundant instructions	Combine redundant instructions
		Simplify the CFG
		Dominator Tree Construction
	Natural Loop Information	Natural Loop Information
Scalar Evolution Analysis	Scalar Evolution Analysis	Scalar Evolution Analysis
Canonicalize natural loops	Canonicalize natural loops	Canonicalize natural loops
Loop-Closed SSA Form Pass	Loop-Closed SSA Form Pass	Loop-Closed SSA Form Pass
Induction Variable Simplification	Induction Variable Simplification	Induction Variable Simplification
		Basic Alias Analysis (stateless AA impl)
Function Alias Analysis Results	Function Alias Analysis Results	Function Alias Analysis Results
Recognize loop idioms	Recognize loop idioms	Recognize loop idioms
...	...	...

[hfinkel]

In D13064#252353, @mzolotukhin wrote:

Hi Hal,

What's the overall change to the pass/analysis schedule? I'd tend to think that putting it after InstCombine would be better so it would not need to recompute DT again for InstCombine.

That shouldn't matter because InstCombine preserves DominatorTree - so we'll rebuild it after SimplifyCFG only once. If we run SimplifyCFG after InstCombine, we invoke Basic Alias Analysis (stateless AA impl) twice (, but as far as I understand it's almost free.

...

Okay, thanks. Indeed, in this case, constructing the DT after SimplifyCFG is probably going to be cheaper (or the same cost) as constructing it before hand, so keeping it before InstCombine is probably better. LGTM.

[mzolotukhin]

Thanks!

llvm/trunk/lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::populateModulePassManager(
 
   MPM.add(createTailCallEliminationPass()); // Eliminate tail calls
   MPM.add(createCFGSimplificationPass());     // Merge & remove BBs
   MPM.add(createReassociatePass());           // Reassociate expressions
   // Rotate Loop - disable header duplication at -Oz
   MPM.add(createLoopRotatePass(SizeLevel == 2 ? 0 : -1));
   MPM.add(createLICMPass());                  // Hoist loop invariants
   MPM.add(createLoopUnswitchPass(SizeLevel || OptLevel < 3));
+  MPM.add(createCFGSimplificationPass());
   MPM.add(createInstructionCombiningPass());
   MPM.add(createIndVarSimplifyPass());        // Canonicalize indvars
   MPM.add(createLoopIdiomPass());             // Recognize idioms like memset.
   MPM.add(createLoopDeletionPass());          // Delete dead loops
   if (EnableLoopInterchange) {
     MPM.add(createLoopInterchangePass()); // Interchange loops
     MPM.add(createCFGSimplificationPass());
   }