[InstCombine] Try harder to simplify ~(X & Y) -> ~X | ~Y and ~(X | Y) -> ~X & ~Y when X and Y have more than one uses.

[bmakam]

Summary

This is a fix for PR26083:
My first attempt to fix this was to skip CSE of compares that were input to idempotent instructions. But, this could leave redundant code and might inhibit inliner from inlining if the IR is bloated. This version enhances the instcombine to look for users where we can elide xor and clone those users if profitable.

[mssimpso]

This is a very basic question. But have you thought about enhancing instcombine to catch this case rather than preventing early-cse from optimizing it? It seems like the case you're aiming to prevent could exist without early-cse having created it.

[bmakam]

In D16978#346340, @mssimpso wrote:

This is a very basic question. But have you thought about enhancing instcombine to catch this case rather than preventing early-cse from optimizing it? It seems like the case you're aiming to prevent could exist without early-cse having created it.

Good question. I initially started off implementing an enhancement to instcombine. Specifically, whenever we see a candidate that can be simplified using DeMorgan's Law we currently check if the predicate has more than one use because we would want to avoid inverting the predicate for other users and cause a miscompile. I began implementing an enhancement which checked if all the uses of this predicate can be inverted but this requires walking the use-def chain and seemed very inefficient to catch this corner case. I also considered if we can move the Demorgan Laws simplification to instsimplify but that requires mutation of CFG so that is not possible. Another solution that I thought of in parallel to this solution is to clone the compare instruction during instcombine while applying DeMorgan's Law. However, this will be a performance neutral simplification in most cases as we will be trading an icmp for xor. So, I came up with this solution first to see if it fires for any of Spec2k6.

[majnemer]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1246

Functions should start with a lower case letter.

1247

Sentances start with an upper case letter.

1251–1253

Why?

1277–1285

Seems like we might do an awfully large amount of work. How large does Users typically get when this xform is profitable?

1289

What stops Users.size() from equaling zero?

1291

You are using cast_or_null but indiscriminately dereference the result, this seems wrong.

test/Transforms/InstCombine/not2.ll

3

This is too broad, please CHECK your tests more thoroughly.

[bmakam]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1277–1285

Sorry for late response. This was added to avoid unnecessarily commutating the operands of AND instruction when we could not elide a xor because it resulted in suboptimal codegen due to another issue that I am addressing in D17942. This is still on my plate and I plan to address the comments here once D17942 is landed.

[bmakam]

Refactored code addressing some review comments now that D17942 is landed.

[bmakam]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1251–1253

Only supporting for non vector types for now as the codegen for vector types is suboptimal.

1277–1285

I have refactored the code after landing D17942. To reduce the amount of work I am now checking only local users.

1291

Refactored code so that Users will always contain instructions.

test/Transforms/InstCombine/not2.ll

4

There is nothing more to test in these testcases other than checking if xor has been elided similar to the tests in test/Transforms/InstCombine/not.ll

[mcrosier]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1344

Perhaps you could move the isa<BinaryOperator> check into a separate if statement. IMO, it doesn't go with the comment above.

1349

This can be a cast<> rather than a dyn_cast<> because you've already checked we have a BO.

Alternatively, you could do the following to address the previous comment:

BinaryOperator *BO = dyn_cast<BinaryOperator>(V);
if (!BO)
  return false;

This will also decrease the indention.

1364

Is VI loop invariant? If so, please hoist this out of the loop. Also, I believe we know V is either a cmp or BO, so we can use a cast<> rather than a dyn_cast<>?

[mcrosier]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1344

Ignore this comment.. :)

1349

Ignore this one too..

[bmakam]

Address Chad's comments.

[majnemer]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1374–1375

Can't this be simplified to a range-based for loop?

[bmakam]

Address David's comments.

[bmakam]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1374–1375

Thanks David, I have simplified it to a range-based for loop.

[bmakam]

Minor fix to limit patch such that BinaryOp must be Add/Sub.

[bmakam]

another attempt to minor fix, sorry.

[mcrosier]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1350

This might read a bit better with something like:

if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V)) {
  // Must be an 'add' or a 'sub'.
  unsigned Opc = BO->getOpcode();
  if (Opc != Instruction::Add && Opc != Instruction::Sub)
    return false;
  // At least one operand must be a constant.
  if (!isa<Constant>(BO->getOperand(0)) &&
      !isa<Constant>(BO->getOperand(1)))
      return false;
}

Also, is it not the case that constants are always canonicalized to the RHS, which would mean the check on operands 0 is unnecessary?

[bmakam]

Update with Chad's suggestion.

[bmakam]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1350

IIRC, instcombine is still early to assume that that constants are always canonicalized to the RHS.

[mcrosier]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

1350

Okay, I just wanted to check. FWIW, the reassocation pass is responsible for the canonicalization.

[gberry]

Removing myself as others seem to be handling review

[mcrosier]

Just getting this off my queue. If you decide to pursue this further, please add me back as a reviewer, Balaram.

[bmakam]

Performance data was not promising, so abandoning this change.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (A->getType()->isIntegerTy(1) && B->getType()->isIntegerTy(1) &&
       Value *Not = Builder->CreateNot(LogicOp);
       return CastInst::CreateZExtOrBitCast(Not, I.getType());
     }
   }
 
   return nullptr;
 }
 
 Instruction *InstCombiner::foldCastedBitwiseLogic(BinaryOperator &I) {
   auto LogicOpc = I.getOpcode();
   assert((LogicOpc == Instruction::And || LogicOpc == Instruction::Or ||
           LogicOpc == Instruction::Xor) &&
          "Unexpected opcode for bitwise logic folding");
 
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   CastInst *Cast0 = dyn_cast<CastInst>(Op0);
   if (!Cast0)
     return nullptr;
 
   // This must be a cast from an integer or integer vector source type to allow
   // transformation of the logic operation to the source type.
   Type *DestTy = I.getType();
   Type *SrcTy = Cast0->getSrcTy();
   if (!SrcTy->isIntOrIntVectorTy())
     return nullptr;
 
   // If one operand is a bitcast and the other is a constant, move the logic
   // operation ahead of the bitcast. That is, do the logic operation in the
   // original type. This can eliminate useless bitcasts and allow normal
   // combines that would otherwise be impeded by the bitcast. Canonicalization
   // ensures that if there is a constant operand, it will be the second operand.
   Value *BC = nullptr;
   Constant *C = nullptr;
   if ((match(Op0, m_BitCast(m_Value(BC))) && match(Op1, m_Constant(C)))) {
     // A bitcast of a constant will be removed.
     Value *NewConstant = Builder->CreateBitCast(C, SrcTy);
     Value *NewOp = Builder->CreateBinOp(LogicOpc, BC, NewConstant, I.getName());
     return CastInst::CreateBitOrPointerCast(NewOp, DestTy);
   }
 
   CastInst *Cast1 = dyn_cast<CastInst>(Op1);
   if (!Cast1)
     return nullptr;
 
   // Both operands of the logic operation are casts. The casts must be of the
   // same type for reduction.
   auto CastOpcode = Cast0->getOpcode();
   if (CastOpcode != Cast1->getOpcode() || SrcTy != Cast1->getSrcTy())
     return nullptr;
 
   Value *Cast0Src = Cast0->getOperand(0);
   Value *Cast1Src = Cast1->getOperand(0);
 
   // fold (logic (cast A), (cast B)) -> (cast (logic A, B))
 
   // Only do this if the casts both really cause code to be generated.
   if ((!isa<ICmpInst>(Cast0Src) || !isa<ICmpInst>(Cast1Src)) &&
       ShouldOptimizeCast(CastOpcode, Cast0Src, DestTy) &&
       ShouldOptimizeCast(CastOpcode, Cast1Src, DestTy)) {
     Value *NewOp = Builder->CreateBinOp(LogicOpc, Cast0Src, Cast1Src,
                                         I.getName());
     return CastInst::Create(CastOpcode, NewOp, DestTy);
if (FCmp0 && FCmp1) {
     if (Res)
       return CastInst::Create(CastOpcode, Res, DestTy);
     return nullptr;
   }
 
   return nullptr;
 }
 
+static bool canInvertUsesOf(Value *V, InstCombiner &IC) {
+  // Handle trivial case.
+  if (V->hasOneUse())
+    return true;
+
+  // Bail out early for vector types, the code generator doesn't
+  // handle them well yet.
+  if (V->getType()->isVectorTy())
+    return false;
+
+  // Compares can be inverted if some of their uses are being modified to use
+  // the ~V.
+  if (!isa<CmpInst>(V) && !isa<BinaryOperator>(V))
+    return false;
+
+  // If `V` is of the form `A + Constant` then `-1 - V` can be folded into `(-1
+  // - Constant) - A` if we are willing to invert some of the uses.
+  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V))
+    if (BO->getOpcode() == Instruction::Add ||
+        BO->getOpcode() == Instruction::Sub)
+      if (!isa<Constant>(BO->getOperand(0)) &&
+          !isa<Constant>(BO->getOperand(1)))
+        return false;
+
+  // Add subset of local users that can be inverted to a worklist.
+  // Bail out early if it is not safe to invert.
+  SmallVector<Instruction *, 4> UserInsts;
+  auto *Inst = cast<Instruction>(V);
+  for (auto *U : V->users()) {
+    if (!U->hasOneUse())
+      return false;
+    if (dyn_castNotVal(U->user_back())) {
+      auto *UI = dyn_cast<Instruction>(U);
+      if (UI && (UI->getParent() == Inst->getParent()))
+        UserInsts.push_back(UI);
+    }
+  }
+
+  if (UserInsts.empty())
+    return false;
+
+  for (auto *InvertedUse : UserInsts) {
+    Instruction *NewI = Inst->clone();
+    NewI->setName(Inst->getName() + ".invert");
+    IC.InsertNewInstBefore(NewI, *Inst);
+    InvertedUse->replaceUsesOfWith(Inst, NewI);
+  }
+  return true;
+}
+
 Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
   bool Changed = SimplifyAssociativeOrCommutative(I);
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
   if (Value *V = SimplifyVectorOp(I))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = SimplifyAndInst(Op0, Op1, DL, TLI, DT, AC))
if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(NotOp)) {
           if (Op0I->getOpcode() == Instruction::And)
             return BinaryOperator::CreateOr(Op0NotVal, NotY);
           return BinaryOperator::CreateAnd(Op0NotVal, NotY);
         }
 
         // ~(X & Y) --> (~X | ~Y) - De Morgan's Law
         // ~(X | Y) === (~X & ~Y) - De Morgan's Law
         if (IsFreeToInvert(Op0I->getOperand(0),
-                           Op0I->getOperand(0)->hasOneUse()) &&
+                           canInvertUsesOf(Op0I->getOperand(0), *this)) &&
             IsFreeToInvert(Op0I->getOperand(1),
-                           Op0I->getOperand(1)->hasOneUse())) {
+                           canInvertUsesOf(Op0I->getOperand(1), *this))) {
           Value *NotX =
             Builder->CreateNot(Op0I->getOperand(0), "notlhs");
           Value *NotY =
             Builder->CreateNot(Op0I->getOperand(1), "notrhs");
           if (Op0I->getOpcode() == Instruction::And)
             return BinaryOperator::CreateOr(NotX, NotY);
           return BinaryOperator::CreateAnd(NotX, NotY);
         }

test/Transforms/InstCombine/not2.ll

+; RUN: opt < %s -instcombine -S | FileCheck %s
+; CHECK-NOT: xor
+
+define void @test1(i32 %A, i32 %B, i32 %C) {
+entry:
+  %cmp = icmp sgt i32 %A, 0
+  %cmp1 = icmp sgt i32 %B, 0
+  %0 = and i1 %cmp, %cmp1
+  %lnot = xor i1 %0, true
+  %conv = zext i1 %lnot to i32
+  %cmp2 = icmp sgt i32 %C, 0
+  %1 = and i1 %cmp2, %cmp1
+  %lnot6 = xor i1 %1, true
+  %conv7 = zext i1 %lnot6 to i32
+  call void @foo(i32 %conv, i32 %conv7)
+  ret void
+}
+
+define void @test2(i32 %A, i32 %B, i32 %C) {
+entry:
+  %cmp = icmp sgt i32 %A, 0
+  %cmp1 = icmp sgt i32 %B, 0
+  %0 = and i1 %cmp, %cmp1
+  %lnot = xor i1 %0, true
+  %conv = zext i1 %lnot to i32
+  %cmp4 = icmp sgt i32 %C, 0
+  %1 = and i1 %cmp, %cmp4
+  %lnot6 = xor i1 %1, true
+  %conv7 = zext i1 %lnot6 to i32
+  call void @foo(i32 %conv, i32 %conv7)
+  ret void
+}
+
+define void @test3(i32 %A, i32 %B, i32 %C) {
+entry:
+  %cmp = icmp sgt i32 %A, 0
+  %cmp1 = icmp sgt i32 %B, 0
+  %0 = and i1 %cmp, %cmp1
+  %lnot = xor i1 %0, true
+  %conv = zext i1 %lnot to i32
+  %cmp4 = icmp sgt i32 %C, 0
+  %1 = and i1 %cmp, %cmp4
+  %lnot6 = xor i1 %1, true
+  %conv7 = zext i1 %lnot6 to i32
+  %2 = and i1 %cmp1, %cmp4
+  %lnot12 = xor i1 %2, true
+  %conv13 = zext i1 %lnot12 to i32
+  call void @bar(i32 %conv, i32 %conv7, i32 %conv13)
+  ret void
+}
+
+define void @test4(i32 %A, i32 %B, i32 %C) {
+entry:
+  %cmp = icmp sgt i32 %A, 0
+  %cmp1 = icmp sgt i32 %B, 0
+  %0 = and i1 %cmp, %cmp1
+  %lnot = xor i1 %0, true
+  %conv = zext i1 %lnot to i32
+  %cmp4 = icmp sgt i32 %C, 0
+  %1 = and i1 %cmp, %cmp4
+  %lnot6 = xor i1 %1, true
+  %conv7 = zext i1 %lnot6 to i32
+  %2 = and i1 %cmp1, %cmp4
+  %conv12 = zext i1 %2 to i32
+  call void @bar(i32 %conv, i32 %conv7, i32 %conv12)
+  ret void
+}
+
+define void @test5(i32 %A, i32 %B, i32 %C) {
+entry:
+  %cmp = icmp sgt i32 %A, 0
+  %cmp1 = icmp sgt i32 %B, 0
+  %0 = and i1 %cmp, %cmp1
+  %lnot = xor i1 %0, true
+  %conv = zext i1 %lnot to i32
+  %cmp4 = icmp sgt i32 %C, 0
+  %1 = and i1 %cmp, %cmp4
+  %lnot6 = xor i1 %1, true
+  %conv7 = zext i1 %lnot6 to i32
+  %cmp8 = icmp slt i32 %B, 1
+  %cmp10 = icmp slt i32 %C, 1
+  %2 = and i1 %cmp8, %cmp10
+  %conv12 = zext i1 %2 to i32
+  call void @bar(i32 %conv, i32 %conv7, i32 %conv12)
+  ret void
+}
+
+define void @test6(i32 %A, i32 %B, i32 %C, i32 %D) {
+entry:
+  %cmp = icmp sgt i32 %A, 0
+  %cmp1 = icmp sgt i32 %B, 0
+  %0 = and i1 %cmp, %cmp1
+  %lnot = xor i1 %0, true
+  %conv = zext i1 %lnot to i32
+  %cmp4 = icmp sgt i32 %C, 0
+  %1 = and i1 %cmp, %cmp4
+  %lnot6 = xor i1 %1, true
+  %conv7 = zext i1 %lnot6 to i32
+  %cmp10 = icmp sgt i32 %D, 0
+  %2 = and i1 %cmp, %cmp10
+  %conv12 = zext i1 %2 to i32
+  %3 = and i1 %cmp1, %cmp4
+  %lnot17 = xor i1 %3, true
+  %conv18 = zext i1 %lnot17 to i32
+  call void @baz(i32 %conv, i32 %conv7, i32 %conv12, i32 %conv18)
+  ret void
+}
+
+declare void @foo(i32, i32)
+declare void @bar(i32, i32, i32)
+declare void @baz(i32, i32, i32, i32)