[DemandedBits] Add Div instruction to DetermineLiveOperandBits

[zjaffal]

Summary

DetermineLiveOperandBits is missing a case for div instructions. Before the patch, the pass assumed that the operand of div instructions uses all the available bits which can be an overestimate.

[RKSimon]

Please can you add udiv/sdiv exhaustive test coverage to llvm-project\llvm\unittests\IR\DemandedBitsTest.cpp

[zjaffal]

In D136753#3885186, @RKSimon wrote:

Please can you add udiv/sdiv exhaustive test coverage to llvm-project\llvm\unittests\IR\DemandedBitsTest.cpp

Would be possible to use the same logic used for add and sub or I need to create something new? Also do you think we should add ir tests as well or that wouldn't be necessary

[RKSimon]

In D136753#3885422, @zjaffal wrote:

In D136753#3885186, @RKSimon wrote:

Please can you add udiv/sdiv exhaustive test coverage to llvm-project\llvm\unittests\IR\DemandedBitsTest.cpp

Would be possible to use the same logic used for add and sub or I need to create something new? Also do you think we should add ir tests as well or that wouldn't be necessary

You'll probably have to create a similar ForeachKnownBits system from scratch

Adding IR tests to test\Analysis\DemandedBits is always welcome - its pretty empty in there

[t.p.northover]

I don't think this is how division works. It mixes bits up far more than add/sub/mul for which a bit in the input can only affect equal or lower ones in the output.

[RKSimon]

In D136753#3915555, @t.p.northover wrote:

I don't think this is how division works. It mixes bits up far more than add/sub/mul for which a bit in the input can only affect equal or lower ones in the output.

This is why I wanted to see an exhaustive test, its more subtle than the current attempt - but there's definitely a case for a suitable demanded bitmask of the lower bits based off the number of common known leading sign/zero bits of the arguments.

[fhahn]

Marking as changes requested as per the previous comments.

[lebedev.ri]

This review may be stuck/dead, consider abandoning if no longer relevant.
Removing myself as reviewer in attempt to clean dashboard.

llvm/lib/Analysis/DemandedBits.cpp

void DemandedBits::determineLiveOperandBits(
   case Instruction::Sub:
     if (AOut.isMask()) {
       AB = AOut;
     } else {
       ComputeKnownBits(BitWidth, UserI->getOperand(0), UserI->getOperand(1));
       AB = determineLiveOperandBitsSub(OperandNo, AOut, Known, Known2);
     }
     break;
+  case Instruction::UDiv:
+  case Instruction::SDiv:
   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) {

llvm/test/Transforms/PhaseOrdering/ARM/arm_mean_q7.ll

 ; CHECK-NEXT:    [[PSRC_ADDR_0_LCSSA:%.*]] = phi ptr [ [[PSRC]], [[ENTRY:%.*]] ], [ [[UGLYGEP]], [[WHILE_END_LOOPEXIT]] ]
 ; CHECK-NEXT:    [[SUM_0_LCSSA:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[TMP3]], [[WHILE_END_LOOPEXIT]] ]
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[BLOCKSIZE]], 15
 ; CHECK-NEXT:    [[CMP2_NOT15:%.*]] = icmp eq i32 [[AND]], 0
 ; CHECK-NEXT:    br i1 [[CMP2_NOT15]], label [[WHILE_END5:%.*]], label [[VECTOR_BODY:%.*]]
 ; CHECK:       vector.body:
 ; CHECK-NEXT:    [[ACTIVE_LANE_MASK:%.*]] = tail call <16 x i1> @llvm.get.active.lane.mask.v16i1.i32(i32 0, i32 [[AND]])
 ; CHECK-NEXT:    [[WIDE_MASKED_LOAD:%.*]] = tail call <16 x i8> @llvm.masked.load.v16i8.p0(ptr [[PSRC_ADDR_0_LCSSA]], i32 1, <16 x i1> [[ACTIVE_LANE_MASK]], <16 x i8> poison)
-; CHECK-NEXT:    [[TMP4:%.*]] = sext <16 x i8> [[WIDE_MASKED_LOAD]] to <16 x i32>
+; CHECK-NEXT:    [[TMP4:%.*]] = zext <16 x i8> [[WIDE_MASKED_LOAD]] to <16 x i32>
 ; CHECK-NEXT:    [[TMP5:%.*]] = select <16 x i1> [[ACTIVE_LANE_MASK]], <16 x i32> [[TMP4]], <16 x i32> zeroinitializer
 ; CHECK-NEXT:    [[TMP6:%.*]] = tail call i32 @llvm.vector.reduce.add.v16i32(<16 x i32> [[TMP5]])
 ; CHECK-NEXT:    [[TMP7:%.*]] = add i32 [[TMP6]], [[SUM_0_LCSSA]]
 ; CHECK-NEXT:    br label [[WHILE_END5]]
 ; CHECK:       while.end5:
 ; CHECK-NEXT:    [[SUM_1_LCSSA:%.*]] = phi i32 [ [[SUM_0_LCSSA]], [[WHILE_END]] ], [ [[TMP7]], [[VECTOR_BODY]] ]
 ; CHECK-NEXT:    [[DIV:%.*]] = sdiv i32 [[SUM_1_LCSSA]], [[BLOCKSIZE]]
 ; CHECK-NEXT:    [[CONV6:%.*]] = trunc i32 [[DIV]] to i8