Page MenuHomePhabricator

[LICM] Preserve DT and LoopInfo specifically
ClosedPublic

Authored by junbuml on May 11 2018, 1:56 PM.

Details

Summary

In LICM, CFG could be changed in splitPredecessorsOfLoopExit(), which update
only DT and LoopInfo. Therefore, we should preserve only DT and LoopInfo specifically,
instead of all analyses that depend on the CFG (setPreservesCFG()).

This change should fix PR37323.

Diff Detail

Repository
rL LLVM

Event Timeline

junbuml created this revision.May 11 2018, 1:56 PM
bjope added a subscriber: bjope.May 11 2018, 2:28 PM
Ka-Ka resigned from this revision.May 14 2018, 1:03 AM

This definitely solve the problem I saw in the issue pr37369.

Previously LICM claimed that it preserved all CFG analyses which was not true as at least post dominator tree was not preserved. With this patch LICM claim to only preserve dominator tree and loop analysis. I leave to someone else to review if there are more of the CFG analyses that actually are preserved (and then should be marked as preserved in LICM).

Thanks for working on this.

Thanks Jun, this indeed solves PR37323.

I've no idea if this is the best way to solve the problem though so it would be good with some opinion from Davide or Daniel.

dberlin accepted this revision.May 14 2018, 8:01 AM

In a perfect world we should update LICM to preserve all CFG analysis.
For now, this at least makes it correct.

Unfortunately, this also means we didn't properly take into account the compile time affects of the underlying change that broke this.

We shall see what the fallout is.

This revision is now accepted and ready to land.May 14 2018, 8:01 AM

Thanks Daniel for the review.
I agree that ideally LICM should preserve the CFG, and this change could potentially impact the compile time. However, I think this is the safest fix at this moment without a mess of updating extra analysis passes. In current pipelines (-O3, -O2, -O1, -Oz, and -Os), I looked at -debug-pass=Executions, and didn't see any extra execution of analysis passes after this change.

mzolotukhin added inline comments.
test/Transforms/LICM/pr37323.ll
1–2 ↗(On Diff #146409)

By the way, do we have something like -verify-dom-tree for PostDT? It would be cleaner to explicitly verify postdom tree here than calling ADCE and hoping it crashes.

junbuml updated this revision to Diff 147178.May 16 2018, 2:21 PM

Addressed Michael's comment.

test/Transforms/LICM/pr37323.ll
1–2 ↗(On Diff #146409)

The same tag (-verify-dom-info) seem to cover PostDT's verifyAnalysis as well. Using -verify-dom-info, I confirmed that this test crash in PostDT's verifyAnalysis without this change.

mzolotukhin added inline comments.May 16 2018, 2:30 PM
test/Transforms/LICM/pr37323.ll
1–2 ↗(On Diff #146409)

Thanks for checking! Also, speaking of reducing the test case further- can we get rid of -loop-simplify (i.e. replace the test with the output of loop-simplify) and -adce?

junbuml added inline comments.May 17 2018, 9:41 AM
test/Transforms/LICM/pr37323.ll
1–2 ↗(On Diff #146409)

Without this patch, I tried to reproduce the crash in this test case without -loop-simplify and -adce. However, we need both to reproduce the crash. If we remove -loop-simplify and put passes just like "-postdomtree -licm -adce", then the PDT executed before LICM will be invalidated (not preserved) after "Canonicalize natural loops". Therefore, we cannot reproduce the crash because the postdom will be re-executed before ADCE. Please see the pass order for "-postdomtree -licm -adce" :

Post-Dominator Tree Construction     <-- execute postdom
Dominator Tree Construction
Natural Loop Information
Canonicalize natural loops           <-- postdom is invalidated and not preserved
LCSSA Verifier
Loop-Closed SSA Form Pass
Basic Alias Analysis (stateless AA impl)
Function Alias Analysis Results
Scalar Evolution Analysis
Loop Pass Manager
  Loop Invariant Code Motion
Post-Dominator Tree Construction    <--- re-execute postdom
Aggressive Dead Code Elimination    <--- cannot reproduce the crash

We should make the postdom executed after "Canonicalize natural loops".

Even with -verify-loop-info, after licm, we still need a pass which requires postdom (e.g., adce) to verify postdom. Otherwise, PostDT's verifyAnalysis wont be invoked.

test/Transforms/LICM/pr37323.ll
1–2 ↗(On Diff #146409)

Hi Michael,

Can you please let me know if this test is okay with loop-simplify and adce ?
Thanks,
Jun

mzolotukhin added inline comments.May 23 2018, 9:05 AM
test/Transforms/LICM/pr37323.ll
1–2 ↗(On Diff #146409)

Yes, it's ok, thanks for the investigation and explanation!

This revision was automatically updated to reflect the committed changes.