diff --git a/llvm/include/llvm/CodeGen/GlobalISel/CSEMIRBuilder.h b/llvm/include/llvm/CodeGen/GlobalISel/CSEMIRBuilder.h
--- a/llvm/include/llvm/CodeGen/GlobalISel/CSEMIRBuilder.h
+++ b/llvm/include/llvm/CodeGen/GlobalISel/CSEMIRBuilder.h
@@ -32,7 +32,10 @@
 class CSEMIRBuilder : public MachineIRBuilder {
 
   /// Returns true if A dominates B (within the same basic block).
-  /// Both iterators must be in the same basic block.
+  /// Both iterators must be in the same basic block. Note that if there are
+  /// more than a set threshold of instructions scanned during computation,
+  /// this will return false and exit early. Therefore, returning false does
+  /// not necessarily imply that A does *not* dominate B.
   //
   // TODO: Another approach for checking dominance is having two iterators and
   // making them go towards each other until they meet or reach begin/end. Which
diff --git a/llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp b/llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp
--- a/llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp
+++ b/llvm/lib/CodeGen/GlobalISel/CSEMIRBuilder.cpp
@@ -17,6 +17,12 @@
 
 using namespace llvm;
 
+static cl::opt<unsigned>
+    DominatesSearchThreshold("csemib-dom-threshold",
+                             cl::desc("Max number of instructions to scan for "
+                                      "CSEMIRBuilder inst dominance checks"),
+                             cl::init(10000), cl::Hidden);
+
 bool CSEMIRBuilder::dominates(MachineBasicBlock::const_iterator A,
                               MachineBasicBlock::const_iterator B) const {
   auto MBBEnd = getMBB().end();
@@ -26,8 +32,11 @@
          "Iterators should be in same block");
   const MachineBasicBlock *BBA = A->getParent();
   MachineBasicBlock::const_iterator I = BBA->begin();
-  for (; &*I != A && &*I != B; ++I)
-    ;
+  for (unsigned Count = 0; &*I != A && &*I != B; ++I, ++Count) {
+    if (Count > DominatesSearchThreshold)
+      return false; // Conservatively return false.
+  }
+
   return &*I == A;
 }
 
diff --git a/llvm/lib/CodeGen/GlobalISel/Localizer.cpp b/llvm/lib/CodeGen/GlobalISel/Localizer.cpp
--- a/llvm/lib/CodeGen/GlobalISel/Localizer.cpp
+++ b/llvm/lib/CodeGen/GlobalISel/Localizer.cpp
@@ -14,6 +14,7 @@
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetLowering.h"
+#include "llvm/IR/Constants.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/Debug.h"
 
@@ -21,6 +22,12 @@
 
 using namespace llvm;
 
+static cl::opt<unsigned>
+    IntraBlockScanThreshold("localizer-intrablock-scan-threshold",
+                            cl::desc("Max number of unrelated insts to scan "
+                                     "over during intra-block localization."),
+                            cl::init(100000), cl::Hidden);
+
 char Localizer::ID = 0;
 INITIALIZE_PASS_BEGIN(Localizer, DEBUG_TYPE,
                       "Move/duplicate certain instructions close to their use",
@@ -149,9 +156,22 @@
       continue;
 
     MachineBasicBlock::iterator II(MI);
+    // Once again don't try to scan over every instruction past a threshold.
+    // For some pathological cases with extremely large basic blocks, don't try
+    // to scan beyond a certain threshold, since this is potentially O(N^2).
+    unsigned Count = 0;
+    bool ExitedEarly = false;
     ++II;
-    while (II != MBB.end() && !Users.count(&*II))
+    Count = 0;
+    while (II != MBB.end() && !Users.count(&*II)) {
+      if (++Count > IntraBlockScanThreshold) {
+        ExitedEarly = true;
+        break;
+      }
       ++II;
+    }
+    if (ExitedEarly)
+      continue;
 
     LLVM_DEBUG(dbgs() << "Intra-block: moving " << *MI << " before " << *&*II
                       << "\n");