This is an archive of the discontinued LLVM Phabricator instance.

[SimplifyCFG] add nsw on SwitchToLookupTable Index calculation
ClosedPublic

Authored by khei4 on Mar 26 2023, 2:24 AM.

Details

Summary

This is the first step to resolve the following issue, no-signed wrap flags propagation on SwitchToLookupTable.
https://github.com/llvm/llvm-project/issues/59671

motivated transformation: https://alive2.llvm.org/ce/z/GZs_dj

  1. add nsw/nuw on SwitchToLookupTable in SimplifyCFG

    a. add nsw on SwitchToLookupTable index calculation on MinCaseVal subtraction <- this revision will be

    https://alive2.llvm.org/ce/z/WSFRK5

    b. add nuw/nsw on BuildLookuptable BitMap shiftwidth calculation https://reviews.llvm.org/D150838

    https://alive2.llvm.org/ce/z/5Cmc72

    c. add nsw on BuildLookuptable LinearMap calculation https://reviews.llvm.org/D150943

    https://alive2.llvm.org/ce/z/cKBQfs
  1. preserve nsw on InstCombine for the cases. https://reviews.llvm.org/D152088

transformation: https://alive2.llvm.org/ce/z/ZWmZLv

Diff Detail

Event Timeline

khei4 created this revision.Mar 26 2023, 2:24 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 26 2023, 2:24 AM
khei4 requested review of this revision.Mar 26 2023, 2:24 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 26 2023, 2:24 AM
khei4 edited the summary of this revision. (Show Details)Mar 26 2023, 3:30 AM
khei4 updated this revision to Diff 511021.Apr 5 2023, 2:03 AM

update test (without confirmation)

khei4 edited the summary of this revision. (Show Details)May 7 2023, 10:59 PM
khei4 updated this revision to Diff 520376.May 8 2023, 7:51 AM

change plan to use Unreachabiliity of DefaultDest. (not yet change on test except X86)

khei4 edited the summary of this revision. (Show Details)May 8 2023, 7:53 AM
khei4 updated this revision to Diff 521548.May 11 2023, 8:50 PM

reuse DefaultIsReachable and fix tests

khei4 retitled this revision from (WIP)[SimplifyCFG] add nuw/nsw on SwitchToLookupTable to (WIP)[SimplifyCFG] add nsw on SwitchToLookupTable.May 11 2023, 8:56 PM
khei4 edited the summary of this revision. (Show Details)
nikic added inline comments.May 14 2023, 1:33 PM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6122

Looking at how LinearMultiplier and LinearOffset are generated in SwitchLookupTable, I don't think that always setting NSW is correct. Nothing in the calculation suggests that it can't overflow. I believe we would have to track this separate when these values are computed. I also think that DefaultIsReachable doesn't matter for this part: At this point the range of the input values has already been checked.

6139

I believe in this case both NUW and NSW can always be set. We know that this multiply must be < BitWidth to be a valid shift amount, so it can't overflow in either signed or unsigned sense.

6504–6505

Add something like // If the default is unreachable, all case values are s>= MinCaseVal, so the subtraction cannot wrap in a signed sense.

This part of the change looks correct to me. It might be worthwhile to split it from the changes to BuildLookup.

khei4 added a comment.EditedMay 14 2023, 11:05 PM

@nikic Thank you for the review!

This part of the change looks correct to me. It might be worthwhile to split it from the changes to BuildLookup.

As you suggested, I'll first focus on flags only by DeafultsReachable outside of BuildLookup on this revision!

khei4 retitled this revision from (WIP)[SimplifyCFG] add nsw on SwitchToLookupTable to (WIP)[SimplifyCFG] add nsw on SwitchToLookupTable by DefaultsReachable.May 14 2023, 11:13 PM
khei4 edited the summary of this revision. (Show Details)
khei4 retitled this revision from (WIP)[SimplifyCFG] add nsw on SwitchToLookupTable by DefaultsReachable to [SimplifyCFG] add nsw on SwitchToLookupTable index calculation by DefaultsReachable.May 14 2023, 11:15 PM
khei4 edited the summary of this revision. (Show Details)
khei4 edited the summary of this revision. (Show Details)May 14 2023, 11:15 PM
khei4 edited the summary of this revision. (Show Details)May 15 2023, 7:08 AM
khei4 retitled this revision from [SimplifyCFG] add nsw on SwitchToLookupTable index calculation by DefaultsReachable to (WIP)[SimplifyCFG] add nsw on SwitchToLookupTable index calculation by DefaultsReachable.May 15 2023, 6:59 PM
khei4 retitled this revision from (WIP)[SimplifyCFG] add nsw on SwitchToLookupTable index calculation by DefaultsReachable to (WIP)[SimplifyCFG] add nsw on SwitchToLookupTable index calculation outside of BuildLookup.May 17 2023, 6:47 AM
khei4 edited the summary of this revision. (Show Details)
khei4 updated this revision to Diff 523037.May 17 2023, 6:57 AM

temporary remove changes in BuildLookup

khei4 retitled this revision from (WIP)[SimplifyCFG] add nsw on SwitchToLookupTable index calculation outside of BuildLookup to [SimplifyCFG] add nsw on SwitchToLookupTable index calculation on .May 17 2023, 8:11 PM
khei4 edited the summary of this revision. (Show Details)
khei4 retitled this revision from [SimplifyCFG] add nsw on SwitchToLookupTable index calculation on to [SimplifyCFG] add nsw on SwitchToLookupTable index calculation on MinCaseVal subtraction.May 17 2023, 8:34 PM
khei4 edited the summary of this revision. (Show Details)
khei4 updated this revision to Diff 523248.May 17 2023, 8:36 PM

update non-X86 platform test, narrow revision scope

khei4 edited the summary of this revision. (Show Details)May 17 2023, 8:51 PM
khei4 retitled this revision from [SimplifyCFG] add nsw on SwitchToLookupTable index calculation on MinCaseVal subtraction to [SimplifyCFG] add nsw on SwitchToLookupTable Index calculation .May 17 2023, 9:29 PM
nikic added inline comments.May 18 2023, 7:17 AM
llvm/test/Transforms/SimplifyCFG/X86/switch-table-bug.ll
12 ↗(On Diff #523248)

This is a miscompile: E.g. if the input was 0 then we'll do 0 - (-2) which should be 2 but overflows to -2.

The bit I missed here is that we're effectively mapping a signed range to an unsigned one, doing something like -2 -> 0, -1 -> 1, 0 -> 2, 1 -> 3, but of course the last two become -2 and -1 when interpreted as signed.

I think we need an additional check that TableSize is small enough (should not be larger than half the integer space, or something like that).

nikic added inline comments.May 18 2023, 9:19 AM
llvm/test/Transforms/SimplifyCFG/X86/switch-table-bug.ll
12 ↗(On Diff #523248)

Probably the simplest way to check this is to do something like MaxCaseVal->getValue().ssub_ov(MinCaseVal->getValue()) and check that it doesn't overflow. That directly corresponds to the operation we're doing...

khei4 added inline comments.May 18 2023, 9:53 PM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6504–6505

Add something like // If the default is unreachable, all case values are s>= MinCaseVal, so the subtraction cannot wrap in a signed sense.

Thanks! I'll basically took this comment as it is

llvm/test/Transforms/SimplifyCFG/X86/switch-table-bug.ll
12 ↗(On Diff #523248)

It seems right! Thank you for a good catch!

Probably the simplest way to check this is to do something like MaxCaseVal->getValue().ssub_ov(MinCaseVal->getValue()) and check that it doesn't overflow.

Yeah, it seems like repetitions though, seem simpler than
1 << (TableIndexOffset->getBitWidth() - 1) < TableSize - 1. :)

khei4 updated this revision to Diff 523652.May 18 2023, 9:55 PM

fix to check signed overflow directly. (may need to be update tests

Looks like this no longer affects any of the existing tests. Could you please add a test where this adds the nsw flag? Preferably two tests, one directly before overflow happens, and one directly after.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6507

CanBeWrapped -> CanWrap?

Thank you for the review!

Looks like this no longer affects any of the existing tests. Could you please add a test where this adds the nsw flag? Preferably two tests, one directly before overflow happens, and one directly after.

Sure!

llvm/lib/Transforms/Utils/SimplifyCFG.cpp
6507

Thanks! MayWrap might be correct :)

khei4 updated this revision to Diff 524162.May 21 2023, 10:39 PM

add tests.

khei4 updated this revision to Diff 524163.May 21 2023, 10:59 PM

change flag name and remove obsolete comment.

nikic accepted this revision.May 22 2023, 12:50 PM

LGTM

llvm/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll
1812

signd -> signed

This revision is now accepted and ready to land.May 22 2023, 12:50 PM
khei4 updated this revision to Diff 524605.May 23 2023, 1:25 AM

fix typo

This revision was landed with ongoing or failed builds.May 23 2023, 2:02 AM
This revision was automatically updated to reflect the committed changes.
khei4 edited the summary of this revision. (Show Details)Jun 12 2023, 9:49 PM