diff --git a/llvm/include/llvm/CodeGen/PseudoSourceValue.h b/llvm/include/llvm/CodeGen/PseudoSourceValue.h
--- a/llvm/include/llvm/CodeGen/PseudoSourceValue.h
+++ b/llvm/include/llvm/CodeGen/PseudoSourceValue.h
@@ -93,7 +93,7 @@
 /// A specialized PseudoSourceValue for holding FixedStack values, which must
 /// include a frame index.
 class FixedStackPseudoSourceValue : public PseudoSourceValue {
-  int FI;
+  const int FI;
 
 public:
   explicit FixedStackPseudoSourceValue(int FI, const TargetInstrInfo &TII)
@@ -112,7 +112,6 @@
   void printCustom(raw_ostream &OS) const override;
 
   int getFrameIndex() const { return FI; }
-  void setFrameIndex(int FI) { this->FI = FI; }
 };
 
 class CallEntryPseudoSourceValue : public PseudoSourceValue {
diff --git a/llvm/lib/CodeGen/StackColoring.cpp b/llvm/lib/CodeGen/StackColoring.cpp
--- a/llvm/lib/CodeGen/StackColoring.cpp
+++ b/llvm/lib/CodeGen/StackColoring.cpp
@@ -960,6 +960,8 @@
   }
 
   // Remap all instructions to the new stack slots.
+  std::vector<std::vector<MachineMemOperand *>> SSRefs(
+      MFI->getObjectIndexEnd());
   for (MachineBasicBlock &BB : *MF)
     for (MachineInstr &I : BB) {
       // Skip lifetime markers. We'll remove them soon.
@@ -1025,13 +1027,14 @@
       SmallVector<MachineMemOperand *, 2> NewMMOs;
       bool ReplaceMemOps = false;
       for (MachineMemOperand *MMO : I.memoperands()) {
+        // Collect MachineMemOperands which reference
+        // FixedStackPseudoSourceValues with old frame indices.
         if (const auto *FSV = dyn_cast_or_null<FixedStackPseudoSourceValue>(
                 MMO->getPseudoValue())) {
           int FI = FSV->getFrameIndex();
           auto To = SlotRemap.find(FI);
           if (To != SlotRemap.end())
-            const_cast<FixedStackPseudoSourceValue *>(FSV)->setFrameIndex(
-                To->second);
+            SSRefs[FI].push_back(MMO);
         }
 
         // If this memory location can be a slot remapped here,
@@ -1071,6 +1074,15 @@
         I.setMemRefs(*MF, NewMMOs);
     }
 
+  // Rewrite MachineMemOperands that reference old frame indices.
+  for (auto E : enumerate(SSRefs))
+    if (!E.value().empty()) {
+      const PseudoSourceValue *NewSV =
+          MF->getPSVManager().getFixedStack(SlotRemap.find(E.index())->second);
+      for (MachineMemOperand *Ref : E.value())
+        Ref->setValue(NewSV);
+    }
+
   // Update the location of C++ catch objects for the MSVC personality routine.
   if (WinEHFuncInfo *EHInfo = MF->getWinEHFuncInfo())
     for (WinEHTryBlockMapEntry &TBME : EHInfo->TryBlockMap)
diff --git a/llvm/test/CodeGen/PowerPC/stack-coloring-vararg.mir b/llvm/test/CodeGen/PowerPC/stack-coloring-vararg.mir
--- a/llvm/test/CodeGen/PowerPC/stack-coloring-vararg.mir
+++ b/llvm/test/CodeGen/PowerPC/stack-coloring-vararg.mir
@@ -1,4 +1,16 @@
-# RUN: llc -o - %s -start-before=stack-coloring
+# RUN: llc -run-pass=stack-coloring %s -o - | FileCheck %s
+
+## Test %stack.1 is merged into %stack.0 and there is no MemoryMemOperand
+## referencing %stack.1. This regression test is sensitive to the StackColoring
+## algorithm. Please adjust or delete this test if the merging strategy
+## changes.
+
+# CHECK:    {{^}}stack:
+# CHECK-NEXT: - { id: 0,
+# CHECK-NOT:  - { id: 1,
+# CHECK:      - { id: 2,
+# CHECK-NOT: %stack.1
+
 --- |
   ; ModuleID = '<stdin>'
   source_filename = "<stdin>"