[DemandedBits] Improve analysis of second shl operand.

[fhahn]

Summary

For SHL, the demanded bits are currently improved for the first operand
by also considering second operand. As we use the second operand to
restrict the range for the first operand, we can also use it to restrict
the range of the second operand.

[nikic]

I don't really get what you're trying to do here, but this looks clearly incorrect to me. Shift operands aren't symmetrical, and the shift amount generally has to be fully demanded.

llvm/test/Analysis/DemandedBits/shl.ll

7

This is saying that shift amounts 0x4 and 0xfffffff4 behave the same way in this operation, which is clearly not the case: The latter would return poison.

[fhahn]

Yeah I realized I was thinking backwards about it. Put up D154717 to handle the motivating issue directly.

llvm/lib/Analysis/DemandedBits.cpp

case Instruction::Sub:
     }
     break;
   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).
     AB = APInt::getLowBitsSet(BitWidth, AOut.getActiveBits());
     break;
-  case Instruction::Shl:
-    if (OperandNo == 0) {
-      const APInt *ShiftAmtC;
-      if (match(UserI->getOperand(1), m_APInt(ShiftAmtC))) {
-        uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(BitWidth - 1);
-        AB = AOut.lshr(ShiftAmt);
+  case Instruction::Shl: {
 
-        // If the shift is nuw/nsw, then the high bits are not dead
-        // (because we've promised that they *must* be zero).
-        const auto *S = cast<ShlOperator>(UserI);
-        if (S->hasNoSignedWrap())
-          AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt+1);
-        else if (S->hasNoUnsignedWrap())
-          AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt);
-      }
-    }
-    break;
+        AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt + 1);
+  } break;
   case Instruction::LShr:
     if (OperandNo == 0) {
       const APInt *ShiftAmtC;
       if (match(UserI->getOperand(1), m_APInt(ShiftAmtC))) {
         uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(BitWidth - 1);
         AB = AOut.shl(ShiftAmt);
 
         // If the shift is exact, then the low bits are not dead

llvm/test/Analysis/DemandedBits/shl.ll

 ; RUN: opt -S -disable-output -passes="print<demanded-bits>" < %s 2>&1 | FileCheck %s
 
 define i8 @test_shl_const_amount_4(i32 %a) {
 ; CHECK-LABEL: 'test_shl_const_amount_4'
 ; CHECK-DAG:  DemandedBits: 0xff for %shl = shl i32 %a, 4
 ; CHECK-DAG:  DemandedBits: 0xf for %a in %shl = shl i32 %a, 4
-; CHECK-DAG:  DemandedBits: 0xffffffff for 4 in %shl = shl i32 %a, 4
+; CHECK-DAG:  DemandedBits: 0xf for 4 in %shl = shl i32 %a, 4
 ; CHECK-DAG:  DemandedBits: 0xff for %shl.t = trunc i32 %shl to i8
 ; CHECK-DAG:  DemandedBits: 0xff for %shl in %shl.t = trunc i32 %shl to i8
 ;
   %shl = shl i32 %a, 4
   %shl.t = trunc i32 %shl to i8
   ret i8 %shl.t
 }
 
 define i8 @test_shl_const_amount_5(i32 %a) {
 ; CHECK-LABEL: 'test_shl_const_amount_5'
 ; CHECK-DAG:  DemandedBits: 0xff for %shl = shl i32 %a, 5
 ; CHECK-DAG:  DemandedBits: 0x7 for %a in %shl = shl i32 %a, 5
-; CHECK-DAG:  DemandedBits: 0xffffffff for 5 in %shl = shl i32 %a, 5
+; CHECK-DAG:  DemandedBits: 0x7 for 5 in %shl = shl i32 %a, 5
 ; CHECK-DAG:  DemandedBits: 0xff for %shl.t = trunc i32 %shl to i8
 ; CHECK-DAG:  DemandedBits: 0xff for %shl in %shl.t = trunc i32 %shl to i8
 ;
   %shl = shl i32 %a, 5
   %shl.t = trunc i32 %shl to i8
   ret i8 %shl.t
 }
 
 define i8 @test_shl_const_amount_8(i32 %a) {
 ; CHECK-LABEL: 'test_shl_const_amount_8'
 ; CHECK-DAG:  DemandedBits: 0xff for %shl.t = trunc i32 %shl to i8
 ; CHECK-DAG:  DemandedBits: 0xff for %shl in %shl.t = trunc i32 %shl to i8
 ; CHECK-DAG:  DemandedBits: 0xff for %shl = shl i32 %a, 8
 ; CHECK-DAG:  DemandedBits: 0x0 for %a in %shl = shl i32 %a, 8
-; CHECK-DAG:  DemandedBits: 0xffffffff for 8 in %shl = shl i32 %a, 8
+; CHECK-DAG:  DemandedBits: 0x0 for 8 in %shl = shl i32 %a, 8
 ;
   %shl = shl i32 %a, 8
   %shl.t = trunc i32 %shl to i8
   ret i8 %shl.t
 }
 
 define i8 @test_shl_const_amount_9(i32 %a) {
 ; CHECK-LABEL: 'test_shl_const_amount_9'
 ; CHECK-DAG:  DemandedBits: 0xff for %shl = shl i32 %a, 9
 ; CHECK-DAG:  DemandedBits: 0x0 for %a in %shl = shl i32 %a, 9
-; CHECK-DAG:  DemandedBits: 0xffffffff for 9 in %shl = shl i32 %a, 9
+; CHECK-DAG:  DemandedBits: 0x0 for 9 in %shl = shl i32 %a, 9
 ; CHECK-DAG:  DemandedBits: 0xff for %shl.t = trunc i32 %shl to i8
 ; CHECK-DAG:  DemandedBits: 0xff for %shl in %shl.t = trunc i32 %shl to i8
 ;
   %shl = shl i32 %a, 9
   %shl.t = trunc i32 %shl to i8
   ret i8 %shl.t
 }