Change Details

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 reduction all the time can result in subtractions being inserted that are not wanted later, because every switch cases is handled by actual value when lowered into if/else, but these transforms can easily undo this, and it is better than not generating excessively large tables. 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.

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.

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 reduction all the time can result in subtractions being inserted that are not wanted later, because every switch cases is handled by actual value when lowered into if/else, but these transforms can easily undo thiseven when not generating a Lookup/Jump Table actually improves even LowerSwitch, and it is better than not generating excessively large tablesas 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.