Index: llvm/lib/Transforms/Scalar/NewGVN.cpp
===================================================================
--- llvm/lib/Transforms/Scalar/NewGVN.cpp
+++ llvm/lib/Transforms/Scalar/NewGVN.cpp
@@ -1074,6 +1074,7 @@
                                                  Value *Arg1, Value *Arg2,
                                                  Instruction *I) const {
   auto *E = new (ExpressionAllocator) BasicExpression(2);
+  const SimplifyQuery Q = SQ.getWithInstruction(I);
 
   E->setType(T);
   E->setOpcode(Opcode);
@@ -1089,7 +1090,7 @@
   E->op_push_back(lookupOperandLeader(Arg1));
   E->op_push_back(lookupOperandLeader(Arg2));
 
-  Value *V = simplifyBinOp(Opcode, E->getOperand(0), E->getOperand(1), SQ);
+  Value *V = simplifyBinOp(Opcode, E->getOperand(0), E->getOperand(1), Q);
   if (auto Simplified = checkExprResults(E, I, V)) {
     addAdditionalUsers(Simplified, I);
     return Simplified.Expr;
@@ -1145,6 +1146,7 @@
 
 NewGVN::ExprResult NewGVN::createExpression(Instruction *I) const {
   auto *E = new (ExpressionAllocator) BasicExpression(I->getNumOperands());
+  const SimplifyQuery Q = SQ.getWithInstruction(I);
 
   bool AllConstant = setBasicExpressionInfo(I, E);
 
@@ -1173,7 +1175,7 @@
     assert((E->getOperand(0)->getType() == I->getOperand(0)->getType() &&
             E->getOperand(1)->getType() == I->getOperand(1)->getType()));
     Value *V =
-        simplifyCmpInst(Predicate, E->getOperand(0), E->getOperand(1), SQ);
+        simplifyCmpInst(Predicate, E->getOperand(0), E->getOperand(1), Q);
     if (auto Simplified = checkExprResults(E, I, V))
       return Simplified;
   } else if (isa<SelectInst>(I)) {
@@ -1182,25 +1184,25 @@
       assert(E->getOperand(1)->getType() == I->getOperand(1)->getType() &&
              E->getOperand(2)->getType() == I->getOperand(2)->getType());
       Value *V = simplifySelectInst(E->getOperand(0), E->getOperand(1),
-                                    E->getOperand(2), SQ);
+                                    E->getOperand(2), Q);
       if (auto Simplified = checkExprResults(E, I, V))
         return Simplified;
     }
   } else if (I->isBinaryOp()) {
     Value *V =
-        simplifyBinOp(E->getOpcode(), E->getOperand(0), E->getOperand(1), SQ);
+        simplifyBinOp(E->getOpcode(), E->getOperand(0), E->getOperand(1), Q);
     if (auto Simplified = checkExprResults(E, I, V))
       return Simplified;
   } else if (auto *CI = dyn_cast<CastInst>(I)) {
     Value *V =
-        simplifyCastInst(CI->getOpcode(), E->getOperand(0), CI->getType(), SQ);
+        simplifyCastInst(CI->getOpcode(), E->getOperand(0), CI->getType(), Q);
     if (auto Simplified = checkExprResults(E, I, V))
       return Simplified;
   } else if (auto *GEPI = dyn_cast<GetElementPtrInst>(I)) {
     Value *V =
         simplifyGEPInst(GEPI->getSourceElementType(), *E->op_begin(),
                         makeArrayRef(std::next(E->op_begin()), E->op_end()),
-                        GEPI->isInBounds(), SQ);
+                        GEPI->isInBounds(), Q);
     if (auto Simplified = checkExprResults(E, I, V))
       return Simplified;
   } else if (AllConstant) {
Index: llvm/test/Transforms/NewGVN/sq-ctxi.ll
===================================================================
--- /dev/null
+++ llvm/test/Transforms/NewGVN/sq-ctxi.ll
@@ -0,0 +1,46 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes=newgvn -S | FileCheck %s
+
+; github issue #56039
+define i8 @src(i8* %a, i8* %b, i1 %c) {
+; CHECK-LABEL: @src(
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[LB1:%.*]] = load i8, i8* [[B:%.*]], align 1
+; CHECK-NEXT:    [[TOBOOL3_NOT_I:%.*]] = icmp eq i8 [[LB1]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL3_NOT_I]], label [[BB4:%.*]], label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    [[LB2:%.*]] = load i8, i8* [[B]], align 1
+; CHECK-NEXT:    [[CMP_NOT_I:%.*]] = icmp ult i8 0, [[LB2]]
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[CMP_NOT_I]])
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    [[LA:%.*]] = load i8, i8* [[A:%.*]], align 1
+; CHECK-NEXT:    br label [[BB4]]
+; CHECK:       bb4:
+; CHECK-NEXT:    ret i8 0
+;
+  br i1 %c, label %bb1, label %bb2
+
+bb1:
+  %lb1 = load i8, i8* %b
+  %tobool3.not.i = icmp eq i8 %lb1, 0
+  br i1 %tobool3.not.i, label %bb4, label %bb3
+
+bb2:
+  %lb2 = load i8, i8* %b
+  %cmp.not.i = icmp ult i8 0, %lb2
+  tail call void @llvm.assume(i1 %cmp.not.i)
+  br label %bb3
+
+bb3:
+  %p = phi i8 [ %lb1, %bb1 ], [ %lb2, %bb2 ]
+  %la = load i8, i8* %a
+  %xor = xor i8 %la, %p
+  br label %bb4
+
+bb4:
+  ret i8 0
+}
+
+declare void @llvm.assume(i1)