[InstCombine] change bitwise logic type to eliminate bitcasts

[spatel]

Summary

In PR27925:
https://llvm.org/bugs/show_bug.cgi?id=27925

...we proposed adding this fold to eliminate a bitcast. In D20774, there was some concern about changing the type of a bitwise op as well as creating bitcasts that might not be free for a target. However, if we're strictly eliminating an instruction (by limiting this to one-use ops), then we should be able to do this in InstCombine.

I purposely chose vector+scalar types in a couple of the tests to show the possibility of changing the logic op from a scalar to vector or vice-versa. But again, I think we're safe because we can assume that the source and destination types are DataLayout-legal because InstCombine shouldn't be creating strange types. Ie, I would typically only expect this pattern to emerge for vector-vector bitcasts like in the PR27925 test.

[spatel]

Note - the re-motivation to look at this pattern came up because there's a similar problem in the "ideal" example in PR6137:
https://llvm.org/bugs/show_bug.cgi?id=6137#c6

[efriedma]

I'm a little skeptical this is a good idea in all cases... it would be terrible to transform a vector xor into an i128 xor (and therefore force the operation into integer registers) just because SROA happened to produce an i128, or some calling convention has weird requirements. The transform looks good for your testcase in PR27925 in particular because "xor <2 x i64>" and "xor <4 x i32>" lower to the same instruction on x86.

lib/Transforms/InstCombine/InstCombineCasts.cpp

1796 ↗

(On Diff #77892)

Don't you need some sort of check that DestTy is an integer type?

[spatel]

In D26641#602029, @efriedma wrote:

I'm a little skeptical this is a good idea in all cases... it would be terrible to transform a vector xor into an i128 xor (and therefore force the operation into integer registers) just because SROA happened to produce an i128, or some calling convention has weird requirements. The transform looks good for your testcase in PR27925 in particular because "xor <2 x i64>" and "xor <4 x i32>" lower to the same instruction on x86.

I see 3 possible ways to solve/work-around this:

1. Don't do this transform in InstCombine (but then we're missing a potential canonicalization).
2. Limit this to vector-vector transforms in InstCombine (but then we're still missing a potential canonicalization for some types).
3. Fix it up in DAGCombine by using TLI to transform away from illegal operations.

I think #3 is the answer, but please let me know if I've missed any possibilities.

lib/Transforms/InstCombine/InstCombineCasts.cpp

1796 ↗

(On Diff #77892)

Oops - yes, that was an oversight.

[efriedma]

3 would be nice... but I'm not sure you can actually implement it properly without global isel because the operands/users could be defined in different blocks.

[spatel]

In D26641#602101, @efriedma wrote:

3 would be nice... but I'm not sure you can actually implement it properly without global isel because the operands/users could be defined in different blocks.

Hmm..good point. Could add to the CGP pile instead? But I'll propose that we use #2 with a FIXME comment for this patch, so we can make partial progress (I've only seen vector code with this problem so far).

[efriedma]

Not particularly excited about 2, but I don't see a better solution.

[spatel]

Patch updated:

1. Added a check on the destination type to be an integer element type (can't do a bitwise op otherwise).
2. Added a test for that case.
3. Restricted the transform to vector types (FIXME comment in the code) pending a backend fix-up to make sure we're not creating a mess with an illegal logic op for the destination type.

[efriedma]

LGTM.

llvm/trunk/lib/Transforms/InstCombine/InstCombineCasts.cpp

static Instruction *canonicalizeBitCastExtElt(BitCastInst &BitCast,
 
   unsigned NumElts = ExtElt->getVectorOperandType()->getNumElements();
   auto *NewVecType = VectorType::get(DestType, NumElts);
   auto *NewBC = IC.Builder->CreateBitCast(ExtElt->getVectorOperand(),
                                           NewVecType, "bc");
   return ExtractElementInst::Create(NewBC, ExtElt->getIndexOperand());
 }
 
+/// Change the type of a bitwise logic operation if we can eliminate a bitcast.
+static Instruction *foldBitCastBitwiseLogic(BitCastInst &BitCast,
+                                            InstCombiner::BuilderTy &Builder) {
+  BinaryOperator *BO;
+  if (!match(BitCast.getOperand(0), m_OneUse(m_BinOp(BO))))
+    return nullptr;
+
+  auto Opcode = BO->getOpcode();
+  if (Opcode != Instruction::And && Opcode != Instruction::Or &&
+      Opcode != Instruction::Xor)
+    return nullptr;
+
+  Type *DestTy = BitCast.getType();
+  if (!DestTy->getScalarType()->isIntegerTy())
+    return nullptr;
+  
+  // FIXME: This transform is restricted to vector types to avoid backend
+  // problems caused by creating potentially illegal operations. If a fix-up is
+  // added to handle that situation, we can remove this check.
+  if (!DestTy->isVectorTy() || !BO->getType()->isVectorTy())
+    return nullptr;
+  
+  Value *X;
+  if (match(BO->getOperand(0), m_OneUse(m_BitCast(m_Value(X)))) &&
+      X->getType() == DestTy && !isa<Constant>(X)) {
+    // bitcast(logic(bitcast(X), Y)) --> logic'(X, bitcast(Y))
+    Value *CastedOp1 = Builder.CreateBitCast(BO->getOperand(1), DestTy);
+    return BinaryOperator::Create(Opcode, X, CastedOp1);
+  }
+
+  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(Opcode, CastedOp0, X);
+  }
+
+  return nullptr;
+}
+
 /// Check if all users of CI are StoreInsts.
 static bool hasStoreUsersOnly(CastInst &CI) {
   for (User *U : CI.users()) {
     if (!isa<StoreInst>(U))
       return false;
   }
   return true;
 }
Instruction *InstCombiner::visitBitCast(BitCastInst &CI) {
   // Handle the A->B->A cast, and there is an intervening PHI node.
   if (PHINode *PN = dyn_cast<PHINode>(Src))
     if (Instruction *I = optimizeBitCastFromPhi(CI, PN))
       return I;
 
   if (Instruction *I = canonicalizeBitCastExtElt(CI, *this, DL))
     return I;
 
+  if (Instruction *I = foldBitCastBitwiseLogic(CI, *Builder))
+    return I;
+
   if (SrcTy->isPointerTy())
     return commonPointerCastTransforms(CI);
   return commonCastTransforms(CI);
 }
 
 Instruction *InstCombiner::visitAddrSpaceCast(AddrSpaceCastInst &CI) {
   // If the destination pointer element type is not the same as the source's
   // first do a bitcast to the destination type, and then the addrspacecast.

llvm/trunk/test/Transforms/InstCombine/bitcast.ll

;
   %t2 = or <2 x i32> %t1, <i32 1, i32 2>
   ret <2 x i32> %t2
 }
 
 ; PR27925 - https://llvm.org/bugs/show_bug.cgi?id=27925
 
 define <4 x i32> @bitcasts_and_bitcast(<4 x i32> %a, <8 x i16> %b) {
 ; CHECK-LABEL: @bitcasts_and_bitcast(
-; CHECK-NEXT:    [[BC1:%.*]] = bitcast <4 x i32> %a to <2 x i64>
-; CHECK-NEXT:    [[BC2:%.*]] = bitcast <8 x i16> %b to <2 x i64>
-; CHECK-NEXT:    [[AND:%.*]] = and <2 x i64> [[BC2]], [[BC1]]
-; CHECK-NEXT:    [[BC3:%.*]] = bitcast <2 x i64> [[AND]] to <4 x i32>
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast <8 x i16> %b to <4 x i32>
+; CHECK-NEXT:    [[BC3:%.*]] = and <4 x i32> [[TMP1]], %a
 ; CHECK-NEXT:    ret <4 x i32> [[BC3]]
 ;
   %bc1 = bitcast <4 x i32> %a to <2 x i64>
   %bc2 = bitcast <8 x i16> %b to <2 x i64>
   %and = and <2 x i64> %bc2, %bc1
   %bc3 = bitcast <2 x i64> %and to <4 x i32>
   ret <4 x i32> %bc3
 }
 
+; The destination must have an integer element type.
+; FIXME: We can still eliminate one bitcast in this test by doing the logic op
+; in the type of the input that has an integer element type.
+
+define <4 x float> @bitcasts_and_bitcast_to_fp(<4 x float> %a, <8 x i16> %b) {
+; CHECK-LABEL: @bitcasts_and_bitcast_to_fp(
+; CHECK-NEXT:    [[BC1:%.*]] = bitcast <4 x float> %a to <2 x i64>
+; CHECK-NEXT:    [[BC2:%.*]] = bitcast <8 x i16> %b to <2 x i64>
+; CHECK-NEXT:    [[AND:%.*]] = and <2 x i64> [[BC2]], [[BC1]]
+; CHECK-NEXT:    [[BC3:%.*]] = bitcast <2 x i64> [[AND]] to <4 x float>
+; CHECK-NEXT:    ret <4 x float> [[BC3]]
+;
+  %bc1 = bitcast <4 x float> %a to <2 x i64>
+  %bc2 = bitcast <8 x i16> %b to <2 x i64>
+  %and = and <2 x i64> %bc2, %bc1
+  %bc3 = bitcast <2 x i64> %and to <4 x float>
+  ret <4 x float> %bc3
+}
+
+; FIXME: Transform limited from changing vector op to integer op to avoid codegen problems.
+
 define i128 @bitcast_or_bitcast(i128 %a, <2 x i64> %b) {
 ; CHECK-LABEL: @bitcast_or_bitcast(
 ; CHECK-NEXT:    [[BC1:%.*]] = bitcast i128 %a to <2 x i64>
 ; CHECK-NEXT:    [[OR:%.*]] = or <2 x i64> [[BC1]], %b
 ; CHECK-NEXT:    [[BC2:%.*]] = bitcast <2 x i64> [[OR]] to i128
 ; CHECK-NEXT:    ret i128 [[BC2]]
 ;
   %bc1 = bitcast i128 %a to <2 x i64>
   %or = or <2 x i64> %b, %bc1
   %bc2 = bitcast <2 x i64> %or to i128
   ret i128 %bc2
 }
 
+; FIXME: Transform limited from changing integer op to vector op to avoid codegen problems.
+
 define <4 x i32> @bitcast_xor_bitcast(<4 x i32> %a, i128 %b) {
 ; CHECK-LABEL: @bitcast_xor_bitcast(
 ; CHECK-NEXT:    [[BC1:%.*]] = bitcast <4 x i32> %a to i128
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i128 [[BC1]], %b
 ; CHECK-NEXT:    [[BC2:%.*]] = bitcast i128 [[XOR]] to <4 x i32>
 ; CHECK-NEXT:    ret <4 x i32> [[BC2]]
 ;
   %bc1 = bitcast <4 x i32> %a to i128