This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Fix to switch narrowing
Needs ReviewPublic

Authored by Gerolf on Dec 1 2016, 6:04 PM.

Details

Reviewers
hans
majnemer
Summary

This fixes an issue with switch narrowing that gets exposed
by r274233 ( https://reviews.llvm.org/D12965 - [InstCombine] shrink
switch conditions better (PR24766)). The problem is that case constants are
narrowed (to, say, width "k"), then the condition like cond = expr + const is
simplified by adding const to the case constants, and finally the new case
constants are narrowed again. However, when the width for the second round
of narrowing increases to, say, "k+n", then cond is a "k" bit expression
which won't match properly any "k+n" wide case constants.
The fix is to do the cond optimization first and only then narrow the case
constants appropriately.

Event Timeline

Gerolf updated this revision to Diff 80008.Dec 1 2016, 6:04 PM
Gerolf retitled this revision from to [InstCombine] Fix to switch narrowing.
Gerolf updated this object.
Gerolf added reviewers: sanjoy, majnemer.
Gerolf added a subscriber: llvm-commits.
majnemer edited edge metadata.

Adding a switch expert to take a look :)

hans added inline comments.Dec 7 2016, 1:10 PM
lib/Transforms/InstCombine/InstructionCombining.cpp
2276

What happened to this part?

test/Transforms/InstCombine/narrow-switch.ll
108

Why does this need to be i61 now, and should the test be renamed to reflect that?

Gerolf added inline comments.Dec 8 2016, 7:32 PM
lib/Transforms/InstCombine/InstructionCombining.cpp
2276

Gone as part of the fix: the condition expression a+const is evaluated at full width before the case constants are inspected.

test/Transforms/InstCombine/narrow-switch.ll
108

The original code evaluates the case constants.
+ It recognizes they can be truncated to 61b.
+ It truncates the case values to 61b
+ It truncates the cond value to 61b
+ It checks the condition a+const in 61b and adjusts the case value - const to 61b.
+ It returns SI, so switch narrowing is invoked again and now finds the case values to be 59b. It is this double adjustment of the case values that potentially can lead to a bug. Obviously the test cases in narrow-switch.ll did not catch it.

The fix evaluates a+const in 64b and changes the case value to value -const (still 64b). Then it finds the case values to be 61b , and adjusts with of the values and cond accordingly.

hans edited edge metadata.Dec 9 2016, 10:24 AM

I'm sorry, but I'm having trouble fully understanding exactly what the bug is that this is fixing.

It seems that this patch is regressing the @trunc64to59 test since we're now failing to truncate the condition to i59.

It does seem reasonable to optimize the switch (x + C) before doing truncation, so this is probably the right thing to do, I'd just like to understand it better.

And if we're going to do truncation after we've changed the switch condition, don't we need to move the computeKnownBits part as well? With your patch, we're first computing known bits of the condition, then changing the condition, and then later using those known bits. That seems wrong.

lib/Transforms/InstCombine/InstructionCombining.cpp
2276

Oh, I see now.

Hans, you were right. The computeKnowBits etc parts should have been moved also. Sanjay committed the fix proper in r289442. I only kept the regression test in narrow-switch.ll (r293018).

-Gerolf

sanjoy resigned from this revision.Jan 29 2022, 5:35 PM
sanjoy added inline comments.
lib/Transforms/InstCombine/InstructionCombining.cpp
2247

Range-for?

sanjoy removed a reviewer: sanjoy.Jan 29 2022, 5:36 PM