Index: llvm/lib/Transforms/Utils/SimplifyCFG.cpp
===================================================================
--- llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -2688,8 +2688,20 @@
     if (!OrigCE && !ThenCE)
       continue; // Known cheap (FIXME: Maybe not true for aggregates).
 
-    InstructionCost OrigCost = OrigCE ? computeSpeculationCost(OrigCE, TTI) : 0;
-    InstructionCost ThenCost = ThenCE ? computeSpeculationCost(ThenCE, TTI) : 0;
+    InstructionCost OrigCost = 0;
+    if (OrigCE) {
+      if (!isSafeToSpeculativelyExecute(OrigCE))
+        return false;
+      OrigCost = computeSpeculationCost(OrigCE, TTI);
+    }
+
+    InstructionCost ThenCost = 0;
+    if (ThenCE) {
+      if (!isSafeToSpeculativelyExecute(ThenCE))
+        return false;
+      ThenCost = computeSpeculationCost(ThenCE, TTI);
+    }
+
     InstructionCost MaxCost =
         2 * PHINodeFoldingThreshold * TargetTransformInfo::TCC_Basic;
     if (OrigCost + ThenCost > MaxCost)
Index: llvm/test/Transforms/SimplifyCFG/issue-56038.ll
===================================================================
--- /dev/null
+++ llvm/test/Transforms/SimplifyCFG/issue-56038.ll
@@ -0,0 +1,23 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -simplifycfg < %s | FileCheck %s
+
+@_ZL1e = internal global [2 x i32] zeroinitializer
+@_ZL1d = internal global i32 0
+
+; This test used to crash
+define i32 @test(i1 %b) {
+; CHECK-LABEL: @test(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[COND_I:%.*]] = select i1 [[B:%.*]], i32 0, i32 srem (i32 zext (i1 icmp ne (ptr getelementptr inbounds ([2 x i32], ptr @_ZL1e, i64 0, i64 1), ptr @_ZL1d) to i32), i32 -1)
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  br i1 %b, label %f.exit, label %cond.false.i
+
+cond.false.i:                                     ; preds = %entry
+  br label %f.exit
+
+f.exit:                                       ; preds = %entry, %cond.false.i
+  %cond.i = phi i32 [ srem (i32 zext (i1 icmp ne (ptr getelementptr inbounds ([2 x i32], ptr @_ZL1e, i64 0, i64 1), ptr @_ZL1d) to i32), i32 -1), %cond.false.i ], [ 0, %entry ]
+  ret i32 0
+}