[DemandedBits] Add support for funnel shifts

[nikic]

Summary

Add support for funnel shifts to the DemandedBits analysis. The demanded bits of the first two operands can be determined if the shift amount is constant. The demanded bits of the third operand (shift amount) can be determined if the bitwidth is a power of two.

This is basically the same functionality as implemented in D54869 and D54478, but for DemandedBits rather than InstCombine.

[spatel]

lib/Analysis/DemandedBits.cpp

147

Is this analysis completely ignoring vector integer instructions?

It would still be good to use 'match(X, m_APInt())' in case we ever upgrade the whole thing to handle vectors. But if the answer to the above question is 'yes', then a TODO comment is ok for now.

154–156

Can we do something like D54478 for operand 2 in a follow-up patch?

[nikic]

Determine demanded bits for shift operand as well.

[nikic]

lib/Analysis/DemandedBits.cpp

147

Yes, DemandedBits currently only operates on scalar integer instructions. I originally wanted to use match() here, but seeing how all the surrounding code uses ConstantInt casts, I went with that.

I might look into adding vector support for DemandedBits, it does not seem too complicated.

154–156

I went ahead and included it here, as it seems like a small enough change :)

[spatel]

LGTM

lib/Analysis/DemandedBits.cpp

if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(UserI))
           // We need some output bits, so we need all bits of the
           // input to the right of, and including, the rightmost bit
           // known to be one.
           ComputeKnownBits(BitWidth, I, nullptr);
           AB = APInt::getLowBitsSet(BitWidth,
                  std::min(BitWidth, Known.countMaxTrailingZeros()+1));
         }
         break;
+      case Intrinsic::fshl:
+      case Intrinsic::fshr:
+        if (auto *SA = dyn_cast<ConstantInt>(II->getOperand(2))) {
+          // 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->getValue().urem(BitWidth);
+          if (II->getIntrinsicID() == Intrinsic::fshr)
+            ShiftAmt = BitWidth - ShiftAmt;
+
+          if (OperandNo == 0)
+            AB = AOut.lshr(ShiftAmt);
+          else if (OperandNo == 1)
+            AB = AOut.shl(BitWidth - ShiftAmt);
+        }
+        break;
       }
     break;
   case Instruction::Add:
   case Instruction::Sub:
   case Instruction::Mul:
     // Find the highest live output bit. We don't need any more input
     // bits than that (adds, and thus subtracts, ripple only to the
     // left).

test/Analysis/DemandedBits/intrinsics.ll

 define i8 @test_bitreverse(i32 %x) {
   %1 = or i32 %x, 1
   %2 = call i32 @llvm.bitreverse.i32(i32 %1)
   %3 = trunc i32 %2 to i8
   ret i8 %3
 }
 declare i32 @llvm.bitreverse.i32(i32)
 
+; Funnel shifts
+declare i32 @llvm.fshl.i32(i32, i32, i32)
+declare i32 @llvm.fshr.i32(i32, i32, i32)
+
+; CHECK-DAG: DemandedBits: 0xff for   %x2 = or i32 %x, 1
+; CHECK-DAG: DemandedBits: 0xff000000 for   %y2 = or i32 %y, 1
+; CHECK-DAG: DemandedBits: 0xffff for   %z = call i32 @llvm.fshl.i32(i32 %x2, i32 %y2, i32 8)
+; CHECK-DAG: DemandedBits: 0xffffffff for   %r = and i32 %z, 65535
+define i32 @test_fshl(i32 %x, i32 %y) {
+  %x2 = or i32 %x, 1
+  %y2 = or i32 %y, 1
+  %z = call i32 @llvm.fshl.i32(i32 %x2, i32 %y2, i32 8)
+  %r = and i32 %z, 65535
+  ret i32 %r
+}
+
+; CHECK-DAG: DemandedBits: 0xff for   %x2 = or i32 %x, 1
+; CHECK-DAG: DemandedBits: 0xff000000 for   %y2 = or i32 %y, 1
+; CHECK-DAG: DemandedBits: 0xffff for   %z = call i32 @llvm.fshr.i32(i32 %x2, i32 %y2, i32 24)
+; CHECK-DAG: DemandedBits: 0xffffffff for   %r = and i32 %z, 65535
+define i32 @test_fshr(i32 %x, i32 %y) {
+  %x2 = or i32 %x, 1
+  %y2 = or i32 %y, 1
+  %z = call i32 @llvm.fshr.i32(i32 %x2, i32 %y2, i32 24)
+  %r = and i32 %z, 65535
+  ret i32 %r
+}
+
+; CHECK-DAG: DemandedBits: 0xffff for   %x2 = or i32 %x, 1
+; CHECK-DAG: DemandedBits: 0x0 for   %y2 = or i32 %y, 1
+; CHECK-DAG: DemandedBits: 0xffff for   %z = call i32 @llvm.fshl.i32(i32 %x2, i32 %y2, i32 0)
+; CHECK-DAG: DemandedBits: 0xffffffff for   %r = and i32 %z, 65535
+define i32 @test_fshl_zero_shift(i32 %x, i32 %y) {
+  %x2 = or i32 %x, 1
+  %y2 = or i32 %y, 1
+  %z = call i32 @llvm.fshl.i32(i32 %x2, i32 %y2, i32 0)
+  %r = and i32 %z, 65535
+  ret i32 %r
+}
+
+; CHECK-DAG: DemandedBits: 0x0 for   %x2 = or i32 %x, 1
+; CHECK-DAG: DemandedBits: 0xffff for   %y2 = or i32 %y, 1
+; CHECK-DAG: DemandedBits: 0xffff for   %z = call i32 @llvm.fshr.i32(i32 %x2, i32 %y2, i32 32)
+; CHECK-DAG: DemandedBits: 0xffffffff for   %r = and i32 %z, 65535
+define i32 @test_fshr_full_shift(i32 %x, i32 %y) {
+  %x2 = or i32 %x, 1
+  %y2 = or i32 %y, 1
+  %z = call i32 @llvm.fshr.i32(i32 %x2, i32 %y2, i32 32)
+  %r = and i32 %z, 65535
+  ret i32 %r
+}