[ConstantRange] Calculate precise range for shl by -1

[Allen]

Summary

According https://reviews.llvm.org/D154953#inline-1516362, this fold
should be handled via simple range propagation.

proofs：https://alive2.llvm.org/ce/z/g5xBqe

[goldstein.w.n]

The proofs shouldn't only be for 32. It should use param C that you setup with assumes

llvm/test/Transforms/FunctionSpecialization/and-add-shl.ll

2 ↗

(On Diff #546294)

Should the tests be in a different place? At the very least please precommit change of pass so we can more accurately see what's the result of the code change vs the pass change.

[Allen]

1、update the proofs
2、Precommit test on D156865

[arsenm]

llvm/lib/IR/ConstantRange.cpp

1501

No else after return

[Allen]

address comment

[Allen]

llvm/lib/IR/ConstantRange.cpp

1501

Done, thanks

[Allen]

ping

[goldstein.w.n]

llvm/lib/IR/ConstantRange.cpp

1485

Imo should be Min = -Min; Max = -Max here instead of abs, think thats clearer given your negating.

Can you also add a comment explaining why you're doing this.

[Allen]

address comment

[Allen]

llvm/lib/IR/ConstantRange.cpp

1485

apply your comments, thanks

[goldstein.w.n]

llvm/lib/IR/ConstantRange.cpp

1501

Why are you inverting min/max here?

[Allen]

llvm/lib/IR/ConstantRange.cpp

1501

because this is a negative value. For example
-1 << x.min > -1 << x.max, so its range [-1 << x.max, -1 << x.min +1]

[Allen]

Add some comment for codes

[goldstein.w.n]

llvm/lib/IR/ConstantRange.cpp

1501

I'm probably missing something (haven't really worked on ConstantRanges much), but since you are re-negating min/max isn't that already doing it?

[Allen]

For negitive value c, its max value and min value of shifted range should be swapped

[Allen]

llvm/lib/IR/ConstantRange.cpp

1501

Yes, it is already done, but need swap it max/min values for negitive value

[goldstein.w.n]

llvm/lib/IR/ConstantRange.cpp

1484

bool Neg = getSingleElement && isAllNegative();

1499

(style)

// Comment
if (Neg)
   std::swap(...)

[Allen]

address comment

[Allen]

llvm/lib/IR/ConstantRange.cpp

1499

Done, thanks

[nikic]

Your patch is failing the ConstantRange unit tests. That's also the place to add test coverage for this change. This patch has no relation to FunctionSpecialization at all.

[Allen]

add condition OtherMax.ule(Max.abs().countl_zero()) to fix the failure cases reported in unittests/IR/ConstantRangeTest.cpp

[Allen]

ping :)

[goldstein.w.n]

llvm/lib/IR/ConstantRange.cpp

1485

You can either drop the !Neg here (my opinion) or drop the OtherMax.ule(Max...) in Neg definition.

If OtherMax.ugt(...) is true, Neg will always be false.
If OtherMax.ule(...) is false, then this if statement here will ensure Neg is valid after.

[Allen]

llvm/lib/IR/ConstantRange.cpp

1485

thanks for your comment.

the **OtherMax.ule(Max.abs()...)** in Neg definition has extra **abs()**, so this is different from the origin **OtherMax.ugt(...)** ?

For example, if the Max type is i8, then -1 is 255, so Max.countl_zero() is 0, so the negative value Max will return getFull(), and the Neg condition is used to skip this blockage.

[Allen]

refactor according comment

[goldstein.w.n]

llvm/lib/IR/ConstantRange.cpp

1485

I missed that but you still changed the codes. Was it not an issue afterall?

[Allen]

I revert to use the previous change because there is an failure case Clang :: CodeGenOpenCL/shifts.cl
showed that the check getSingleElement() && isAllNegative() && OtherMax.ugt(Max.abs().countl_zero()) is necessary

[Allen]

llvm/lib/IR/ConstantRange.cpp

1485

Yes, it is an issue, and the case Clang :: CodeGenOpenCL/shifts.c will failure.

[goldstein.w.n]

Can you rebase this?

[Allen]

Add a negative test to show that the condition getSingleElement() is necessary for negative value, (derived from the C testcase in file Clang :: CodeGenOpenCL/shifts.cl)

[Allen]

In D156845#4617745, @goldstein.w.n wrote:

Can you rebase this?

I don't find this PR has some changes after rebasing. So I have a dig into it, and attached the negative test positiveShift32

[goldstein.w.n]

In D156845#4620358, @Allen wrote:

In D156845#4617745, @goldstein.w.n wrote:

Can you rebase this?

I don't find this PR has some changes after rebasing. So I have a dig into it, and attached the negative test positiveShift32

Its not checkoutable as its not based on master.

[Allen]

try to rebase on today's new commit aebe312c according comment

[nikic]

I've implemented this myself in https://github.com/llvm/llvm-project/commit/4dd392fcd7847ef73233cd2f24623064ebc90a16.

[Allen]

Thanks

llvm/lib/IR/ConstantRange.cpp

     if (RHS->ule(EqualLeadingBits))
       return getNonEmpty(Min << *RHS, (Max << *RHS) + 1);
 
     return getNonEmpty(APInt::getZero(BW),
                        APInt::getBitsSetFrom(BW, RHS->getZExtValue()) + 1);
   }
 
   APInt OtherMax = Other.getUnsignedMax();
+  // Make sure single element for negative value just for simplicity,
+  // otherwise we should checking both Lower and Upper for negative value.
+  bool Neg = getSingleElement() && isAllNegative() &&
+             OtherMax.ule(Max.abs().countl_zero());
 
   // There's overflow!
-  if (OtherMax.ugt(Max.countl_zero()))
+  if (OtherMax.ugt(Max.countl_zero()) && !Neg)
     return getFull();
 
   // FIXME: implement the other tricky cases
 
   Min <<= Other.getUnsignedMin();
   Max <<= OtherMax;
 
+  // For negitive value c, its shifted range is [c<<Other.max) , c<<Other.min)]
+  if (Neg)
+    std::swap(Min, Max);
+
   return ConstantRange::getNonEmpty(std::move(Min), std::move(Max) + 1);
 }
 
 ConstantRange
 ConstantRange::lshr(const ConstantRange &Other) const {
   if (isEmptySet() || Other.isEmptySet())
     return getEmpty();
 
   APInt max = getUnsignedMax().lshr(Other.getUnsignedMin()) + 1;
   APInt min = getUnsignedMin().lshr(Other.getUnsignedMax());
   return getNonEmpty(std::move(min), std::move(max));
 }

llvm/test/Transforms/SCCP/and-add-shl.ll

 ; https://alive2.llvm.org/ce/z/YNYYdV
 define i8 @and_not_shl(i8 %x) {
 ; CHECK-LABEL: define i8 @and_not_shl
 ; CHECK-SAME: (i8 [[X:%.*]]) {
 ; CHECK-NEXT:    [[OP1_P2:%.*]] = icmp ule i8 [[X]], 5
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[OP1_P2]])
 ; CHECK-NEXT:    [[SHIFT:%.*]] = shl nsw i8 -1, [[X]]
 ; CHECK-NEXT:    [[NOT:%.*]] = xor i8 [[SHIFT]], -1
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[NOT]], 32
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 0
 ;
   %op1_p2 = icmp ule i8 %x, 5
   call void @llvm.assume(i1 %op1_p2)
   %shift = shl i8 -1, %x
   %not = xor i8 %shift, -1
   %r = and i8 %not, 32
   ret i8 %r
 }
 
 define i8 @and_not_shl_1(i8 %x) {
 ; CHECK-LABEL: define i8 @and_not_shl_1
 ; CHECK-SAME: (i8 [[X:%.*]]) {
 ; CHECK-NEXT:    [[OP1_P2:%.*]] = icmp ule i8 [[X]], 4
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[OP1_P2]])
 ; CHECK-NEXT:    [[SHIFT:%.*]] = shl nsw i8 -1, [[X]]
 ; CHECK-NEXT:    [[NOT:%.*]] = xor i8 [[SHIFT]], -1
-; CHECK-NEXT:    [[R:%.*]] = and i8 [[NOT]], 48
-; CHECK-NEXT:    ret i8 [[R]]
+; CHECK-NEXT:    ret i8 0
 ;
   %op1_p2 = icmp ule i8 %x, 4
   call void @llvm.assume(i1 %op1_p2)
   %shift = shl i8 -1, %x
   %not = xor i8 %shift, -1
   %r = and i8 %not, 48 ;    3 * 16
   ret i8 %r
 }

 ;
   %op1_p2 = icmp ule i8 %x, 3
   call void @llvm.assume(i1 %op1_p2)
   %shift = shl i8 -1, %x
   %not = xor i8 %shift, -1
   %r = and i8 %not, 4   ; expect 8
   ret i8 %r
 }
+
+; Negative test: https://alive2.llvm.org/ce/z/ZZrjkj
+define i32 @positiveShift32(i32 noundef %a, i32 noundef %b) {
+; CHECK-LABEL: define i32 @positiveShift32
+; CHECK-SAME: (i32 noundef [[A:%.*]], i32 noundef [[B:%.*]]) {
+; CHECK-NEXT:    [[OP0_P1:%.*]] = icmp slt i32 [[A]], 0
+; CHECK-NEXT:    call void @llvm.assume(i1 [[OP0_P1]])
+; CHECK-NEXT:    [[SHL_MASK:%.*]] = and i32 [[B]], 31
+; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[A]], [[SHL_MASK]]
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[SHL]], 2
+; CHECK-NEXT:    ret i32 [[ADD]]
+;
+  %op0_p1 = icmp slt i32 %a, 0
+  call void @llvm.assume(i1 %op0_p1)
+  %shl.mask = and i32 %b, 31
+  %shl = shl i32 %a, %shl.mask ; the %a is not a single element value
+  %add = add nsw i32 %shl, 2
+  ret i32 %add
+}