[LICM] Preserve DT and LoopInfo specifically

[junbuml]

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.

[Ka-Ka]

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.

[uabelho]

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]

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.

[junbuml]

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]

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]

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]

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]

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.

[junbuml]

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]

test/Transforms/LICM/pr37323.ll

1–2 ↗

(On Diff #146409)

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

llvm/trunk/lib/Transforms/Scalar/LICM.cpp

return LICM.runOnLoop(L,
                               *L->getHeader()->getParent()),
                           SE ? &SE->getSE() : nullptr, MSSA, &ORE, false);
   }
 
   /// This transformation requires natural loop information & requires that
   /// loop preheaders be inserted into the CFG...
   ///
   void getAnalysisUsage(AnalysisUsage &AU) const override {
-    AU.setPreservesCFG();
+    AU.addPreserved<DominatorTreeWrapperPass>();
+    AU.addPreserved<LoopInfoWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
     if (EnableMSSALoopDependency)
       AU.addRequired<MemorySSAWrapperPass>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
     getLoopAnalysisUsage(AU);
   }
 
   using llvm::Pass::doFinalization;
report_fatal_error("LICM: OptimizationRemarkEmitterAnalysis not "
                        "cached at a higher level");
 
   LoopInvariantCodeMotion LICM;
   if (!LICM.runOnLoop(&L, &AR.AA, &AR.LI, &AR.DT, &AR.TLI, &AR.TTI, &AR.SE,
                       AR.MSSA, ORE, true))
     return PreservedAnalyses::all();
 
   auto PA = getLoopPassPreservedAnalyses();
-  PA.preserveSet<CFGAnalyses>();
+
+  PA.preserve<DominatorTreeAnalysis>();
+  PA.preserve<LoopAnalysis>();
+
   return PA;
 }
 
 char LegacyLICMPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LegacyLICMPass, "licm", "Loop Invariant Code Motion",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)

llvm/trunk/test/Transforms/LICM/pr37323.ll

+;RUN: opt -verify-dom-info -loop-simplify -postdomtree -licm -adce -verify-loop-info -S -o - %s | FileCheck %s
+;RUN: opt -verify-dom-info -passes='loop-simplify,require<postdomtree>,require<opt-remark-emit>,loop(licm),function(adce)' -S -o - %s | FileCheck %s
+
+target triple = "x86_64-unknown-linux-gnu"
+
+@c = external global i16, align 1
+
+;Make sure this test do not crash while accessing PostDomTree which is not
+;preserved in LICM.
+;
+;CHECK-LABEL: fn1()
+;CHECK-LABEL: for.cond.loopexit.split.loop.exit
+;CHECK-LABEL: for.cond.loopexit.split.loop.exit1
+define void @fn1() {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %if.end, %for.cond1, %entry
+  %0 = phi i16 [ undef, %entry ], [ ptrtoint (i16* @c to i16), %if.end ], [ %.mux, %for.cond1 ]
+  br i1 undef, label %for.cond1, label %for.end8
+
+for.cond1:                                        ; preds = %if.end, %for.cond
+  %.mux = select i1 undef, i16 undef, i16 ptrtoint (i16* @c to i16)
+  br i1 undef, label %for.cond, label %if.end
+
+if.end:                                           ; preds = %for.cond1
+  br i1 undef, label %for.cond, label %for.cond1
+
+for.end8:                                         ; preds = %for.cond
+  ret void
+}