[InstCombine] reverse bitcast + bitwise-logic canonicalization (PR33138)

[spatel]

Summary

There are 2 parts to this patch, but I think they need to be simultaneous to avoid a regression.

1. I'm proposing to reverse the canonicalization that moves bitwise vector ops before bitcasts. I want to move bitwise vector ops *after* bitcasts instead. That's the 1st and 3rd hunks of the patch. The motivation is that I only know of one fold that currently depends on the existing canonicalization (see next), but there are many folds that would automatically benefit from the new canonicalization. PR33138 ( https://bugs.llvm.org/show_bug.cgi?id=33138 ) shows why/how we have these patterns in IR.

2. There's an or(and,andn) pattern that requires an adjustment in order to continue matching to 'select' because the bitcast changes position. This match is unfortunately complicated because it requires 4 logic ops with optional bitcast and sext ops. As part of making that part less ugly, I'd like to add a 'peekThroughBitcasts()' helper based on similar functions that we use in the DAG. (I can add that in a separate NFC commit if preferred.)

Test diffs:

1. The bitcast.ll and bitcast-bigendian.ll changes show the most basic difference - bitcast comes before logic.
2. There are also tests with no diffs in bitcast.ll that verify that we're still doing folds that were enabled by the previous canonicalization.
3. icmp-xor-signbit.ll shows the payoff. We don't need to adjust existing icmp patterns to look through bitcasts.
4. logical-select.ll contains several tests for the or(and,andn) --> select fold to verify that we are still handling those cases. The lone diff shows the movement of the bitcast from the new canonicalization rule.

[spatel]

Ping.

[spatel]

Ping * 2.

[spatel]

Ping * 3.

[RKSimon]

LGTM. Please do the peekThroughBitcast helper as a NFC pre-commit.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

static Instruction *foldLogicCastConstant(BinaryOperator &Logic, CastInst *Cast,
   Constant *C;
   if (!match(Logic.getOperand(1), m_Constant(C)))
     return nullptr;
 
   auto LogicOpc = Logic.getOpcode();
   Type *DestTy = Logic.getType();
   Type *SrcTy = Cast->getSrcTy();
 
-  // If the first operand is bitcast, move the logic operation ahead of the
-  // bitcast (do the logic operation in the original type). This can eliminate
-  // bitcasts and allow combines that would otherwise be impeded by the bitcast.
+  // Move the logic operation ahead of a zext if the constant is unchanged in
+  // the smaller source type. Performing the logic in a smaller type may provide
+  // more information to later folds, and the smaller logic instruction may be
+  // cheaper (particularly in the case of vectors).
   Value *X;
-  if (match(Cast, m_BitCast(m_Value(X)))) {
-    Value *NewConstant = ConstantExpr::getBitCast(C, SrcTy);
-    Value *NewOp = Builder->CreateBinOp(LogicOpc, X, NewConstant);
-    return CastInst::CreateBitOrPointerCast(NewOp, DestTy);
-  }
-
-  // Similarly, move the logic operation ahead of a zext if the constant is
-  // unchanged in the smaller source type. Performing the logic in a smaller
-  // type may provide more information to later folds, and the smaller logic
-  // instruction may be cheaper (particularly in the case of vectors).
   if (match(Cast, m_OneUse(m_ZExt(m_Value(X))))) {
     Constant *TruncC = ConstantExpr::getTrunc(C, SrcTy);
     Constant *ZextTruncC = ConstantExpr::getZExt(TruncC, DestTy);
     if (ZextTruncC == C) {
       // LogicOpc (zext X), C --> zext (LogicOpc X, C)
       Value *NewOp = Builder->CreateBinOp(LogicOpc, X, TruncC);
       return new ZExtInst(NewOp, DestTy);
     }
static Value *getSelectCondition(Value *A, Value *B,
                                  InstCombiner::BuilderTy &Builder) {
   // If these are scalars or vectors of i1, A can be used directly.
   Type *Ty = A->getType();
   if (match(A, m_Not(m_Specific(B))) && Ty->getScalarType()->isIntegerTy(1))
     return A;
 
   // If A and B are sign-extended, look through the sexts to find the booleans.
   Value *Cond;
+  Value *NotB;
   if (match(A, m_SExt(m_Value(Cond))) &&
       Cond->getType()->getScalarType()->isIntegerTy(1) &&
-      match(B, m_CombineOr(m_Not(m_SExt(m_Specific(Cond))),
-                           m_SExt(m_Not(m_Specific(Cond))))))
+      match(B, m_OneUse(m_Not(m_Value(NotB))))) {
+    NotB = peekThroughBitcast(NotB, true);
+    if (match(NotB, m_SExt(m_Specific(Cond))))
       return Cond;
+  }
 
   // All scalar (and most vector) possibilities should be handled now.
   // Try more matches that only apply to non-splat constant vectors.
   if (!Ty->isVectorTy())
     return nullptr;
 
   // If both operands are constants, see if the constants are inverse bitmasks.
   Constant *AC, *BC;

 
 /// We have an expression of the form (A & C) | (B & D). Try to simplify this
 /// to "A' ? C : D", where A' is a boolean or vector of booleans.
 static Value *matchSelectFromAndOr(Value *A, Value *C, Value *B, Value *D,
                                    InstCombiner::BuilderTy &Builder) {
   // The potential condition of the select may be bitcasted. In that case, look
   // through its bitcast and the corresponding bitcast of the 'not' condition.
   Type *OrigType = A->getType();
-  Value *SrcA, *SrcB;
-  if (match(A, m_OneUse(m_BitCast(m_Value(SrcA)))) &&
-      match(B, m_OneUse(m_BitCast(m_Value(SrcB))))) {
-    A = SrcA;
-    B = SrcB;
-  }
+  A = peekThroughBitcast(A, true);
+  B = peekThroughBitcast(B, true);
 
   if (Value *Cond = getSelectCondition(A, B, Builder)) {
     // ((bc Cond) & C) | ((bc ~Cond) & D) --> bc (select Cond, (bc C), (bc D))
     // The bitcasts will either all exist or all not exist. The builder will
     // not create unnecessary casts if the types already match.
     Value *BitcastC = Builder.CreateBitCast(C, A->getType());
     Value *BitcastD = Builder.CreateBitCast(D, A->getType());
     Value *Select = Builder.CreateSelect(Cond, BitcastC, BitcastD);

lib/Transforms/InstCombine/InstCombineCasts.cpp

static Instruction *foldBitCastBitwiseLogic(BitCastInst &BitCast,
 
   if (match(BO->getOperand(1), m_OneUse(m_BitCast(m_Value(X)))) &&
       X->getType() == DestTy && !isa<Constant>(X)) {
     // bitcast(logic(Y, bitcast(X))) --> logic'(bitcast(Y), X)
     Value *CastedOp0 = Builder.CreateBitCast(BO->getOperand(0), DestTy);
     return BinaryOperator::Create(BO->getOpcode(), CastedOp0, X);
   }
 
+  // Canonicalize vector bitcasts to come before vector bitwise logic with a
+  // constant. This eases recognition of special constants for later ops.
+  // Example:
+  // icmp u/s (a ^ signmask), (b ^ signmask) --> icmp s/u a, b
+  Constant *C;
+  if (match(BO->getOperand(1), m_Constant(C))) {
+    // bitcast (logic X, C) --> logic (bitcast X, C')
+    Value *CastedOp0 = Builder.CreateBitCast(BO->getOperand(0), DestTy);
+    Value *CastedC = ConstantExpr::getBitCast(C, DestTy);
+    return BinaryOperator::Create(BO->getOpcode(), CastedOp0, CastedC);
+  }
+
   return nullptr;
 }
 
 /// Change the type of a select if we can eliminate a bitcast.
 static Instruction *foldBitCastSelect(BitCastInst &BitCast,
                                       InstCombiner::BuilderTy &Builder) {
   Value *Cond, *TVal, *FVal;
   if (!match(BitCast.getOperand(0),

lib/Transforms/InstCombine/InstCombineInternal.h

static inline bool isCanonicalPredicate(CmpInst::Predicate Pred) {
   case CmpInst::FCMP_OLE:
   case CmpInst::FCMP_OGE:
     return false;
   default:
     return true;
   }
 }
 
+/// Return the source operand of a potentially bitcasted value while optionally
+/// checking if it has one use. If there is no bitcast or the one use check is
+/// not met, just return the input value itself.
+static inline Value *peekThroughBitcast(Value *V, bool OneUseOnly = false) {
+  if (auto *BitCast = dyn_cast<BitCastInst>(V))
+    if (!OneUseOnly || BitCast->hasOneUse())
+      return BitCast->getOperand(0);
+
+  // V is not a bitcast, or V has more than one use and OneUseOnly is true.
+  return V;
+}
+
 /// \brief Add one to a Constant
 static inline Constant *AddOne(Constant *C) {
   return ConstantExpr::getAdd(C, ConstantInt::get(C->getType(), 1));
 }
 /// \brief Subtract one from a Constant
 static inline Constant *SubOne(Constant *C) {
   return ConstantExpr::getSub(C, ConstantInt::get(C->getType(), 1));
 }

test/Transforms/InstCombine/bitcast-bigendian.ll

;
   %tmp23 = bitcast float %A to i32
   %tmp24 = zext i32 %tmp23 to i64
   %tmp25 = shl i64 %tmp24, 32
   %mask20 = or i64 %tmp25, 1109917696
   %tmp35 = bitcast i64 %mask20 to <2 x float>
   ret <2 x float> %tmp35
 }
 
-; Verify that 'xor' of vector and constant is done as a vector bitwise op before the bitcast.
+; No change. Bitcasts are canonicalized above bitwise logic.
 
 define <2 x i32> @xor_bitcast_vec_to_vec(<1 x i64> %a) {
 ; CHECK-LABEL: @xor_bitcast_vec_to_vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor <1 x i64> [[A:%.*]], <i64 4294967298>
-; CHECK-NEXT:    [[T2:%.*]] = bitcast <1 x i64> [[TMP1]] to <2 x i32>
+; CHECK-NEXT:    [[T1:%.*]] = bitcast <1 x i64> [[A:%.*]] to <2 x i32>
+; CHECK-NEXT:    [[T2:%.*]] = xor <2 x i32> [[T1]], <i32 1, i32 2>
 ; CHECK-NEXT:    ret <2 x i32> [[T2]]
 ;
   %t1 = bitcast <1 x i64> %a to <2 x i32>
   %t2 = xor <2 x i32> <i32 1, i32 2>, %t1
   ret <2 x i32> %t2
 }
 
-; Verify that 'and' of integer and constant is done as a vector bitwise op before the bitcast.
+; No change. Bitcasts are canonicalized above bitwise logic.
 
 define i64 @and_bitcast_vec_to_int(<2 x i32> %a) {
 ; CHECK-LABEL: @and_bitcast_vec_to_int(
-; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i32> [[A:%.*]], <i32 0, i32 3>
-; CHECK-NEXT:    [[T2:%.*]] = bitcast <2 x i32> [[TMP1]] to i64
+; CHECK-NEXT:    [[T1:%.*]] = bitcast <2 x i32> [[A:%.*]] to i64
+; CHECK-NEXT:    [[T2:%.*]] = and i64 [[T1]], 3
 ; CHECK-NEXT:    ret i64 [[T2]]
 ;
   %t1 = bitcast <2 x i32> %a to i64
   %t2 = and i64 %t1, 3
   ret i64 %t2
 }
 
-; Verify that 'or' of vector and constant is done as an integer bitwise op before the bitcast.
+; No change. Bitcasts are canonicalized above bitwise logic.
 
 define <2 x i32> @or_bitcast_int_to_vec(i64 %a) {
 ; CHECK-LABEL: @or_bitcast_int_to_vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[A:%.*]], 4294967298
-; CHECK-NEXT:    [[T2:%.*]] = bitcast i64 [[TMP1]] to <2 x i32>
+; CHECK-NEXT:    [[T1:%.*]] = bitcast i64 [[A:%.*]] to <2 x i32>
+; CHECK-NEXT:    [[T2:%.*]] = or <2 x i32> [[T1]], <i32 1, i32 2>
 ; CHECK-NEXT:    ret <2 x i32> [[T2]]
 ;
   %t1 = bitcast i64 %a to <2 x i32>
   %t2 = or <2 x i32> %t1, <i32 1, i32 2>
   ret <2 x i32> %t2
 }
 

test/Transforms/InstCombine/bitcast.ll

 ; CHECK-NEXT:    ret <2 x i32> [[T3]]
 ;
   %t1 = bitcast <1 x i64> %a to <2 x i32>
   %t2 = bitcast <1 x i64> %b to <2 x i32>
   %t3 = xor <2 x i32> %t1, %t2
   ret <2 x i32> %t3
 }
 
-; Verify that 'xor' of vector and constant is done as a vector bitwise op before the bitcast.
+; No change. Bitcasts are canonicalized above bitwise logic.
 
 define <2 x i32> @xor_bitcast_vec_to_vec(<1 x i64> %a) {
 ; CHECK-LABEL: @xor_bitcast_vec_to_vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = xor <1 x i64> [[A:%.*]], <i64 8589934593>
-; CHECK-NEXT:    [[T2:%.*]] = bitcast <1 x i64> [[TMP1]] to <2 x i32>
+; CHECK-NEXT:    [[T1:%.*]] = bitcast <1 x i64> [[A:%.*]] to <2 x i32>
+; CHECK-NEXT:    [[T2:%.*]] = xor <2 x i32> [[T1]], <i32 1, i32 2>
 ; CHECK-NEXT:    ret <2 x i32> [[T2]]
 ;
   %t1 = bitcast <1 x i64> %a to <2 x i32>
   %t2 = xor <2 x i32> <i32 1, i32 2>, %t1
   ret <2 x i32> %t2
 }
 
-; Verify that 'and' of integer and constant is done as a vector bitwise op before the bitcast.
+; No change. Bitcasts are canonicalized above bitwise logic.
 
 define i64 @and_bitcast_vec_to_int(<2 x i32> %a) {
 ; CHECK-LABEL: @and_bitcast_vec_to_int(
-; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i32> [[A:%.*]], <i32 3, i32 0>
-; CHECK-NEXT:    [[T2:%.*]] = bitcast <2 x i32> [[TMP1]] to i64
+; CHECK-NEXT:    [[T1:%.*]] = bitcast <2 x i32> [[A:%.*]] to i64
+; CHECK-NEXT:    [[T2:%.*]] = and i64 [[T1]], 3
 ; CHECK-NEXT:    ret i64 [[T2]]
 ;
   %t1 = bitcast <2 x i32> %a to i64
   %t2 = and i64 %t1, 3
   ret i64 %t2
 }
 
-; Verify that 'or' of vector and constant is done as an integer bitwise op before the bitcast.
+; No change. Bitcasts are canonicalized above bitwise logic.
 
 define <2 x i32> @or_bitcast_int_to_vec(i64 %a) {
 ; CHECK-LABEL: @or_bitcast_int_to_vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = or i64 [[A:%.*]], 8589934593
-; CHECK-NEXT:    [[T2:%.*]] = bitcast i64 [[TMP1]] to <2 x i32>
+; CHECK-NEXT:    [[T1:%.*]] = bitcast i64 [[A:%.*]] to <2 x i32>
+; CHECK-NEXT:    [[T2:%.*]] = or <2 x i32> [[T1]], <i32 1, i32 2>
 ; CHECK-NEXT:    ret <2 x i32> [[T2]]
 ;
   %t1 = bitcast i64 %a to <2 x i32>
   %t2 = or <2 x i32> %t1, <i32 1, i32 2>
   ret <2 x i32> %t2
 }
 
 ; PR26702 - https://bugs.llvm.org//show_bug.cgi?id=26702
-; Bitcast is canonicalized below logic, so we can see the not-not pattern.
+; Bitcast is canonicalized above logic, so we can see the not-not pattern.
 
 define <2 x i64> @is_negative(<4 x i32> %x) {
 ; CHECK-LABEL: @is_negative(
 ; CHECK-NEXT:    [[LOBIT:%.*]] = ashr <4 x i32> %x, <i32 31, i32 31, i32 31, i32 31>
 ; CHECK-NEXT:    [[NOTNOT:%.*]] = bitcast <4 x i32> [[LOBIT]] to <2 x i64>
 ; CHECK-NEXT:    ret <2 x i64> [[NOTNOT]]
 ;
   %lobit = ashr <4 x i32> %x, <i32 31, i32 31, i32 31, i32 31>
;
   %lobit = ashr <4 x i32> %x, <i32 31, i32 31, i32 31, i32 31>
   %not = xor <4 x i32> %lobit, <i32 -1, i32 -1, i32 -1, i32 -1>
   %bc = bitcast <4 x i32> %not to <2 x i64>
   %notnot = xor <2 x i64> %bc, <i64 -1, i64 -1>
   %bc2 = bitcast <2 x i64> %notnot to <4 x i32>
   ret <4 x i32> %bc2
 }
 
-; Negative test: bitcasts are canonicalized below bitwise logic. No changes here.
+; Bitcasts are canonicalized above bitwise logic.
 
 define <2 x i8> @canonicalize_bitcast_logic_with_constant(<4 x i4> %x) {
 ; CHECK-LABEL: @canonicalize_bitcast_logic_with_constant(
-; CHECK-NEXT:    [[A:%.*]] = and <4 x i4> %x, <i4 0, i4 -8, i4 0, i4 -8>
-; CHECK-NEXT:    [[B:%.*]] = bitcast <4 x i4> [[A]] to <2 x i8>
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast <4 x i4> [[X:%.*]] to <2 x i8>
+; CHECK-NEXT:    [[B:%.*]] = and <2 x i8> [[TMP1]], <i8 -128, i8 -128>
 ; CHECK-NEXT:    ret <2 x i8> [[B]]
 ;
   %a = and <4 x i4> %x, <i4 0, i4 8, i4 0, i4 8>
   %b = bitcast <4 x i4> %a to <2 x i8>
   ret <2 x i8> %b
 }
 
 ; PR27925 - https://llvm.org/bugs/show_bug.cgi?id=27925

test/Transforms/InstCombine/icmp-xor-signbit.ll

 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %a = xor <2 x i8> %x, <i8 127, i8 127>
   %cmp = icmp uge <2 x i8> %a, <i8 15, i8 15>
   ret <2 x i1> %cmp
 }
 
 ; PR33138, part 2: https://bugs.llvm.org/show_bug.cgi?id=33138
-; TODO: We could look through vector bitcasts for icmp folds,
-; or we could canonicalize bitcast ahead of logic ops with constants.
+; Bitcast canonicalization ensures that we recognize the signbit constant.
 
 define <8 x i1> @sgt_to_ugt_bitcasted_splat(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @sgt_to_ugt_bitcasted_splat(
-; CHECK-NEXT:    [[A:%.*]] = xor <2 x i32> %x, <i32 -2139062144, i32 -2139062144>
-; CHECK-NEXT:    [[B:%.*]] = xor <2 x i32> %y, <i32 -2139062144, i32 -2139062144>
-; CHECK-NEXT:    [[C:%.*]] = bitcast <2 x i32> [[A]] to <8 x i8>
-; CHECK-NEXT:    [[D:%.*]] = bitcast <2 x i32> [[B]] to <8 x i8>
-; CHECK-NEXT:    [[E:%.*]] = icmp sgt <8 x i8> [[C]], [[D]]
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast <2 x i32> %x to <8 x i8>
+; CHECK-NEXT:    [[TMP2:%.*]] = bitcast <2 x i32> %y to <8 x i8>
+; CHECK-NEXT:    [[E:%.*]] = icmp ugt <8 x i8> [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    ret <8 x i1> [[E]]
 ;
   %a = xor <2 x i32> %x, <i32 2155905152, i32 2155905152> ; 0x80808080
   %b = xor <2 x i32> %y, <i32 2155905152, i32 2155905152>
   %c = bitcast <2 x i32> %a to <8 x i8>
   %d = bitcast <2 x i32> %b to <8 x i8>
   %e = icmp sgt <8 x i8> %c, %d
   ret <8 x i1> %e
 }
 
-; TODO: This is false (little-endian). How should that be recognized?
-; Ie, should InstSimplify know this directly, should InstCombine canonicalize
-; this so InstSimplify can know this, or is that not something that we want
-; either pass to recognize?
+; Bitcast canonicalization ensures that we recognize the signbit constant.
 
 define <2 x i1> @negative_simplify_splat(<4 x i8> %x) {
 ; CHECK-LABEL: @negative_simplify_splat(
-; CHECK-NEXT:    [[A:%.*]] = or <4 x i8> %x, <i8 0, i8 -128, i8 0, i8 -128>
-; CHECK-NEXT:    [[B:%.*]] = bitcast <4 x i8> [[A]] to <2 x i16>
-; CHECK-NEXT:    [[C:%.*]] = icmp sgt <2 x i16> [[B]], zeroinitializer
-; CHECK-NEXT:    ret <2 x i1> [[C]]
+; CHECK-NEXT:    ret <2 x i1> zeroinitializer
 ;
   %a = or <4 x i8> %x, <i8 0, i8 128, i8 0, i8 128>
   %b = bitcast <4 x i8> %a to <2 x i16>
   %c = icmp sgt <2 x i16> %b, zeroinitializer
   ret <2 x i1> %c
 }
 

test/Transforms/InstCombine/logical-select.ll

;
   ret <2 x i64> %or
 }
 
 define <2 x i64> @bitcast_select_multi_uses(<4 x i1> %cmp, <2 x i64> %a, <2 x i64> %b) {
 ; CHECK-LABEL: @bitcast_select_multi_uses(
 ; CHECK-NEXT:    [[SEXT:%.*]] = sext <4 x i1> %cmp to <4 x i32>
 ; CHECK-NEXT:    [[BC1:%.*]] = bitcast <4 x i32> [[SEXT]] to <2 x i64>
 ; CHECK-NEXT:    [[AND1:%.*]] = and <2 x i64> [[BC1]], %a
-; CHECK-NEXT:    [[NEG:%.*]] = xor <4 x i32> [[SEXT]], <i32 -1, i32 -1, i32 -1, i32 -1>
-; CHECK-NEXT:    [[BC2:%.*]] = bitcast <4 x i32> [[NEG]] to <2 x i64>
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast <4 x i32> [[SEXT]] to <2 x i64>
+; CHECK-NEXT:    [[BC2:%.*]] = xor <2 x i64> [[TMP1]], <i64 -1, i64 -1>
 ; CHECK-NEXT:    [[AND2:%.*]] = and <2 x i64> [[BC2]], %b
 ; CHECK-NEXT:    [[OR:%.*]] = or <2 x i64> [[AND2]], [[AND1]]
 ; CHECK-NEXT:    [[ADD:%.*]] = add <2 x i64> [[AND2]], [[BC2]]
 ; CHECK-NEXT:    [[SUB:%.*]] = sub <2 x i64> [[OR]], [[ADD]]
 ; CHECK-NEXT:    ret <2 x i64> [[SUB]]
 ;
   %sext = sext <4 x i1> %cmp to <4 x i32>
   %bc1 = bitcast <4 x i32> %sext to <2 x i64>