Page MenuHomePhabricator

[ValueTracking] ComputeKnownBits - minimum leading/trailing zero bits in LSHR/SHL (PR44526)
Needs ReviewPublic

Authored by RKSimon on Oct 30 2020, 10:33 AM.

Details

Summary

Followup to D72573 - as detailed in https://blog.regehr.org/archives/1709 we don't make use of the known leading/trailing zeros for shifted values in cases where we don't know the shift amount value.

Make use of the KnownBits default shift handling first and then wrap the the ValueTracking specific poison cases around it.

Diff Detail

Unit TestsFailed

TimeTest
1,330 msx64 debian > UBSan-AddressSanitizer-lld-x86_64.TestCases/Misc::coverage-levels.cpp
Script: -- : 'RUN: at line 6'; rm -rf /mnt/disks/ssd0/agent/llvm-project/build/projects/compiler-rt/test/ubsan/AddressSanitizer-lld-x86_64/TestCases/Misc/Output/coverage-levels.cpp.tmp-dir && mkdir /mnt/disks/ssd0/agent/llvm-project/build/projects/compiler-rt/test/ubsan/AddressSanitizer-lld-x86_64/TestCases/Misc/Output/coverage-levels.cpp.tmp-dir
2,450 msx64 debian > UBSan-AddressSanitizer-x86_64.TestCases/Misc::coverage-levels.cpp
Script: -- : 'RUN: at line 6'; rm -rf /mnt/disks/ssd0/agent/llvm-project/build/projects/compiler-rt/test/ubsan/AddressSanitizer-x86_64/TestCases/Misc/Output/coverage-levels.cpp.tmp-dir && mkdir /mnt/disks/ssd0/agent/llvm-project/build/projects/compiler-rt/test/ubsan/AddressSanitizer-x86_64/TestCases/Misc/Output/coverage-levels.cpp.tmp-dir
1,180 msx64 debian > UBSan-MemorySanitizer-lld-x86_64.TestCases/Misc::coverage-levels.cpp
Script: -- : 'RUN: at line 6'; rm -rf /mnt/disks/ssd0/agent/llvm-project/build/projects/compiler-rt/test/ubsan/MemorySanitizer-lld-x86_64/TestCases/Misc/Output/coverage-levels.cpp.tmp-dir && mkdir /mnt/disks/ssd0/agent/llvm-project/build/projects/compiler-rt/test/ubsan/MemorySanitizer-lld-x86_64/TestCases/Misc/Output/coverage-levels.cpp.tmp-dir
2,330 msx64 debian > UBSan-MemorySanitizer-x86_64.TestCases/Misc::coverage-levels.cpp
Script: -- : 'RUN: at line 6'; rm -rf /mnt/disks/ssd0/agent/llvm-project/build/projects/compiler-rt/test/ubsan/MemorySanitizer-x86_64/TestCases/Misc/Output/coverage-levels.cpp.tmp-dir && mkdir /mnt/disks/ssd0/agent/llvm-project/build/projects/compiler-rt/test/ubsan/MemorySanitizer-x86_64/TestCases/Misc/Output/coverage-levels.cpp.tmp-dir
1,000 msx64 debian > UBSan-Standalone-lld-x86_64.TestCases/Misc::coverage-levels.cpp
Script: -- : 'RUN: at line 6'; rm -rf /mnt/disks/ssd0/agent/llvm-project/build/projects/compiler-rt/test/ubsan/Standalone-lld-x86_64/TestCases/Misc/Output/coverage-levels.cpp.tmp-dir && mkdir /mnt/disks/ssd0/agent/llvm-project/build/projects/compiler-rt/test/ubsan/Standalone-lld-x86_64/TestCases/Misc/Output/coverage-levels.cpp.tmp-dir
View Full Test Results (6 Failed)

Event Timeline

RKSimon created this revision.Oct 30 2020, 10:33 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 30 2020, 10:33 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
RKSimon requested review of this revision.Oct 30 2020, 10:33 AM
RKSimon added inline comments.Oct 30 2020, 10:39 AM
llvm/test/Transforms/InstCombine/and2.ll
156

These tests look like they might even need to be scrapped? And we just limit the transform to Shl instead of logical shifts in general.

llvm/test/Transforms/InstCombine/lshr-and-negC-icmpeq-zero.ll
191

Replace with -12345 so we don't have leading zeroes?

llvm/test/Transforms/InstCombine/signbit-shl-and-icmpeq-zero.ll
190

Replace with -2147483649 so we don't have trailing zeroes?

efriedma added inline comments.Oct 30 2020, 11:13 AM
llvm/lib/Analysis/ValueTracking.cpp
1252

We could also do AShr... not really useful for known zeros, but maybe for known ones.

llvm/test/Transforms/InstCombine/and2.ll
156

I suspect we might want to continue to favor icmp+zext over lshr.

RKSimon planned changes to this revision.Nov 7 2020, 7:06 AM
RKSimon updated this revision to Diff 305760.Nov 17 2020, 5:53 AM
RKSimon edited the summary of this revision. (Show Details)

Rebase now that computeKnownBitsFromShiftOperator's callbacks uses KnownBits shift handling.

RKSimon planned changes to this revision.Nov 17 2020, 6:22 AM
RKSimon updated this revision to Diff 308079.Nov 27 2020, 9:46 AM
RKSimon retitled this revision from [WIP][ValueTracking] ComputeKnownBits - minimum leading/trailing zero bits in LSHR/SHL (PR44526) to [ValueTracking] ComputeKnownBits - minimum leading/trailing zero bits in LSHR/SHL (PR44526).
RKSimon edited the summary of this revision. (Show Details)

Move the and(logical_shift(1, X), 1) --> zext(X == 0) earlier so SimplifyDemandedInstructionBits doesn't remove the pattern.

spatel added inline comments.Nov 30 2020, 4:58 AM
llvm/lib/Analysis/ValueTracking.cpp
1011–1012

I'm not sure if it changes anything directly here, but we should revisit this conflict logic (similarly at the final block in the function) because we have a poison value in IR with D71126 (see also D92270).

RKSimon marked an inline comment as done.Nov 30 2020, 7:14 AM
RKSimon added inline comments.
llvm/lib/Analysis/ValueTracking.cpp
1011–1012

TBH - I don't think we should be setting 'known bits' to arbitrary/poison numbers like this inside ValueTracking - poison handling should be inside the shift combines and we should just return 'unknown' here.

Is this something that needs to be addressed before this patch do you think? I've just kept to the current behaviour here so far.

spatel added inline comments.Nov 30 2020, 8:53 AM
llvm/lib/Analysis/ValueTracking.cpp
1011–1012

I'm not sure if this patch exposes a new way for that clamp to zero to cause trouble, but I agree that we can return unknown state here and try to deal with the poison cases more directly in instsimplify or other passes.