diff --git a/llvm/lib/IR/Instruction.cpp b/llvm/lib/IR/Instruction.cpp
--- a/llvm/lib/IR/Instruction.cpp
+++ b/llvm/lib/IR/Instruction.cpp
@@ -691,6 +691,11 @@
 }
 
 bool Instruction::isSafeToRemove() const {
+  if (const auto *CI = dyn_cast<ConstrainedFPIntrinsic>(this)) {
+    Optional<fp::ExceptionBehavior> EB = CI->getExceptionBehavior();
+    if (EB && EB != fp::ExceptionBehavior::ebStrict)
+      return true;
+  }
   return (!isa<CallInst>(this) || !this->mayHaveSideEffects()) &&
          !this->isTerminator();
 }
diff --git a/llvm/lib/Transforms/Utils/SCCPSolver.cpp b/llvm/lib/Transforms/Utils/SCCPSolver.cpp
--- a/llvm/lib/Transforms/Utils/SCCPSolver.cpp
+++ b/llvm/lib/Transforms/Utils/SCCPSolver.cpp
@@ -292,7 +292,7 @@
   void visitSelectInst(SelectInst &I);
   void visitUnaryOperator(Instruction &I);
   void visitBinaryOperator(Instruction &I);
-  void visitCmpInst(CmpInst &I);
+  void visitCmpInst(Instruction &I);
   void visitExtractValueInst(ExtractValueInst &EVI);
   void visitInsertValueInst(InsertValueInst &IVI);
 
@@ -985,7 +985,9 @@
 
   // If either of the operands is a constant, try to fold it to a constant.
   // TODO: Use information from notconstant better.
-  if ((V1State.isConstant() || V2State.isConstant())) {
+  if ((V1State.isConstant() || V2State.isConstant()) &&
+      !isa<ConstrainedFPIntrinsic>(I)) {
+    // FIXME: SimplifyBinOp() doesn't understand constrained intrinsics.
     Value *V1 = isConstant(V1State) ? getConstant(V1State) : I.getOperand(0);
     Value *V2 = isConstant(V2State) ? getConstant(V2State) : I.getOperand(1);
     Value *R = SimplifyBinOp(I.getOpcode(), V1, V2, SimplifyQuery(DL));
@@ -1025,8 +1027,9 @@
   // point types, like and <4 x i32> overdefined, zeroinitializer.
 }
 
-// Handle ICmpInst instruction.
-void SCCPInstVisitor::visitCmpInst(CmpInst &I) {
+// Handle ICmpInst and FCmpInst instruction.
+void SCCPInstVisitor::visitCmpInst(Instruction &I) {
+  assert((isa<CmpInst>(I) || isa<ConstrainedFPCmpIntrinsic>(I)) && "Wrong class of Instruction!");
   // Do not cache this lookup, getValueState calls later in the function might
   // invalidate the reference.
   if (isOverdefined(ValueState[&I]))
@@ -1040,7 +1043,16 @@
   auto V1State = getValueState(Op1);
   auto V2State = getValueState(Op2);
 
-  Constant *C = V1State.getCompare(I.getPredicate(), I.getType(), V2State);
+  FCmpInst::Predicate IPred;
+  if (isa<CmpInst>(I)) {
+    CmpInst *CI = cast<CmpInst>(&I);
+    IPred = CI->getPredicate();
+  }
+  else {
+    ConstrainedFPCmpIntrinsic *CCI = cast<ConstrainedFPCmpIntrinsic>(&I);
+    IPred = CCI->getPredicate();
+  }
+  Constant *C = V1State.getCompare(IPred, I.getType(), V2State);
   if (C) {
     if (isa<UndefValue>(C))
       return;
@@ -1178,6 +1190,32 @@
 }
 
 void SCCPInstVisitor::visitCallBase(CallBase &CB) {
+  auto *CFP = dyn_cast<ConstrainedFPIntrinsic>(&CB);
+  if (CFP) {
+    switch ((Intrinsic::ID)CFP->getIntrinsicID()) {
+    case Intrinsic::experimental_constrained_fadd:
+    case Intrinsic::experimental_constrained_fsub:
+    case Intrinsic::experimental_constrained_fmul:
+    case Intrinsic::experimental_constrained_fdiv:
+    case Intrinsic::experimental_constrained_frem:
+      return (void) visitBinaryOperator(CB);
+      break;
+    case Intrinsic::experimental_constrained_fptosi:
+    case Intrinsic::experimental_constrained_sitofp:
+    case Intrinsic::experimental_constrained_fptoui:
+    case Intrinsic::experimental_constrained_uitofp:
+      // FIXME: return (void) visitCastInst(CB);
+      break;
+    case Intrinsic::experimental_constrained_fcmp:
+    case Intrinsic::experimental_constrained_fcmps:
+      return (void) visitCmpInst(CB);
+      break;
+    default:
+      // We only examine the constrained intrinsics that replace
+      // llvm instructions.
+      break;
+    }
+  }
   handleCallResult(CB);
   handleCallArguments(CB);
 }
diff --git a/llvm/test/Transforms/SCCP/strictfp-float-nan-simplification.ll b/llvm/test/Transforms/SCCP/strictfp-float-nan-simplification.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/SCCP/strictfp-float-nan-simplification.ll
@@ -0,0 +1,77 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes=sccp -S %s | FileCheck %s
+
+; This test, derived from another, tests coverage of binary operators
+; when using constrained intrinsics.
+
+; When marking the edge from bb2 -> exit as executable first, %p will be NaN
+; first and %v.1 will simplify to NaN. But when marking bb1 -> exit executable,
+; %p will we overdefined and %v.1 will be simplified to 0.0. Make sure we go to
+; overdefined, instead of crashing.
+; TODO: Can we do better, i.e. choose the 'conservative' 0.0 initially?
+define float @test1(float %a, i1 %bc) #0 {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[BC:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[P:%.*]] = phi float [ [[A:%.*]], [[BB1]] ], [ 0x7FF8000000000000, [[BB2]] ]
+; CHECK-NEXT:    [[V_1:%.*]] = call float @llvm.experimental.constrained.fmul.f32(float [[P]], float 0.000000e+00, metadata !"round.dynamic", metadata !"fpexcept.maytrap") #[[ATTR0:[0-9]+]]
+; CHECK-NEXT:    [[V_2:%.*]] = call float @llvm.experimental.constrained.fadd.f32(float [[V_1]], float 0xFFF8000000000000, metadata !"round.dynamic", metadata !"fpexcept.maytrap") #[[ATTR0]]
+; CHECK-NEXT:    ret float [[V_2]]
+;
+entry:
+  br i1 %bc, label %bb1, label %bb2
+
+bb1:
+  br label %exit
+
+bb2:
+  br label %exit
+
+exit:
+  %p = phi float [ %a, %bb1 ], [ 0x7FF8000000000000, %bb2 ]
+  %v.1 = call float @llvm.experimental.constrained.fmul.f32(float %p, float 0.000000e+00, metadata !"round.dynamic", metadata !"fpexcept.maytrap") #0
+  %v.2 = call float @llvm.experimental.constrained.fadd.f32(float %v.1, float 0xFFF8000000000000, metadata !"round.dynamic", metadata !"fpexcept.maytrap") #0
+  ret float %v.2
+}
+
+; Same as @test1, but with the incoming values switched.
+define float @test2(float %a, i1 %bc) #0 {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[BC:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[P:%.*]] = phi float [ 0x7FF8000000000000, [[BB1]] ], [ [[A:%.*]], [[BB2]] ]
+; CHECK-NEXT:    [[V_1:%.*]] = call float @llvm.experimental.constrained.fmul.f32(float [[P]], float 0.000000e+00, metadata !"round.dynamic", metadata !"fpexcept.maytrap") #[[ATTR0]]
+; CHECK-NEXT:    [[V_2:%.*]] = call float @llvm.experimental.constrained.fadd.f32(float [[V_1]], float 0xFFF8000000000000, metadata !"round.dynamic", metadata !"fpexcept.maytrap") #[[ATTR0]]
+; CHECK-NEXT:    ret float [[V_2]]
+;
+entry:
+  br i1 %bc, label %bb1, label %bb2
+
+bb1:
+  br label %exit
+
+bb2:
+  br label %exit
+
+exit:
+  %p = phi float [ 0x7FF8000000000000, %bb1 ], [ %a, %bb2 ]
+  %v.1 = call float @llvm.experimental.constrained.fmul.f32(float %p, float 0.000000e+00, metadata !"round.dynamic", metadata !"fpexcept.maytrap") #0
+  %v.2 = call float @llvm.experimental.constrained.fadd.f32(float %v.1, float 0xFFF8000000000000, metadata !"round.dynamic", metadata !"fpexcept.maytrap") #0
+  ret float %v.2
+}
+
+attributes #0 = { strictfp }
+
+declare float @llvm.experimental.constrained.fadd.f32(float, float, metadata, metadata)
+declare float @llvm.experimental.constrained.fmul.f32(float, float, metadata, metadata)
+
diff --git a/llvm/test/Transforms/SCCP/strictfp-phis.ll b/llvm/test/Transforms/SCCP/strictfp-phis.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Transforms/SCCP/strictfp-phis.ll
@@ -0,0 +1,249 @@
+; RUN: opt < %s -passes=sccp -S | FileCheck %s
+
+define i1 @float.1.defaultenv(i1 %cmp) #0 {
+; CHECK-LABEL: define i1 @float.1.defaultenv(i1 %cmp) #0 {
+
+; CHECK-LABEL: end:
+; CHECK-NEXT:    ret i1 true
+;
+entry:
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  br label %end
+
+end:
+  %p = phi float [ 1.0, %entry ], [ 1.0, %if.true]
+  %c = call i1 @llvm.experimental.constrained.fcmp.i1.f32(float %p, float 1.0, metadata !"ueq", metadata !"fpexcept.ignore") #0
+
+  ret i1 %c
+}
+
+define i1 @float.1.maytrap(i1 %cmp) #0 {
+; CHECK-LABEL: define i1 @float.1.maytrap(i1 %cmp) #0 {
+
+; CHECK-LABEL: end:
+; CHECK-NEXT:    ret i1 true
+;
+entry:
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  br label %end
+
+end:
+  %p = phi float [ 1.0, %entry ], [ 1.0, %if.true]
+  %c = call i1 @llvm.experimental.constrained.fcmp.i1.f32(float %p, float 1.0, metadata !"ueq", metadata !"fpexcept.maytrap") #0
+
+  ret i1 %c
+}
+
+define i1 @float.1.strict(i1 %cmp) #0 {
+; CHECK-LABEL: define i1 @float.1.strict(i1 %cmp) #0 {
+
+; CHECK-LABEL: end:
+; CHECK-NEXT:    %c = call i1 @llvm.experimental.constrained.fcmp.f32(float 1.000000e+00, float 1.000000e+00, metadata !"ueq", metadata !"fpexcept.strict") #0
+; CHECK-NEXT:    ret i1 true
+;
+entry:
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  br label %end
+
+end:
+  %p = phi float [ 1.0, %entry ], [ 1.0, %if.true]
+  %c = call i1 @llvm.experimental.constrained.fcmp.i1.f32(float %p, float 1.0, metadata !"ueq", metadata !"fpexcept.strict") #0
+
+  ret i1 %c
+}
+
+define i1 @float.2.defaultenv(i1 %cmp) #0 {
+; CHECK-LABEL: define i1 @float.2.defaultenv(i1 %cmp) #0 {
+
+; CHECK-LABEL: end:
+; CHECK-NEXT:    %p = phi float [ 1.000000e+00, %entry ], [ 2.000000e+00, %if.true ]
+; CHECK-NEXT:    %c = call i1 @llvm.experimental.constrained.fcmp.f32(float %p, float 1.000000e+00, metadata !"ueq", metadata !"fpexcept.ignore") #0
+; CHECK-NEXT:    ret i1 %c
+;
+entry:
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  br label %end
+
+end:
+  %p = phi float [ 1.0, %entry ], [ 2.0, %if.true]
+  %c = call i1 @llvm.experimental.constrained.fcmp.i1.f32(float %p, float 1.0, metadata !"ueq", metadata !"fpexcept.ignore") #0
+  ret i1 %c
+}
+
+define i1 @float.2.maytrap(i1 %cmp) #0 {
+; CHECK-LABEL: define i1 @float.2.maytrap(i1 %cmp) #0 {
+
+; CHECK-LABEL: end:
+; CHECK-NEXT:    %p = phi float [ 1.000000e+00, %entry ], [ 2.000000e+00, %if.true ]
+; CHECK-NEXT:    %c = call i1 @llvm.experimental.constrained.fcmp.f32(float %p, float 1.000000e+00, metadata !"ueq", metadata !"fpexcept.maytrap") #0
+; CHECK-NEXT:    ret i1 %c
+;
+entry:
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  br label %end
+
+end:
+  %p = phi float [ 1.0, %entry ], [ 2.0, %if.true]
+  %c = call i1 @llvm.experimental.constrained.fcmp.i1.f32(float %p, float 1.0, metadata !"ueq", metadata !"fpexcept.maytrap") #0
+  ret i1 %c
+}
+
+define i1 @float.2.strict(i1 %cmp) #0 {
+; CHECK-LABEL: define i1 @float.2.strict(i1 %cmp) #0 {
+
+; CHECK-LABEL: end:
+; CHECK-NEXT:    %p = phi float [ 1.000000e+00, %entry ], [ 2.000000e+00, %if.true ]
+; CHECK-NEXT:    %c = call i1 @llvm.experimental.constrained.fcmp.f32(float %p, float 1.000000e+00, metadata !"ueq", metadata !"fpexcept.strict") #0
+; CHECK-NEXT:    ret i1 %c
+;
+entry:
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  br label %end
+
+end:
+  %p = phi float [ 1.0, %entry ], [ 2.0, %if.true]
+  %c = call i1 @llvm.experimental.constrained.fcmp.i1.f32(float %p, float 1.0, metadata !"ueq", metadata !"fpexcept.strict") #0
+  ret i1 %c
+}
+
+define i1 @float.3.defaultenv(float %f, i1 %cmp) #0 {
+; CHECK-LABEL: define i1 @float.3.defaultenv(float %f, i1 %cmp) #0
+
+; CHECK-LABEL: end:
+; CHECK-NEXT:    %p = phi float [ 1.000000e+00, %entry ], [ %f, %if.true ]
+; CHECK-NEXT:    %c = call i1 @llvm.experimental.constrained.fcmp.f32(float %p, float 1.000000e+00, metadata !"ueq", metadata !"fpexcept.ignore") #0
+; CHECK-NEXT:    ret i1 %c
+;
+entry:
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  br label %end
+
+end:
+  %p = phi float [ 1.0, %entry ], [ %f, %if.true]
+  %c = call i1 @llvm.experimental.constrained.fcmp.i1.f32(float %p, float 1.0, metadata !"ueq", metadata !"fpexcept.ignore") #0
+  ret i1 %c
+}
+
+define i1 @float.3.maytrap(float %f, i1 %cmp) #0 {
+; CHECK-LABEL: define i1 @float.3.maytrap(float %f, i1 %cmp) #0
+
+; CHECK-LABEL: end:
+; CHECK-NEXT:    %p = phi float [ 1.000000e+00, %entry ], [ %f, %if.true ]
+; CHECK-NEXT:    %c = call i1 @llvm.experimental.constrained.fcmp.f32(float %p, float 1.000000e+00, metadata !"ueq", metadata !"fpexcept.maytrap") #0
+; CHECK-NEXT:    ret i1 %c
+;
+entry:
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  br label %end
+
+end:
+  %p = phi float [ 1.0, %entry ], [ %f, %if.true]
+  %c = call i1 @llvm.experimental.constrained.fcmp.i1.f32(float %p, float 1.0, metadata !"ueq", metadata !"fpexcept.maytrap") #0
+  ret i1 %c
+}
+
+define i1 @float.3.strict(float %f, i1 %cmp) #0 {
+; CHECK-LABEL: define i1 @float.3.strict(float %f, i1 %cmp) #0
+
+; CHECK-LABEL: end:
+; CHECK-NEXT:    %p = phi float [ 1.000000e+00, %entry ], [ %f, %if.true ]
+; CHECK-NEXT:    %c = call i1 @llvm.experimental.constrained.fcmp.f32(float %p, float 1.000000e+00, metadata !"ueq", metadata !"fpexcept.strict") #0
+; CHECK-NEXT:    ret i1 %c
+;
+entry:
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  br label %end
+
+end:
+  %p = phi float [ 1.0, %entry ], [ %f, %if.true]
+  %c = call i1 @llvm.experimental.constrained.fcmp.i1.f32(float %p, float 1.0, metadata !"ueq", metadata !"fpexcept.strict") #0
+  ret i1 %c
+}
+
+define i1 @float.4_unreachable.defaultenv(float %f, i1 %cmp) #0 {
+; CHECK-LABEL: define i1 @float.4_unreachable.defaultenv(float %f, i1 %cmp) #0
+
+; CHECK-LABEL: end:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  br label %end
+
+dead:
+  br label %end
+
+end:
+  %p = phi float [ 1.0, %entry ], [ 1.0, %if.true], [ %f, %dead ]
+  %c = call i1 @llvm.experimental.constrained.fcmp.i1.f32(float %p, float 1.0, metadata !"une", metadata !"fpexcept.ignore") #0
+  ret i1 %c
+}
+
+define i1 @float.4_unreachable.maytrap(float %f, i1 %cmp) #0 {
+; CHECK-LABEL: define i1 @float.4_unreachable.maytrap(float %f, i1 %cmp) #0
+
+; CHECK-LABEL: end:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  br label %end
+
+dead:
+  br label %end
+
+end:
+  %p = phi float [ 1.0, %entry ], [ 1.0, %if.true], [ %f, %dead ]
+  %c = call i1 @llvm.experimental.constrained.fcmp.i1.f32(float %p, float 1.0, metadata !"une", metadata !"fpexcept.maytrap") #0
+  ret i1 %c
+}
+
+; FIXME: It's a shame we can't eliminate this fcmp here:
+define i1 @float.4_unreachable.strict(float %f, i1 %cmp) #0 {
+; CHECK-LABEL: define i1 @float.4_unreachable.strict(float %f, i1 %cmp) #0
+
+; CHECK-LABEL: end:
+; CHECK-NEXT:    %c = call i1 @llvm.experimental.constrained.fcmp.f32(float 1.000000e+00, float 1.000000e+00, metadata !"une", metadata !"fpexcept.strict") #0
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  br i1 %cmp, label %if.true, label %end
+
+if.true:
+  br label %end
+
+dead:
+  br label %end
+
+end:
+  %p = phi float [ 1.0, %entry ], [ 1.0, %if.true], [ %f, %dead ]
+  %c = call i1 @llvm.experimental.constrained.fcmp.i1.f32(float %p, float 1.0, metadata !"une", metadata !"fpexcept.strict") #0
+  ret i1 %c
+}
+
+attributes #0 = { strictfp }
+
+declare i1 @llvm.experimental.constrained.fcmp.i1.f32(float, float, metadata, metadata)
+