Require DominatorTree when requiring/preserving LoopInfo in the old pass manager

[uabelho]

Summary

Require DominatorTree when requiring/preserving LoopInfo in the old pass manager

BreakCriticalEdges tries to keep LoopInfo and DominatorTree updated if they
exist. However, since commit r321653 and r321805, to update LoopInfo we
must have a DominatorTree, or we will hit an assert.

To fix this we now make a couple of passes that only required/preserved
LoopInfo also require DominatorTree.

This solves PR37334.

[efriedma]

Like I said in the bug, I would rather fix BranchProbabilityInfoWrapperPass::getAnalysisUsage.

[uabelho]

In D46829#1098592, @efriedma wrote:

Like I said in the bug, I would rather fix BranchProbabilityInfoWrapperPass::getAnalysisUsage.

Alright, I'll do that then.

I can't say I really understand though.

What if we in some completely other situation, without running BranchProbabilityInfo, do BreakCriticalEdges and LI is available and DT isn't?
Then BreakCriticalEdges will (try to) update LI, but since there is no DT, the same assert will trigger again? Or what is it I'm missing?

[uabelho]

Full stacktrace when it hits the assert:

opt: ../lib/Transforms/Utils/BasicBlockUtils.cpp:337: void UpdateAnalysisInformation(llvm::BasicBlock *, llvm::BasicBlock *, ArrayRef<llvm::BasicBlock *>, llvm::DominatorTree *, llvm::LoopInfo *, bool, bool &): Assertion `DT && "DT should be available to update LoopInfo!"' failed.
Stack dump:
0. Program arguments: build-all-Debug/bin/opt test/Transforms/Util/PR37334-break-crit-edges-require-dt.ll -o - -loop-sink -break-crit-edges -branch-prob -S -debug-pass=Executions

1. Running pass 'Function Pass Manager' on module 'test/Transforms/Util/PR37334-break-crit-edges-require-dt.ll'.
2. Running pass 'Break critical edges in CFG' on function '@f1'

#0 0x00000000035e086c llvm::sys::PrintStackTrace(llvm::raw_ostream&) /data/repo/llvm-patch/build-all-Debug/../lib/Support/Unix/Signals.inc:399:5
#1 0x00000000035e0a19 PrintStackTraceSignalHandler(void*) /data/repo/llvm-patch/build-all-Debug/../lib/Support/Unix/Signals.inc:463:1
#2 0x00000000035defc3 llvm::sys::RunSignalHandlers() /data/repo/llvm-patch/build-all-Debug/../lib/Support/Signals.cpp:50:5
#3 0x00000000035e105e SignalHandler(int) /data/repo/llvm-patch/build-all-Debug/../lib/Support/Unix/Signals.inc:253:1
#4 0x00007f291488e330 restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x10330)
#5 0x00007f291347dc37 gsignal /build/eglibc-ripdx6/eglibc-2.19/signal/../nptl/sysdeps/unix/sysv/linux/raise.c:56:0
#6 0x00007f2913481028 abort /build/eglibc-ripdx6/eglibc-2.19/stdlib/abort.c:91:0
#7 0x00007f2913476bf6 assert_fail_base /build/eglibc-ripdx6/eglibc-2.19/assert/assert.c:92:0
#8 0x00007f2913476ca2 (/lib/x86_64-linux-gnu/libc.so.6+0x2fca2)
#9 0x000000000360796a UpdateAnalysisInformation(llvm::BasicBlock*, llvm::BasicBlock*, llvm::ArrayRef<llvm::BasicBlock*>, llvm::DominatorTree*, llvm::LoopInfo*, bool, bool&) /data/repo/llvm-patch/build-all-Debug/../lib/Transforms/Utils/BasicBlockUtils.cpp:338:13
#10 0x0000000003606e1f llvm::SplitBlockPredecessors(llvm::BasicBlock*, llvm::ArrayRef<llvm::BasicBlock*>, char const*, llvm::DominatorTree*, llvm::LoopInfo*, bool) /data/repo/llvm-patch/build-all-Debug/../lib/Transforms/Utils/BasicBlockUtils.cpp:519:3
#11 0x000000000360ba51 llvm::SplitCriticalEdge(llvm::TerminatorInst*, unsigned int, llvm::CriticalEdgeSplittingOptions const&) /data/repo/llvm-patch/build-all-Debug/../lib/Transforms/Utils/BreakCriticalEdges.cpp:285:23
#12 0x00000000036068b1 llvm::SplitAllCriticalEdges(llvm::Function&, llvm::CriticalEdgeSplittingOptions const&) /data/repo/llvm-patch/build-all-Debug/../lib/Transforms/Utils/BasicBlockUtils.cpp:285:13
#13 0x000000000360cab7 (anonymous namespace)::BreakCriticalEdges::runOnFunction(llvm::Function&) /data/repo/llvm-patch/build-all-Debug/../lib/Transforms/Utils/BreakCriticalEdges.cpp:54:11
#14 0x0000000002cdc95d llvm::FPPassManager::runOnFunction(llvm::Function&) /data/repo/llvm-patch/build-all-Debug/../lib/IR/LegacyPassManager.cpp:1520:23
#15 0x0000000002cdcc95 llvm::FPPassManager::runOnModule(llvm::Module&) /data/repo/llvm-patch/build-all-Debug/../lib/IR/LegacyPassManager.cpp:1541:16
#16 0x0000000002cdd47e (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /data/repo/llvm-patch/build-all-Debug/../lib/IR/LegacyPassManager.cpp:1597:23
#17 0x0000000002cdcf7b llvm::legacy::PassManagerImpl::run(llvm::Module&) /data/repo/llvm-patch/build-all-Debug/../lib/IR/LegacyPassManager.cpp:1700:16
#18 0x0000000002cdd9c1 llvm::legacy::PassManager::run(llvm::Module&) /data/repo/llvm-patch/build-all-Debug/../lib/IR/LegacyPassManager.cpp:1731:3
#19 0x0000000000c19c25 main /data/repo/llvm-patch/build-all-Debug/../tools/opt/opt.cpp:762:3
#20 0x00007f2913468f45 __libc_start_main /build/eglibc-ripdx6/eglibc-2.19/csu/libc-start.c:321:0
#21 0x0000000000bde519 _start (build-all-Debug/bin/opt+0xbde519)
Abort

Adding the require to BranchProbabilityInfoWrapperPass::getAnalysisUsage makes the crash go away too, but I don't understand
why/how that is the proper solution so I'd be happy if you could explain so I can at least write a proper commit message then :)

Thanks!

[efriedma]

LoopInfo has a dependency on DominatorTree: when a pass requests the LoopInfo analysis, DominatorTree gets implicitly added to the pass pipeline. This is fine so far, but doesn't take into account what happens when a pass preserves LoopInfo or DominatorTree. When the CFG is mutated, we need to update LoopInfo, and at that point, we again need the DominatorTree. Normally it should be available: passes which require LoopInfo usually also require DomTree, and passes which preserve LoopInfo also usually preserve DomTree.

But BranchProbabilityInfo is weird: it requires LoopInfo, but not DomTree. In the simple case without any preserved analysis passes, this works because the pass manager implicitly adds the DomTree run anyway. But in the more complicated case, where there's some pass in between the LoopInfo run and the BranchProbabilityInfo run, it doesn't work. The DomTree gets computed, then dropped after LoopInfo, because no future pass in the pipeline requires it. But we actually need it to preserve LoopInfo.

One way to solve this problem is, like you're suggesting, to make any pass which uses a DomTree to update LoopInfo explicitly require a DomTree. This works, but adds unnecessary computation to the pass pipeline: we compute the domtree even if nothing actually needs it.

The other way to solve the issue is to always require/preserve domtree anywhere that requires/preseves LoopInfo. This way, we always have a domtree if we have loopinfo, and we only compute the domtree in cases where we actually need it.

[uabelho]

Ok, added require of DT to BranchProbabilityInfo (and LazyBlockFrequencyInfo and LazyBranchProbabilityInfo since BreakCriticalEdges crashed the same way when running them) instead of to BreakCriticalEdges.

[uabelho]

Thanks for the explanation!

I searched through the code and found two other passes that would also trigger the assertion, so I added the require to them too.
I wouldn't be surprised if there is some other pass that I missed but I haven't seen any other crash.

[efriedma]

LGTM

lib/Analysis/BranchProbabilityInfo.cpp

1008

I don't think you need to specifically mention break-crit-edges here; just a brief explanation of the general problem is enough.

[uabelho]

Updated the comments in the code to not specifically mention -break-crit-edges.

[uabelho]

In D46829#1102108, @efriedma wrote:

LGTM

Thanks!

I'll push this in a little bit then.

lib/Analysis/BranchProbabilityInfo.cpp

 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/Type.h"
if (PrintBranchProb &&
       (PrintBranchProbFuncName.empty() ||
        F.getName().equals(PrintBranchProbFuncName))) {
     print(dbgs());
   }
 }
 
 void BranchProbabilityInfoWrapperPass::getAnalysisUsage(
     AnalysisUsage &AU) const {
+  // We require DT so it's available if -break-crit-edges (which will keep both
+  // DT and LI updated if they exist) is run before.
+  // Else -break-crit-edges will hit an assert when updating LI (due to missing
+  // DT).
+  AU.addRequired<DominatorTreeWrapperPass>();
   AU.addRequired<LoopInfoWrapperPass>();
   AU.addRequired<TargetLibraryInfoWrapperPass>();
   AU.setPreservesAll();
 }
 
 bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) {
   const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   const TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();

lib/Analysis/LazyBlockFrequencyInfo.cpp

 // the analysis pass is executed but rather when the BFI result is explicitly
 // requested by the analysis client.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/LazyBlockFrequencyInfo.h"
 #include "llvm/Analysis/LazyBranchProbabilityInfo.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/IR/Dominators.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "lazy-block-freq"
 
 INITIALIZE_PASS_BEGIN(LazyBlockFrequencyInfoPass, DEBUG_TYPE,
                       "Lazy Block Frequency Analysis", true, true)
 INITIALIZE_PASS_DEPENDENCY(LazyBPIPass)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_END(LazyBlockFrequencyInfoPass, DEBUG_TYPE,
                     "Lazy Block Frequency Analysis", true, true)
 
 char LazyBlockFrequencyInfoPass::ID = 0;
 
 LazyBlockFrequencyInfoPass::LazyBlockFrequencyInfoPass() : FunctionPass(ID) {
   initializeLazyBlockFrequencyInfoPassPass(*PassRegistry::getPassRegistry());
 }
 
 void LazyBlockFrequencyInfoPass::print(raw_ostream &OS, const Module *) const {
   LBFI.getCalculated().print(OS);
 }
 
 void LazyBlockFrequencyInfoPass::getAnalysisUsage(AnalysisUsage &AU) const {
   LazyBranchProbabilityInfoPass::getLazyBPIAnalysisUsage(AU);
+  // We require DT so it's available if -break-crit-edges (which will keep both
+  // DT and LI updated if they exist) is run before.
+  // Else -break-crit-edges will hit an assert when updating LI (due to missing
+  // DT).
+  AU.addRequired<DominatorTreeWrapperPass>();
   AU.addRequired<LoopInfoWrapperPass>();
   AU.setPreservesAll();
 }
 
 void LazyBlockFrequencyInfoPass::releaseMemory() { LBFI.releaseMemory(); }
 
 bool LazyBlockFrequencyInfoPass::runOnFunction(Function &F) {
   auto &BPIPass = getAnalysis<LazyBranchProbabilityInfoPass>();

lib/Analysis/LazyBranchProbabilityInfo.cpp

 // computed when the analysis pass is executed but rather when the BPI results
 // is explicitly requested by the analysis client.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/LazyBranchProbabilityInfo.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/IR/Dominators.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "lazy-branch-prob"
 
 INITIALIZE_PASS_BEGIN(LazyBranchProbabilityInfoPass, DEBUG_TYPE,
                       "Lazy Branch Probability Analysis", true, true)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)

 }
 
 void LazyBranchProbabilityInfoPass::print(raw_ostream &OS,
                                           const Module *) const {
   LBPI->getCalculated().print(OS);
 }
 
 void LazyBranchProbabilityInfoPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  // We require DT so it's available if -break-crit-edges (which will keep both
+  // DT and LI updated if they exist) is run before.
+  // Else -break-crit-edges will hit an assert when updating LI (due to missing
+  // DT).
+  AU.addRequired<DominatorTreeWrapperPass>();
   AU.addRequired<LoopInfoWrapperPass>();
   AU.addRequired<TargetLibraryInfoWrapperPass>();
   AU.setPreservesAll();
 }
 
 void LazyBranchProbabilityInfoPass::releaseMemory() { LBPI.reset(); }
 
 bool LazyBranchProbabilityInfoPass::runOnFunction(Function &F) {

test/Transforms/Util/PR37334-break-crit-edges-require-dt.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -loop-sink -break-crit-edges -branch-prob -S | FileCheck %s
+; RUN: opt < %s -loop-sink -break-crit-edges -lazy-block-freq -S | FileCheck %s
+; RUN: opt < %s -loop-sink -break-crit-edges -lazy-branch-prob -S | FileCheck %s
+
+; BreakCriticalEdges tries to update LI and DT if they are present. However,
+; updating LI actually needs a DT, so we now require DT in
+; BranchProbabilityInfo/LazyBlockFrequencyInfo/LazyBranchProbabilityInfo so it
+; is indeed available when LI is.
+
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @f1() {
+; CHECK-LABEL: @f1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    br i1 false, label [[FOR_BODY:%.*]], label [[FOR_COND_FOR_END_CRIT_EDGE:%.*]]
+; CHECK:       for.cond.for.end_crit_edge:
+; CHECK-NEXT:    br label [[FOR_END:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    br i1 true, label [[FOR_ENDSPLIT:%.*]], label [[FOR_INC:%.*]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    br label [[FOR_COND]]
+; CHECK:       for.endsplit:
+; CHECK-NEXT:    br label [[FOR_END]]
+; CHECK:       for.end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  br i1 undef, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  br i1 undef, label %for.end, label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  br label %for.cond
+
+for.end:                                          ; preds = %for.body, %for.cond
+  ret void
+}