Index: lib/Analysis/BranchProbabilityInfo.cpp
===================================================================
--- lib/Analysis/BranchProbabilityInfo.cpp
+++ lib/Analysis/BranchProbabilityInfo.cpp
@@ -22,6 +22,7 @@
 #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"
@@ -1001,6 +1002,11 @@
 
 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();
Index: lib/Analysis/LazyBlockFrequencyInfo.cpp
===================================================================
--- lib/Analysis/LazyBlockFrequencyInfo.cpp
+++ lib/Analysis/LazyBlockFrequencyInfo.cpp
@@ -17,6 +17,7 @@
 #include "llvm/Analysis/LazyBlockFrequencyInfo.h"
 #include "llvm/Analysis/LazyBranchProbabilityInfo.h"
 #include "llvm/Analysis/LoopInfo.h"
+#include "llvm/IR/Dominators.h"
 
 using namespace llvm;
 
@@ -41,6 +42,11 @@
 
 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();
 }
Index: lib/Analysis/LazyBranchProbabilityInfo.cpp
===================================================================
--- lib/Analysis/LazyBranchProbabilityInfo.cpp
+++ lib/Analysis/LazyBranchProbabilityInfo.cpp
@@ -17,6 +17,7 @@
 #include "llvm/Analysis/LazyBranchProbabilityInfo.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/IR/Dominators.h"
 
 using namespace llvm;
 
@@ -42,6 +43,11 @@
 }
 
 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();
Index: test/Transforms/Util/PR37334-break-crit-edges-require-dt.ll
===================================================================
--- /dev/null
+++ test/Transforms/Util/PR37334-break-crit-edges-require-dt.ll
@@ -0,0 +1,44 @@
+; 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
+}