[InstCombine] Improve cost calculation in foldSelectICmpAndBinOp

[goldstein.w.n]

Summary

There is a case where we save an and instruction because the shift
is the entire bitwidth. So take that into account when accounting the
number of instruction with/without the transform.

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Rebase

[nikic]

Is this useful?

[goldstein.w.n]

In D148415#4484671, @nikic wrote:

Is this useful?

Its more precise at the very least. You think we are better of with the select in this case?
I'm fine dropping this if you think the even-fold isn't actually to our benefit.

[goldstein.w.n]

ping. @nikic you think I should just drop this?

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

static Value *foldSelectICmpAndBinOp(const ICmpInst *IC, Value *TrueVal,
   // Check that 0 on RHS is identity value for this binop.
   if (!ConstantExpr::getBinOpIdentity(BinOp->getOpcode(), BinOp->getType(),
                                       /*AllowRHSConstant*/ true)
            ->isNullValue())
     return nullptr;
 
   unsigned C2Log = C2->logBase2();
 
+  bool SavesAnd = false;
+  if (IC->isEquality() && V->hasOneUse()) {
+    // If we are shifting by bitwidth - 1, the `and` can be optimized out.
+    if (C2Log > C1Log) {
+      SavesAnd =
+          (C2Log - C1Log) == (Y->getType()->getScalarSizeInBits() - 1);
+    } else if (C1Log > C2Log) {
+      SavesAnd =
+          (C1Log - C2Log) == (Y->getType()->getScalarSizeInBits() - 1);
+    }
+  }
+
   bool NeedShift = C1Log != C2Log;
   bool NeedZExtTrunc = Y->getType()->getScalarSizeInBits() !=
                        V->getType()->getScalarSizeInBits();
 
   // Make sure we don't create more instructions than we save.
   if ((NeedShift + NeedXor + NeedZExtTrunc + NeedAnd) >
-      (IC->hasOneUse() + BinOp->hasOneUse()))
+      (IC->hasOneUse() + BinOp->hasOneUse() + SavesAnd))
     return nullptr;
 
   if (NeedAnd) {
     // Insert the AND instruction on the input to the truncate.
     APInt C1 = APInt::getOneBitSet(V->getType()->getScalarSizeInBits(), C1Log);
     V = Builder.CreateAnd(V, ConstantInt::get(V->getType(), C1));
   }
 

llvm/test/Transforms/InstCombine/select-with-bitwise-ops.ll

;
   call void @use(i8 %or)
   %cond = select i1 %b, i8 %and, i8 %or
   ret i8 %cond
 }
 
 ; Tests factoring in cost of saving the `and`
 define i64 @xor_i8_to_i64_shl_save_and_eq(i8 %x, i64 %y) {
 ; CHECK-LABEL: @xor_i8_to_i64_shl_save_and_eq(
-; CHECK-NEXT:    [[XX:%.*]] = and i8 [[X:%.*]], 1
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[XX]], 0
-; CHECK-NEXT:    [[Z:%.*]] = xor i64 [[Y:%.*]], -9223372036854775808
-; CHECK-NEXT:    [[R:%.*]] = select i1 [[CMP]], i64 [[Z]], i64 [[Y]]
+; CHECK-NEXT:    [[TMP1:%.*]] = zext i8 [[X:%.*]] to i64
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i64 [[TMP1]], -1
+; CHECK-NEXT:    [[TMP3:%.*]] = shl i64 [[TMP2]], 63
+; CHECK-NEXT:    [[R:%.*]] = xor i64 [[TMP3]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i64 [[R]]
 ;
   %xx = and i8 %x, 1
   %cmp = icmp eq i8 %xx, 0
   %z = xor i64 %y, -9223372036854775808
   %r = select i1 %cmp, i64 %z, i64 %y
   ret i64 %r
 }