[InstCombine] Fix known bits handling in SimplifyDemandedUseBits

[nikic]

Summary

Fixes a regression from D75801. SimplifyDemandedUseBits() is also supposed to compute the known bits (of the demanded subset) of the instruction. For unknown instructions it does so by directly calling computeKnownBits(). For known instructions it will compute known bits itself. However, for instructions where only some cases are handled directly (e.g. a constant shift amount) the known bits invocation for the unhandled case is sometimes missing. This patch adds the missing calls and thus removes the main discrepancy with ExpensiveCombines mode.

[nikic]

Some comments on the intrinsics code, as it did some weird things before...

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

719

Despite what the comment says, this was already computing known bits, because the "break" falls through to the call below.

752

While known bits were computed explicitly here, this break would still fall through to the known bits call below, and thus recompute the result from scratch.

781

This return nullptr skipped the bit of code for returning a constant integer below.

790

To avoid the three issues mentioned above, I'm now explicitly tracking whether known bits were computed or not for the call.

[spatel]

LGTM

lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp

if (match(I->getOperand(1), m_APInt(SA))) {
       if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1))
         return I;
       assert(!Known.hasConflict() && "Bits known to be one AND zero?");
       Known.Zero <<= ShiftAmt;
       Known.One  <<= ShiftAmt;
       // low bits known zero.
       if (ShiftAmt)
         Known.Zero.setLowBits(ShiftAmt);
+    } else {
+      computeKnownBits(I, Known, Depth, CxtI);
     }
     break;
   }
   case Instruction::LShr: {
     const APInt *SA;
     if (match(I->getOperand(1), m_APInt(SA))) {
       uint64_t ShiftAmt = SA->getLimitedValue(BitWidth-1);
 
       // Unsigned shift right.
       APInt DemandedMaskIn(DemandedMask.shl(ShiftAmt));
 
       // If the shift is exact, then it does demand the low bits (and knows that
       // they are zero).
       if (cast<LShrOperator>(I)->isExact())
         DemandedMaskIn.setLowBits(ShiftAmt);
 
       if (SimplifyDemandedBits(I, 0, DemandedMaskIn, Known, Depth + 1))
         return I;
       assert(!Known.hasConflict() && "Bits known to be one AND zero?");
       Known.Zero.lshrInPlace(ShiftAmt);
       Known.One.lshrInPlace(ShiftAmt);
       if (ShiftAmt)
         Known.Zero.setHighBits(ShiftAmt);  // high bits known zero.
+    } else {
+      computeKnownBits(I, Known, Depth, CxtI);
     }
     break;
   }
   case Instruction::AShr: {
     // If this is an arithmetic shift right and only the low-bit is set, we can
     // always convert this into a logical shr, even if the shift amount is
     // variable.  The low bit of the shift cannot be an input sign bit unless
     // the shift amount is >= the size of the datatype, which is undefined.
if (match(I->getOperand(1), m_APInt(SA))) {
           !DemandedMask.intersects(HighBits)) {
         BinaryOperator *LShr = BinaryOperator::CreateLShr(I->getOperand(0),
                                                           I->getOperand(1));
         LShr->setIsExact(cast<BinaryOperator>(I)->isExact());
         return InsertNewInstWith(LShr, *I);
       } else if (Known.One[BitWidth-ShiftAmt-1]) { // New bits are known one.
         Known.One |= HighBits;
       }
+    } else {
+      computeKnownBits(I, Known, Depth, CxtI);
     }
     break;
   }
   case Instruction::UDiv: {
     // UDiv doesn't demand low bits that are zero in the divisor.
     const APInt *SA;
     if (match(I->getOperand(1), m_APInt(SA))) {
       // If the shift is exact, then it does demand the low bits.
       if (cast<UDivOperator>(I)->isExact())
         break;
 
       // FIXME: Take the demanded mask of the result into account.
       unsigned RHSTrailingZeros = SA->countTrailingZeros();
       APInt DemandedMaskIn =
           APInt::getHighBitsSet(BitWidth, BitWidth - RHSTrailingZeros);
       if (SimplifyDemandedBits(I, 0, DemandedMaskIn, LHSKnown, Depth + 1))
         return I;
 
       // Propagate zero bits from the input.
       Known.Zero.setHighBits(std::min(
           BitWidth, LHSKnown.Zero.countLeadingOnes() + RHSTrailingZeros));
+    } else {
+      computeKnownBits(I, Known, Depth, CxtI);
     }
     break;
   }
   case Instruction::SRem:
     if (ConstantInt *Rem = dyn_cast<ConstantInt>(I->getOperand(1))) {
       // X % -1 demands all the bits because we don't want to introduce
       // INT_MIN % -1 (== undef) by accident.
       if (Rem->isMinusOne())
case Instruction::URem: {
     if (SimplifyDemandedBits(I, 0, AllOnes, Known2, Depth + 1) ||
         SimplifyDemandedBits(I, 1, AllOnes, Known2, Depth + 1))
       return I;
 
     unsigned Leaders = Known2.countMinLeadingZeros();
     Known.Zero = APInt::getHighBitsSet(BitWidth, Leaders) & DemandedMask;
     break;
   }
-  case Instruction::Call:
+  case Instruction::Call: {
+    bool KnownBitsComputed = false;
     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
       switch (II->getIntrinsicID()) {
       default: break;
       case Intrinsic::bswap: {
         // If the only bits demanded come from one byte of the bswap result,
         // just shift the input byte into position to eliminate the bswap.
         unsigned NLZ = DemandedMask.countLeadingZeros();
         unsigned NTZ = DemandedMask.countTrailingZeros();
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
             NewVal = BinaryOperator::CreateLShr(II->getArgOperand(0),
                     ConstantInt::get(I->getType(), InputBit-ResultBit));
           else
             NewVal = BinaryOperator::CreateShl(II->getArgOperand(0),
                     ConstantInt::get(I->getType(), ResultBit-InputBit));
           NewVal->takeName(I);
           return InsertNewInstWith(NewVal, *I);
         }
-
-        // TODO: Could compute known zero/one bits based on the input.
         break;
       }
       case Intrinsic::fshr:
       case Intrinsic::fshl: {
         const APInt *SA;
         if (!match(I->getOperand(2), m_APInt(SA)))
           break;
 
         // Normalize to funnel shift left. APInt shifts of BitWidth are well-
         // defined, so no need to special-case zero shifts here.
         uint64_t ShiftAmt = SA->urem(BitWidth);
         if (II->getIntrinsicID() == Intrinsic::fshr)
           ShiftAmt = BitWidth - ShiftAmt;
 
         APInt DemandedMaskLHS(DemandedMask.lshr(ShiftAmt));
         APInt DemandedMaskRHS(DemandedMask.shl(BitWidth - ShiftAmt));
         if (SimplifyDemandedBits(I, 0, DemandedMaskLHS, LHSKnown, Depth + 1) ||
             SimplifyDemandedBits(I, 1, DemandedMaskRHS, RHSKnown, Depth + 1))
           return I;
 
         Known.Zero = LHSKnown.Zero.shl(ShiftAmt) |
                      RHSKnown.Zero.lshr(BitWidth - ShiftAmt);
         Known.One = LHSKnown.One.shl(ShiftAmt) |
                     RHSKnown.One.lshr(BitWidth - ShiftAmt);
+        KnownBitsComputed = true;
         break;
       }
       case Intrinsic::x86_mmx_pmovmskb:
       case Intrinsic::x86_sse_movmsk_ps:
       case Intrinsic::x86_sse2_movmsk_pd:
       case Intrinsic::x86_sse2_pmovmskb_128:
       case Intrinsic::x86_avx_movmsk_ps_256:
       case Intrinsic::x86_avx_movmsk_pd_256:
       case Intrinsic::x86_avx2_pmovmskb: {
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
         // If we don't need any of low bits then return zero,
         // we know that DemandedMask is non-zero already.
         APInt DemandedElts = DemandedMask.zextOrTrunc(ArgWidth);
         if (DemandedElts.isNullValue())
           return ConstantInt::getNullValue(VTy);
 
         // We know that the upper bits are set to zero.
         Known.Zero.setBitsFrom(ArgWidth);
-        return nullptr;
+        KnownBitsComputed = true;
+        break;
       }
       case Intrinsic::x86_sse42_crc32_64_64:
         Known.Zero.setBitsFrom(32);
-        return nullptr;
+        KnownBitsComputed = true;
+        break;
       }
     }
+
+    if (!KnownBitsComputed)
       computeKnownBits(V, Known, Depth, CxtI);
     break;
   }
+  }
 
   // If the client is only demanding bits that we know, return the known
   // constant.
   if (DemandedMask.isSubsetOf(Known.Zero|Known.One))
     return Constant::getIntegerValue(VTy, Known.One);
   return nullptr;
 }
 

test/Transforms/InstCombine/all-bits-shift.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -instcombine -expensive-combines=0 < %s | FileCheck %s --check-prefixes=CHECK,EXPENSIVE-OFF
 ; RUN: opt -S -instcombine -expensive-combines=1 < %s | FileCheck %s --check-prefixes=CHECK,EXPENSIVE-ON
 target datalayout = "E-m:e-i64:64-n32:64"
 target triple = "powerpc64-unknown-linux-gnu"
 
 @d = global i32 15, align 4
 @b = global i32* @d, align 8
 @a = common global i32 0, align 4
 
 ; Check that both InstCombine and InstSimplify can use computeKnownBits to
 ; realize that:
 ;   ((2072 >> (L == 0)) >> 7) & 1
 ; is always zero.
 define signext i32 @main() #1 {
-; EXPENSIVE-OFF-LABEL: @main(
-; EXPENSIVE-OFF-NEXT:  entry:
-; EXPENSIVE-OFF-NEXT:    [[TMP0:%.*]] = load i32*, i32** @b, align 8
-; EXPENSIVE-OFF-NEXT:    [[TMP1:%.*]] = load i32, i32* @a, align 4
-; EXPENSIVE-OFF-NEXT:    [[LNOT:%.*]] = icmp eq i32 [[TMP1]], 0
-; EXPENSIVE-OFF-NEXT:    [[LNOT_EXT:%.*]] = zext i1 [[LNOT]] to i32
-; EXPENSIVE-OFF-NEXT:    [[SHR_I:%.*]] = lshr i32 2072, [[LNOT_EXT]]
-; EXPENSIVE-OFF-NEXT:    [[CALL_LOBIT:%.*]] = lshr i32 [[SHR_I]], 7
-; EXPENSIVE-OFF-NEXT:    [[TMP2:%.*]] = and i32 [[CALL_LOBIT]], 1
-; EXPENSIVE-OFF-NEXT:    [[TMP3:%.*]] = load i32, i32* [[TMP0]], align 4
-; EXPENSIVE-OFF-NEXT:    [[OR:%.*]] = or i32 [[TMP2]], [[TMP3]]
-; EXPENSIVE-OFF-NEXT:    store i32 [[OR]], i32* [[TMP0]], align 4
-; EXPENSIVE-OFF-NEXT:    [[TMP4:%.*]] = load i32, i32* @a, align 4
-; EXPENSIVE-OFF-NEXT:    [[LNOT_1:%.*]] = icmp eq i32 [[TMP4]], 0
-; EXPENSIVE-OFF-NEXT:    [[LNOT_EXT_1:%.*]] = zext i1 [[LNOT_1]] to i32
-; EXPENSIVE-OFF-NEXT:    [[SHR_I_1:%.*]] = lshr i32 2072, [[LNOT_EXT_1]]
-; EXPENSIVE-OFF-NEXT:    [[CALL_LOBIT_1:%.*]] = lshr i32 [[SHR_I_1]], 7
-; EXPENSIVE-OFF-NEXT:    [[TMP5:%.*]] = and i32 [[CALL_LOBIT_1]], 1
-; EXPENSIVE-OFF-NEXT:    [[OR_1:%.*]] = or i32 [[TMP5]], [[TMP3]]
-; EXPENSIVE-OFF-NEXT:    store i32 [[OR_1]], i32* [[TMP0]], align 4
-; EXPENSIVE-OFF-NEXT:    ret i32 [[OR_1]]
-;
-; EXPENSIVE-ON-LABEL: @main(
-; EXPENSIVE-ON-NEXT:  entry:
-; EXPENSIVE-ON-NEXT:    [[TMP0:%.*]] = load i32*, i32** @b, align 8
-; EXPENSIVE-ON-NEXT:    [[TMP1:%.*]] = load i32, i32* [[TMP0]], align 4
-; EXPENSIVE-ON-NEXT:    ret i32 [[TMP1]]
+; CHECK-LABEL: @main(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i32*, i32** @b, align 8
+; CHECK-NEXT:    [[TMP1:%.*]] = load i32, i32* [[TMP0]], align 4
+; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
 entry:
   %0 = load i32*, i32** @b, align 8
   %1 = load i32, i32* @a, align 4
   %lnot = icmp eq i32 %1, 0
   %lnot.ext = zext i1 %lnot to i32
   %shr.i = lshr i32 2072, %lnot.ext
   %call.lobit = lshr i32 %shr.i, 7

test/Transforms/InstCombine/known-bits.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -instcombine -expensive-combines=0 < %s | FileCheck %s --check-prefixes=CHECK,EXPENSIVE-OFF
 ; RUN: opt -S -instcombine -expensive-combines=1 < %s | FileCheck %s --check-prefixes=CHECK,EXPENSIVE-ON
 
 define void @test_shl(i1 %x) {
-; EXPENSIVE-OFF-LABEL: @test_shl(
-; EXPENSIVE-OFF-NEXT:    [[Y:%.*]] = zext i1 [[X:%.*]] to i8
-; EXPENSIVE-OFF-NEXT:    [[Z:%.*]] = shl i8 64, [[Y]]
-; EXPENSIVE-OFF-NEXT:    [[A:%.*]] = and i8 [[Z]], 1
-; EXPENSIVE-OFF-NEXT:    call void @sink(i8 [[A]])
-; EXPENSIVE-OFF-NEXT:    ret void
-;
-; EXPENSIVE-ON-LABEL: @test_shl(
-; EXPENSIVE-ON-NEXT:    call void @sink(i8 0)
-; EXPENSIVE-ON-NEXT:    ret void
+; CHECK-LABEL: @test_shl(
+; CHECK-NEXT:    call void @sink(i8 0)
+; CHECK-NEXT:    ret void
 ;
   %y = zext i1 %x to i8
   %z = shl i8 64, %y
   %a = and i8 %z, 1
   call void @sink(i8 %a)
   ret void
 }
 
 define void @test_lshr(i1 %x) {
-; EXPENSIVE-OFF-LABEL: @test_lshr(
-; EXPENSIVE-OFF-NEXT:    [[Y:%.*]] = zext i1 [[X:%.*]] to i8
-; EXPENSIVE-OFF-NEXT:    [[Z:%.*]] = lshr i8 64, [[Y]]
-; EXPENSIVE-OFF-NEXT:    [[A:%.*]] = and i8 [[Z]], 1
-; EXPENSIVE-OFF-NEXT:    call void @sink(i8 [[A]])
-; EXPENSIVE-OFF-NEXT:    ret void
-;
-; EXPENSIVE-ON-LABEL: @test_lshr(
-; EXPENSIVE-ON-NEXT:    call void @sink(i8 0)
-; EXPENSIVE-ON-NEXT:    ret void
+; CHECK-LABEL: @test_lshr(
+; CHECK-NEXT:    call void @sink(i8 0)
+; CHECK-NEXT:    ret void
 ;
   %y = zext i1 %x to i8
   %z = lshr i8 64, %y
   %a = and i8 %z, 1
   call void @sink(i8 %a)
   ret void
 }
 
 define void @test_ashr(i1 %x) {
-; EXPENSIVE-OFF-LABEL: @test_ashr(
-; EXPENSIVE-OFF-NEXT:    [[Y:%.*]] = zext i1 [[X:%.*]] to i8
-; EXPENSIVE-OFF-NEXT:    [[Z:%.*]] = ashr i8 -16, [[Y]]
-; EXPENSIVE-OFF-NEXT:    [[A:%.*]] = and i8 [[Z]], 3
-; EXPENSIVE-OFF-NEXT:    call void @sink(i8 [[A]])
-; EXPENSIVE-OFF-NEXT:    ret void
-;
-; EXPENSIVE-ON-LABEL: @test_ashr(
-; EXPENSIVE-ON-NEXT:    call void @sink(i8 0)
-; EXPENSIVE-ON-NEXT:    ret void
+; CHECK-LABEL: @test_ashr(
+; CHECK-NEXT:    call void @sink(i8 0)
+; CHECK-NEXT:    ret void
 ;
   %y = zext i1 %x to i8
   %z = ashr i8 -16, %y
   %a = and i8 %z, 3
   call void @sink(i8 %a)
   ret void
 }
 
 define void @test_udiv(i8 %x) {
-; EXPENSIVE-OFF-LABEL: @test_udiv(
-; EXPENSIVE-OFF-NEXT:    [[Y:%.*]] = udiv i8 10, [[X:%.*]]
-; EXPENSIVE-OFF-NEXT:    [[Z:%.*]] = and i8 [[Y]], 64
-; EXPENSIVE-OFF-NEXT:    call void @sink(i8 [[Z]])
-; EXPENSIVE-OFF-NEXT:    ret void
-;
-; EXPENSIVE-ON-LABEL: @test_udiv(
-; EXPENSIVE-ON-NEXT:    call void @sink(i8 0)
-; EXPENSIVE-ON-NEXT:    ret void
+; CHECK-LABEL: @test_udiv(
+; CHECK-NEXT:    call void @sink(i8 0)
+; CHECK-NEXT:    ret void
 ;
   %y = udiv i8 10, %x
   %z = and i8 %y, 64
   call void @sink(i8 %z)
   ret void
 }
 
 declare void @sink(i8)