diff --git a/llvm/include/llvm/CodeGen/GlobalISel/Legalizer.h b/llvm/include/llvm/CodeGen/GlobalISel/Legalizer.h
--- a/llvm/include/llvm/CodeGen/GlobalISel/Legalizer.h
+++ b/llvm/include/llvm/CodeGen/GlobalISel/Legalizer.h
@@ -21,6 +21,7 @@
 #define LLVM_CODEGEN_GLOBALISEL_LEGALIZEMACHINEIRPASS_H
 
 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 
 namespace llvm {
@@ -41,6 +42,8 @@
   /// Initialize the field members using \p MF.
   void init(MachineFunction &MF);
 
+  SlotIndexes *Indexes;
+
 public:
   // Ctor, nothing fancy.
   Legalizer();
diff --git a/llvm/include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h b/llvm/include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h
--- a/llvm/include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h
+++ b/llvm/include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h
@@ -18,6 +18,7 @@
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/SlotIndexes.h"
 #include "llvm/CodeGen/TargetOpcodes.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DebugLoc.h"
@@ -53,6 +54,8 @@
   GISelChangeObserver *Observer = nullptr;
 
   GISelCSEInfo *CSEInfo = nullptr;
+
+  SlotIndexes *Indexes = nullptr;
 };
 
 class DstOp {
@@ -300,6 +303,9 @@
   GISelCSEInfo *getCSEInfo() { return State.CSEInfo; }
   const GISelCSEInfo *getCSEInfo() const { return State.CSEInfo; }
 
+  SlotIndexes *getSlotIndexes() { return State.Indexes; }
+  const SlotIndexes *getSlotIndexes() const { return State.Indexes; }
+
   /// Current insertion point for new instructions.
   MachineBasicBlock::iterator getInsertPt() { return State.II; }
 
@@ -317,6 +323,8 @@
 
   void setCSEInfo(GISelCSEInfo *Info) { State.CSEInfo = Info; }
 
+  void setSlotIndexes(SlotIndexes *indexes) { State.Indexes = indexes; }
+
   /// \name Setters for the insertion point.
   /// @{
   /// Set the MachineFunction where to build instructions.
@@ -368,7 +376,14 @@
   ///
   /// \return a MachineInstrBuilder for the newly created instruction.
   MachineInstrBuilder buildInstr(unsigned Opcode) {
-    return insertInstr(buildInstrNoInsert(Opcode));
+    auto MIB = insertInstr(buildInstrNoInsert(Opcode));
+    if (State.Indexes) {
+      // We need to repair the range around the newly created instruction.
+      auto Begin = MIB->getIterator();
+      auto End = std::next(Begin);
+      State.Indexes->repairIndexesInRange(&getMBB(), Begin, End);
+    }
+    return MIB;
   }
 
   /// Build but don't insert <empty> = \p Opcode <empty>.
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
@@ -13,6 +13,7 @@
 
 #include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 
 using namespace llvm;
@@ -24,6 +25,13 @@
     return true;
   assert(A->getParent() == B->getParent() &&
          "Iterators should be in same block");
+
+  const SlotIndexes *Indexes = getSlotIndexes();
+  if (Indexes) {
+    SlotIndex SlotA = Indexes->getInstructionIndex(*A);
+    SlotIndex SlotB = Indexes->getInstructionIndex(*B);
+    return SlotIndex::isEarlierInstr(SlotA, SlotB);
+  }
   const MachineBasicBlock *BBA = A->getParent();
   MachineBasicBlock::const_iterator I = BBA->begin();
   for (; &*I != A && &*I != B; ++I)
@@ -48,7 +56,15 @@
       // this builder will have the def ready.
       setInsertPt(*CurMBB, std::next(MII));
     } else if (!dominates(MI, CurrPos)) {
+      ++MII;
       CurMBB->splice(CurrPos, CurMBB, MI);
+      auto *SlotIndexes = getSlotIndexes();
+      if (SlotIndexes) {
+        getSlotIndexes()->removeSingleMachineInstrFromMaps(*MI);
+        // Repair slot indices for the modified range.
+        getSlotIndexes()->repairIndexesInRange(
+            CurMBB, MachineBasicBlock::iterator(MI), MII);
+      }
     }
     return MachineInstrBuilder(getMF(), MI);
   }
diff --git a/llvm/lib/CodeGen/GlobalISel/Legalizer.cpp b/llvm/lib/CodeGen/GlobalISel/Legalizer.cpp
--- a/llvm/lib/CodeGen/GlobalISel/Legalizer.cpp
+++ b/llvm/lib/CodeGen/GlobalISel/Legalizer.cpp
@@ -23,8 +23,10 @@
 #include "llvm/CodeGen/GlobalISel/LegalizerHelper.h"
 #include "llvm/CodeGen/GlobalISel/LostDebugLocObserver.h"
 #include "llvm/CodeGen/GlobalISel/Utils.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/SlotIndexes.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/InitializePasses.h"
@@ -72,6 +74,7 @@
                       false)
 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
 INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
 INITIALIZE_PASS_END(Legalizer, DEBUG_TYPE,
                     "Legalize the Machine IR a function's Machine IR", false,
                     false)
@@ -82,6 +85,7 @@
   AU.addRequired<TargetPassConfig>();
   AU.addRequired<GISelCSEAnalysisWrapperPass>();
   AU.addPreserved<GISelCSEAnalysisWrapperPass>();
+  AU.addRequiredTransitive<SlotIndexes>();
   getSelectionDAGFallbackAnalysisUsage(AU);
   MachineFunctionPass::getAnalysisUsage(AU);
 }
@@ -162,6 +166,21 @@
     createdOrChangedInstr(MI);
   }
 };
+
+class SlotIndexDeletionObserver : public GISelChangeObserver {
+  SlotIndexes *Indexes;
+
+public:
+  SlotIndexDeletionObserver(SlotIndexes *indexes) : Indexes(indexes) {}
+
+  void erasingInstr(MachineInstr &MI) override {
+    LLVM_DEBUG(dbgs() << "Removing MI: " << MI << " from SlotIndexes");
+    Indexes->removeSingleMachineInstrFromMaps(MI);
+  }
+  void createdInstr(MachineInstr &MI) override {}
+  void changingInstr(MachineInstr &MI) override {}
+  void changedInstr(MachineInstr &MI) override {}
+};
 } // namespace
 
 Legalizer::MFResult
@@ -317,6 +336,7 @@
   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
   GISelCSEAnalysisWrapper &Wrapper =
       getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
+  Indexes = &getAnalysis<SlotIndexes>();
   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
 
   const size_t NumBlocks = MF.size();
@@ -333,11 +353,14 @@
   } else
     MIRBuilder = std::make_unique<MachineIRBuilder>();
 
+  MIRBuilder->setSlotIndexes(Indexes);
   SmallVector<GISelChangeObserver *, 1> AuxObservers;
   if (EnableCSE && CSEInfo) {
     // We want CSEInfo in addition to WorkListObserver to observe all changes.
     AuxObservers.push_back(CSEInfo);
   }
+  SlotIndexDeletionObserver SIObserver(Indexes);
+  AuxObservers.push_back(&SIObserver);
   assert(!CSEInfo || !errorToBool(CSEInfo->verify()));
   LostDebugLocObserver LocObserver(DEBUG_TYPE);
   if (VerifyDebugLocs > DebugLocVerifyLevel::None)