From 0baa94a13bf24cf7d916b4c6c415fb84b464bfd3 Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Fri, 1 Apr 2011 20:09:10 +0000 Subject: [PATCH] InstCombine: Turn icmp + sext into bitwise/integer ops when the input has only one unknown bit. 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 --- .../InstCombine/InstCombineCasts.cpp | 50 +++++++++++++++++++ test/Transforms/InstCombine/sext.ll | 48 ++++++++++++++++++ 2 files changed, 98 insertions(+) diff --git a/lib/Transforms/InstCombine/InstCombineCasts.cpp b/lib/Transforms/InstCombine/InstCombineCasts.cpp index 0401fb2d69d..d2ab61845f2 100644 --- 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(Op1)) { // (x 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 ashr x, 31 -> all ones if signed. diff --git a/test/Transforms/InstCombine/sext.ll b/test/Transforms/InstCombine/sext.ll index da52d926952..f49a2efb39d 100644 --- 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 +} -- 2.34.1