InstCombine: Turn icmp + sext into bitwise/integer ops when the input has only one...

int test1(unsigned x) { return (x&8) ? 0 : -1; }
int test3(unsigned x) { return (x&8) ? -1 : 0; }

before (x86_64):
_test1:
	andl	$8, %edi
	cmpl	$1, %edi
	sbbl	%eax, %eax
	ret
_test3:
	andl	$8, %edi
	cmpl	$1, %edi
	sbbl	%eax, %eax
	notl	%eax
	ret

after:
_test1:
	shrl	$3, %edi
	andl	$1, %edi
	leal	-1(%rdi), %eax
	ret
_test3:
	shll	$28, %edi
	movl	%edi, %eax
	sarl	$31, %eax
	ret

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@128732 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/Transforms/InstCombine/InstCombineCasts.cpp b/lib/Transforms/InstCombine/InstCombineCasts.cpp
index 0401fb2d69d7da1680457a003ef95a1a48265f4b..d2ab61845f2e9a197ea75ae9bf4c0bb39b8b8751 100644 (file)
--- a/lib/Transforms/InstCombine/InstCombineCasts.cpp
+++ b/lib/Transforms/InstCombine/InstCombineCasts.cpp
@@ -882,6 +882,10 @@ Instruction *InstCombiner::transformSExtICmp(ICmpInst *ICI, Instruction &CI) {
   Value *Op0 = ICI->getOperand(0), *Op1 = ICI->getOperand(1);
   ICmpInst::Predicate Pred = ICI->getPredicate();
 
+  // Transforming icmps with more than one use is not profitable.
+  if (!ICI->hasOneUse())
+    return 0;
+
   if (ConstantInt *Op1C = dyn_cast<ConstantInt>(Op1)) {
     // (x <s 0) ? -1 : 0 -> ashr x, 31   -> all ones if signed
     // (x >s -1) ? -1 : 0 -> ashr x, 31  -> all ones if not signed
@@ -898,6 +902,52 @@ Instruction *InstCombiner::transformSExtICmp(ICmpInst *ICI, Instruction &CI) {
         In = Builder->CreateNot(In, In->getName()+".not");
       return ReplaceInstUsesWith(CI, In);
     }
+
+    // If we know that only one bit of the LHS of the icmp can be set and we
+    // have an equality comparison with zero or a power of 2, we can transform
+    // the icmp and sext into bitwise/integer operations.
+    if (ICI->isEquality() && (Op1C->isZero() || Op1C->getValue().isPowerOf2())){
+      unsigned BitWidth = Op1C->getType()->getBitWidth();
+      APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
+      APInt TypeMask(APInt::getAllOnesValue(BitWidth));
+      ComputeMaskedBits(Op0, TypeMask, KnownZero, KnownOne);
+
+      if ((~KnownZero).isPowerOf2()) {
+        Value *In = ICI->getOperand(0);
+
+        if (!Op1C->isZero() == (Pred == ICmpInst::ICMP_NE)) {
+          // sext ((x & 2^n) == 0)   -> (x >> n) - 1
+          // sext ((x & 2^n) != 2^n) -> (x >> n) - 1
+          unsigned ShiftAmt = KnownZeroMask.countTrailingZeros();
+          // Perform a right shift to place the desired bit in the LSB.
+          if (ShiftAmt)
+            In = Builder->CreateLShr(In,
+                                     ConstantInt::get(In->getType(), ShiftAmt));
+
+          // At this point "In" is either 1 or 0. Subtract 1 to turn
+          // {1, 0} -> {0, -1}.
+          In = Builder->CreateAdd(In,
+                                  ConstantInt::getAllOnesValue(In->getType()),
+                                  "sext");
+        } else {
+          // sext ((x & 2^n) != 0)   -> (x << bitwidth-n) a>> bitwidth-1
+          // sext ((x & 2^n) != 2^n) -> (x << bitwidth-n) a>> bitwidth-1
+          unsigned ShiftAmt = KnownZeroMask.countLeadingZeros();
+          // Perform a left shift to place the desired bit in the MSB.
+          if (ShiftAmt)
+            In = Builder->CreateShl(In,
+                                    ConstantInt::get(In->getType(), ShiftAmt));
+
+          // Distribute the bit over the whole bit width.
+          In = Builder->CreateAShr(In, ConstantInt::get(In->getType(),
+                                                        BitWidth - 1), "sext");
+        }
+
+        if (CI.getType() == In->getType())
+          return ReplaceInstUsesWith(CI, In);
+        return CastInst::CreateIntegerCast(In, CI.getType(), true/*SExt*/);
+      }
+    }
   }
 
   // vector (x <s 0) ? -1 : 0 -> ashr x, 31   -> all ones if signed.

diff --git a/test/Transforms/InstCombine/sext.ll b/test/Transforms/InstCombine/sext.ll
index da52d92695275ef6d096b4b1f68277d06079f566..f49a2efb39d8fd1cf694a9be8f427cede795c145 100644 (file)
--- a/test/Transforms/InstCombine/sext.ll
+++ b/test/Transforms/InstCombine/sext.ll
@@ -136,3 +136,51 @@ define i64 @test12(i32 %x) nounwind {
 ; CHECK: sext
 ; CHECK: ret
 }
+
+define i32 @test13(i32 %x) nounwind {
+  %and = and i32 %x, 8
+  %cmp = icmp eq i32 %and, 0
+  %ext = sext i1 %cmp to i32
+  ret i32 %ext
+; CHECK: @test13
+; CHECK-NEXT: %and = lshr i32 %x, 3
+; CHECK-NEXT: %1 = and i32 %and, 1
+; CHECK-NEXT: %sext = add i32 %1, -1
+; CHECK-NEXT: ret i32 %sext
+}
+
+define i32 @test14(i16 %x) nounwind {
+  %and = and i16 %x, 16
+  %cmp = icmp ne i16 %and, 16
+  %ext = sext i1 %cmp to i32
+  ret i32 %ext
+; CHECK: @test14
+; CHECK-NEXT: %and = lshr i16 %x, 4
+; CHECK-NEXT: %1 = and i16 %and, 1
+; CHECK-NEXT: %sext = add i16 %1, -1
+; CHECK-NEXT: %ext = sext i16 %sext to i32
+; CHECK-NEXT: ret i32 %ext
+}
+
+define i32 @test15(i32 %x) nounwind {
+  %and = and i32 %x, 16
+  %cmp = icmp ne i32 %and, 0
+  %ext = sext i1 %cmp to i32
+  ret i32 %ext
+; CHECK: @test15
+; CHECK-NEXT: %1 = shl i32 %x, 27
+; CHECK-NEXT: %sext = ashr i32 %1, 31
+; CHECK-NEXT: ret i32 %sext
+}
+
+define i32 @test16(i16 %x) nounwind {
+  %and = and i16 %x, 8
+  %cmp = icmp eq i16 %and, 8
+  %ext = sext i1 %cmp to i32
+  ret i32 %ext
+; CHECK: @test16
+; CHECK-NEXT: %1 = shl i16 %x, 12
+; CHECK-NEXT: %sext = ashr i16 %1, 15
+; CHECK-NEXT: %ext = sext i16 %sext to i32
+; CHECK-NEXT: ret i32 %ext
+}