Page MenuHomePhabricator

Please use GitHub pull requests for new patches. Phabricator shutdown timeline

[ConstantRange] Calculate precise range for shl by -1
AbandonedPublic

Authored by Allen on Aug 1 2023, 7:36 PM.

Details

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

Diff Detail

Event Timeline

Allen created this revision.Aug 1 2023, 7:36 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 1 2023, 7:36 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
Allen requested review of this revision.Aug 1 2023, 7:36 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 1 2023, 7:36 PM

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 updated this revision to Diff 546361.Aug 2 2023, 1:57 AM
Allen edited the summary of this revision. (Show Details)

1、update the proofs
2、Precommit test on D156865

arsenm added inline comments.Aug 2 2023, 4:03 AM
llvm/lib/IR/ConstantRange.cpp
1501

No else after return

Allen updated this revision to Diff 547085.Aug 3 2023, 7:39 PM
Allen marked an inline comment as done.

address comment

Allen marked an inline comment as done.Aug 3 2023, 7:40 PM
Allen added inline comments.
llvm/lib/IR/ConstantRange.cpp
1501

Done, thanks

Allen marked an inline comment as done.Aug 7 2023, 6:10 AM

ping

goldstein.w.n added inline comments.Aug 7 2023, 6:59 AM
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 updated this revision to Diff 547796.Aug 7 2023, 7:52 AM

address comment

Allen marked an inline comment as done.Aug 7 2023, 7:54 AM
Allen added inline comments.
llvm/lib/IR/ConstantRange.cpp
1485

apply your comments, thanks

goldstein.w.n added inline comments.Aug 7 2023, 8:01 AM
llvm/lib/IR/ConstantRange.cpp
1501

Why are you inverting min/max here?

Allen marked an inline comment as done.Aug 7 2023, 8:16 AM
Allen added inline comments.
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 updated this revision to Diff 548847.Aug 9 2023, 6:46 PM

Add some comment for codes

goldstein.w.n added inline comments.Aug 9 2023, 8:13 PM
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 updated this revision to Diff 548867.Aug 9 2023, 8:41 PM

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

Allen marked 2 inline comments as done.Aug 9 2023, 8:42 PM
Allen added inline comments.
llvm/lib/IR/ConstantRange.cpp
1501

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

goldstein.w.n added inline comments.Aug 10 2023, 8:36 AM
llvm/lib/IR/ConstantRange.cpp
1484

bool Neg = getSingleElement && isAllNegative();

1499

(style)

// Comment
if (Neg)
   std::swap(...)
Allen updated this revision to Diff 549226.Aug 10 2023, 7:03 PM
Allen marked an inline comment as done.

address comment

Allen marked 2 inline comments as done.Aug 10 2023, 7:04 PM
Allen added inline comments.
llvm/lib/IR/ConstantRange.cpp
1499

Done, thanks

nikic added a comment.Aug 11 2023, 1:48 PM

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 updated this revision to Diff 549574.Aug 11 2023, 10:05 PM
Allen marked an inline comment as done.

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

goldstein.w.n added inline comments.Aug 15 2023, 9:52 AM
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 added inline comments.Aug 15 2023, 6:11 PM
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 updated this revision to Diff 553112.Aug 24 2023, 7:07 AM

refactor according comment

goldstein.w.n added inline comments.Aug 24 2023, 10:05 AM
llvm/lib/IR/ConstantRange.cpp
1485

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

Allen updated this revision to Diff 553375.Thu, Aug 24, 11:56 PM

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 marked an inline comment as done.Fri, Aug 25, 12:00 AM
Allen added inline comments.
llvm/lib/IR/ConstantRange.cpp
1485

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

Can you rebase this?

Allen updated this revision to Diff 553701.Fri, Aug 25, 9:47 PM
Allen marked an inline comment as done.

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 added a comment.Sun, Aug 27, 6:16 PM

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

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 updated this revision to Diff 554264.Tue, Aug 29, 4:42 AM

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

Allen abandoned this revision.Tue, Aug 29, 6:41 AM

Thanks