Index: lib/Transforms/Scalar/GVN.cpp
===================================================================
--- lib/Transforms/Scalar/GVN.cpp
+++ lib/Transforms/Scalar/GVN.cpp
@@ -1964,6 +1964,13 @@
       continue;
     }
 
+    // If "!A" is known true then A is known false.
+    // If "!A" is known false then A is known true.
+    if (match(LHS, m_Not(m_Value(A)))) {
+      Worklist.push_back(std::make_pair(A, ConstantExpr::getNot(CI)));
+      continue;
+    }
+
     // If we are propagating an equality like "(A == B)" == "true" then also
     // propagate the equality A == B.  When propagating a comparison such as
     // "(A >= B)" == "true", replace all instances of "A < B" with "false".
@@ -2123,6 +2130,32 @@
   uint32_t NextNum = VN.getNextUnusedValueNumber();
   unsigned Num = VN.lookup_or_add(I);
 
+  // Try to transform:
+  //   %isnotzero = icmp ne i32 %A, 0
+  //   %iszero = icmp eq i32 %A, 0
+  // to:
+  //   %isnotzero = icmp ne i32 %A, 0
+  //   %iszero = xor i1 %isnotzero, true
+  if (auto *Cmp = dyn_cast<CmpInst>(I)) {
+    CmpInst::Predicate NotPred = Cmp->getInversePredicate();
+    Value *LHS = Cmp->getOperand(0), *RHS = Cmp->getOperand(1);
+    uint32_t InverseNum =
+        VN.lookup_or_add_cmp(Cmp->getOpcode(), NotPred, LHS, RHS);
+    if (InverseNum < NextNum) {
+      if (Value *NotCmp = findLeader(Cmp->getParent(), InverseNum)) {
+        auto *InvertedNotCmp =
+            BinaryOperator::CreateNot(NotCmp, NotCmp->getName() + ".not", Cmp);
+        InvertedNotCmp->setDebugLoc(Cmp->getDebugLoc());
+        patchAndReplaceAllUsesWith(Cmp, InvertedNotCmp);
+        markInstructionForDeletion(Cmp);
+
+        // Update the availability map to include the new instruction.
+        addToLeaderTable(Num, InvertedNotCmp, InvertedNotCmp->getParent());
+        return true;
+      }
+    }
+  }
+
   // Allocations are always uniquely numbered, so we can save time and memory
   // by fast failing them.
   if (isa<AllocaInst>(I) || isa<TerminatorInst>(I) || isa<PHINode>(I)) {
Index: test/Transforms/GVN/pr27431.ll
===================================================================
--- /dev/null
+++ test/Transforms/GVN/pr27431.ll
@@ -0,0 +1,17 @@
+; RUN: opt -S -gvn < %s | FileCheck %s
+
+declare void @use(i1)
+
+define void @test1(i32 %A) {
+entry:
+  %iszero = icmp eq i32 %A, 0
+  %isnotzero = icmp ne i32 %A, 0
+  call void @use(i1 %iszero)
+  call void @use(i1 %isnotzero)
+  ret void
+; CHECK-LABEL: define void @test1(
+; CHECK: %[[iszero:.*]] = icmp eq i32 %A, 0
+; CHECK: %[[isnotzero:.*]] = xor i1 %[[iszero]], true
+; CHECK: call void @use(i1 %[[iszero]])
+; CHECK: call void @use(i1 %[[isnotzero]])
+}