[GVN] Replace an inverted comparison with a logical not

[majnemer]

Summary

If we have two comparisons:

%iszero = icmp eq i32 %A, 0
%isnotzero = icmp ne i32 %A, 0

we should be able to turn one into the logical not of the other:

%iszero = icmp eq i32 %A, 0
%isnotzero = xor i1 %iszero, true

This fixes PR27431.

[gberry]

Do you think this would be worth adding to EarlyCSE as well since it could lead to simplifications that could effect inlining decisions?

[llvm-commits]

This looks fine to me.

• msg-5105-231.txt162 BDownload

[reames]

As a canonicalization, this makes sense, but I'm worried it will lead to bad code generation. Having to materialize a flag into a register to negate it seems potentially problematic. Do we already have code in the backend (CGP?) which undoes this transformation? If not, I think we're likely to need it.

[mcrosier]

Also, how does this impact the dominating condition optimizations in SimplifyCFG and JumpThreading? Those optimizations expect the dominated conditional branch to be fed by a compare rather than a not of the dominating compare.

[gberry]

@reames I believe CodeGenPrepare::SinkCmpExpressions already takes care of this.

@mcrosier I would guess that any cond branches that have not(c) as their condition would get simplified to use just 'c' and swap the branch targets, so I don't think this would impact the optimizations you mentioned.

[• dberlin]

My suggestion, given the comments on this thread, would be for someone to
make a decision (or build a consensus) on what the canonical form of this
kind of thing should look like, and then we just go and make everything do
that :P, whether it's the result david has produced, or compare over
compare, or whatever.

lib/Transforms/Scalar/GVN.cpp

while (!Worklist.empty()) {
     Value *A, *B;
     if ((isKnownTrue && match(LHS, m_And(m_Value(A), m_Value(B)))) ||
         (isKnownFalse && match(LHS, m_Or(m_Value(A), m_Value(B))))) {
       Worklist.push_back(std::make_pair(A, RHS));
       Worklist.push_back(std::make_pair(B, RHS));
       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".
     if (CmpInst *Cmp = dyn_cast<CmpInst>(LHS)) {
       Value *Op0 = Cmp->getOperand(0), *Op1 = Cmp->getOperand(1);
 
       // If "A == B" is known true, or "A != B" is known false, then replace
       // A with B everywhere in the scope.
bool GVN::processInstruction(Instruction *I) {
   // Instructions with void type don't return a value, so there's
   // no point in trying to find redundancies in them.
   if (I->getType()->isVoidTy())
     return false;
 
   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)) {
     addToLeaderTable(Num, I, I->getParent());
     return false;
   }
 
   // If the number we were assigned was a brand new VN, then we don't

test/Transforms/GVN/pr27431.ll

+; 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]])
+}