This is an archive of the discontinued LLVM Phabricator instance.

[SimplifyCFG] Prune code from a provably unreachable switch default
ClosedPublic

Authored by reames on Aug 12 2015, 3:09 PM.

Details

Summary

As Sanjoy pointed out over in http://reviews.llvm.org/D11819, a switch on an icmp should always be able to become a branch instruction. This patch generalizes that notion slightly to prove that the default case of a switch is unreachable if the cases completely cover all possible bit patterns in the condition. Once that's done, the switch to branch conversion kicks in just fine.

Note: Duplicate case values are disallowed by the LangRef and verifier.

Diff Detail

Event Timeline

reames updated this revision to Diff 31988.Aug 12 2015, 3:09 PM
reames retitled this revision from to [SimplifyCFG] Prune code from a provably unreachable switch default.
reames updated this object.
reames added reviewers: sanjoy, chenli, hans.
reames added a subscriber: llvm-commits.
sanjoy edited edge metadata.Aug 12 2015, 3:21 PM

Minor drop by comments inline. I'll let someone more familiar with this bit of code do a proper review.

lib/Transforms/Utils/SimplifyCFG.cpp
3256

Can SI->getNumCases() ever be > pow(2, Bits)?

I don't think checking for >= is sufficient if switches allow duplicate cases, if that's how number of case can be greater than 2^Bits.

test/Transforms/SimplifyCFG/switch-dead-default.ll
25

Interesting -- I did not know that i2 4 worked -- I presume this is the same as i2 0?

sanjoy added inline comments.Aug 12 2015, 3:25 PM
lib/Transforms/Utils/SimplifyCFG.cpp
3256

I don't think checking for >= is sufficient if switches allow duplicate cases, if that's how number of case can be greater than 2^Bits.

I had missed your note in the commit message -- given that duplicate values are prohibited, I think it should be sufficient to check for equality.

reames added inline comments.Aug 12 2015, 3:33 PM
lib/Transforms/Utils/SimplifyCFG.cpp
3256

I'll switch to the equality before submission.

test/Transforms/SimplifyCFG/switch-dead-default.ll
25

Yep, though that really wasn't intentional. I'll adjust the tests to use the more natural 0-3 before submission.

hans edited edge metadata.Aug 12 2015, 3:34 PM

Nice!

lib/Transforms/Utils/SimplifyCFG.cpp
3255

hmm, why does DeadCases have to be empty?

3256

ultra nit: space between , and Bits

majnemer added inline comments.
lib/Transforms/Utils/SimplifyCFG.cpp
3256

pow uses doubles, was this intentional?

Could we use 1U << Bits or 1ULL << Bits?

sanjoy added inline comments.Aug 12 2015, 4:13 PM
lib/Transforms/Utils/SimplifyCFG.cpp
3256

Could we use 1U << Bits or 1ULL << Bits?

Won't that break if Bits is > 64?

majnemer added inline comments.Aug 12 2015, 4:44 PM
lib/Transforms/Utils/SimplifyCFG.cpp
3256

Right, I guess we'd need to do something like Log2_32(SI->getNumCases()) >= Bits.

reames added inline comments.Aug 12 2015, 4:59 PM
lib/Transforms/Utils/SimplifyCFG.cpp
3255

My original reasoning was that a dead case didn't cover the input, but thinking about it, I think that's false. By proving that it's dead, it still covered that value in the input space. So, it can be removed. :)

3256

I'm tempted to use the shift by Bits with an additional constraint that Bits is <= 63. I can't imagine we're every going to see a switch with more than 2^63 cases. :)

hans added inline comments.Aug 12 2015, 5:04 PM
lib/Transforms/Utils/SimplifyCFG.cpp
3256

We won't; a switch can not have more than 2^32 cases (actually it's probably 2^21-1 or something like that).

But I don't think there's any limit to how wide the switch expression is, so we still need to be careful here.

reames updated this revision to Diff 32010.Aug 12 2015, 5:32 PM
reames edited edge metadata.

Revised per review comments.

reames updated this revision to Diff 32012.Aug 12 2015, 5:35 PM

Add a test case which exercises the Bits > 63 case for completeness.

hans accepted this revision.Aug 14 2015, 9:41 AM
hans edited edge metadata.

I was trying to remember where I'd seen something like this before, and found this in a patch that never got submitted: http://reviews.llvm.org/D6269#inline-51754

It's taking the same idea a little further by taking known bits into account. For example, if the condition is an i4 where we know the two most significant bits are always 0, having four "live" cases (0,1,2,3) means the default is unreachable.

Would you like to add that here? Could also be a follow-up if you like.

This revision is now accepted and ready to land.Aug 14 2015, 9:41 AM
In D11995#224516, @hans wrote:

I was trying to remember where I'd seen something like this before, and found this in a patch that never got submitted: http://reviews.llvm.org/D6269#inline-51754

It's taking the same idea a little further by taking known bits into account. For example, if the condition is an i4 where we know the two most significant bits are always 0, having four "live" cases (0,1,2,3) means the default is unreachable.

Would you like to add that here? Could also be a follow-up if you like.

This sounds like an interesting follow on, but let me land the current change first. Once that's in, I'll extend as you propose.

This revision was automatically updated to reflect the committed changes.