I am trying to move towards much more space-efficient wwitch statements, using popcnt, as described in PR39013. This is the first patch towards that goal.
ReduceSwitchRange only ran if the switch statement wasn't "dense", resulting in unnecessary sparse switch statements. This is a very cheap transform, if it can make improvements should be run, so run it all the time. (that is all IsSwitchDense did, it did not determine if a jump table or lookup table should be generated) Doing this even when not generating a Lookup/Jump Table actually improves even LowerSwitch, as LowerSwitch wants the range to be constrained. Also:
- Do not do an expensive general GCD calculation when only countTrailingZeros() information is used from it.
- Re-order values to ideal with a subtraction, instead of only covering some cases by treating the values as signed.
- Implement the ctlz/cttz transform that was suggested in the comments. This transform is still not ideal, as SwitchToLookupTable doesn't know the potential range of values has been reduced, and there is no good plumbing in LLVM (that I know of) to get that information, and KnownBits is not sufficient.
- Do not reduce the switch range in SwitchToLookupTable
Gotcha: There a few cases where the old NeedMask would have been better than the sparse map, which patch I have yet to submit. However with only a few holes (8 bytes of holes) the old NeedMask implementation would use more space, as it doesn't use popcnt. Also, removing that feature means this will not be suitable for merging until it's replacement is approved.