diff --git a/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
--- a/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
@@ -14384,6 +14384,10 @@
     }
   }
 
+  // The whole node may have been updated, so the value we were holding
+  // may no longer be valid. Re-fetch the operand we're `freeze`ing.
+  N0 = N->getOperand(0);
+
   // Finally, recreate the node, it's operands were updated to use
   // frozen operands, so we just need to use it's "original" operands.
   SmallVector<SDValue> Ops(N0->op_begin(), N0->op_end());
diff --git a/llvm/test/CodeGen/AArch64/pr59891-dagcombine-deleted-freeze.ll b/llvm/test/CodeGen/AArch64/pr59891-dagcombine-deleted-freeze.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/CodeGen/AArch64/pr59891-dagcombine-deleted-freeze.ll
@@ -0,0 +1,18 @@
+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mtriple=aarch64 | FileCheck %s
+
+; Freezing operand of an operation that is being freezed
+; may invalidate the whole SDValue we were trying to originally freeze.
+define i8 @pr59891(i64 %0) {
+; CHECK-LABEL: pr59891:
+; CHECK:       // %bb.0:
+; CHECK-NEXT:    mov w0, wzr
+; CHECK-NEXT:    ret
+  %2 = freeze i64 %0
+  %3 = trunc i64 %2 to i1
+  %4 = trunc i64 %0 to i1
+  %5 = xor i1 %3, %4
+  %6 = freeze i1 %5
+  %7 = zext i1 %6 to i8
+  ret i8 %7
+}