Page MenuHomePhabricator

Add CFG Simplification pass after Loop Unswitching.
ClosedPublic

Authored by mzolotukhin on Sep 22 2015, 12:11 PM.

Details

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.

Diff Detail

Repository
rL LLVM

Event Timeline

mzolotukhin retitled this revision from to Add CFG Simplification pass after Loop Unswitching..
mzolotukhin updated this object.
mzolotukhin added reviewers: chandlerc, hfinkel.
mzolotukhin added a subscriber: llvm-commits.
hfinkel edited edge metadata.Sep 23 2015, 12:57 PM

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.

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 structureSimplifyCFG before InstCombineSimplifyCFG after InstCombine
.........
Unswitch loopsUnswitch loopsUnswitch 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 ResultsFunction Alias Analysis ResultsFunction Alias Analysis Results
Dominator Tree Construction
Combine redundant instructionsCombine redundant instructionsCombine redundant instructions
Simplify the CFG
Dominator Tree Construction
Natural Loop InformationNatural Loop Information
Scalar Evolution AnalysisScalar Evolution AnalysisScalar Evolution Analysis
Canonicalize natural loopsCanonicalize natural loopsCanonicalize natural loops
Loop-Closed SSA Form PassLoop-Closed SSA Form PassLoop-Closed SSA Form Pass
Induction Variable SimplificationInduction Variable SimplificationInduction Variable Simplification
Basic Alias Analysis (stateless AA impl)
Function Alias Analysis ResultsFunction Alias Analysis ResultsFunction Alias Analysis Results
Recognize loop idiomsRecognize loop idiomsRecognize loop idioms
.........
hfinkel accepted this revision.Sep 23 2015, 7:09 PM
hfinkel edited edge metadata.

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.

This revision is now accepted and ready to land.Sep 23 2015, 7:09 PM
This revision was automatically updated to reflect the committed changes.