This is an archive of the discontinued LLVM Phabricator instance.

LowerSwitch: replace unreachable default with popular case destination
ClosedPublic

Authored by hans on Dec 16 2014, 3:20 PM.

Details

Summary

SimplifyCFG currently does this transformation, but I'm planning to remove that (see [1]) in order to be able to exploit unreachable defaults in lowering. By moving it here, we make sure that we don't lose functionality for IR going through SImplifyCFG -> LowerSwitch.

Please take a look.

  1. http://reviews.llvm.org/D6471

Diff Detail

Event Timeline

hans updated this revision to Diff 17370.Dec 16 2014, 3:20 PM
hans retitled this revision from to LowerSwitch: replace unreachable default with popular case destination.
hans updated this object.
hans edited the test plan for this revision. (Show Details)
hans added reviewers: resistor, kariddi.
hans added subscribers: Unknown Object (MLST), hansw.
kariddi edited edge metadata.Dec 23 2014, 10:05 AM

Sorry for the delay! I didn't catch this conversation :-)

The idea itself of this optimization is good and ideally sounds promising for the case where there are many different, non-contiguous switch cases all pointing to the same block, but I'm not sure this is worth it overall.

The main problem is that the presence of a default block confuses the UpperBound and LowerBound computations , that cannot rely on skipping gaps between ranges of switch values anymore, which is a good optimization if the default block is absent.

Your test case is an example of code that gets worse in this case with the patch that without.

I guess is a matter of deciding if the case of non-contiguous switch cases pointing to the same block is a common case or not.

I'm attaching the graphs of the test case lowered through lowerswitch with and without the patch to give context to what I mean:

hans added a comment.Dec 23 2014, 12:17 PM

Thanks for your comments!

I'll see if I can rework the patch to be smarter about when to replace the unreachable default. (Probably not until after the holidays though.)

However, SimplifyCFG already does this transformation (I'm trying to remove it to be able to exploit unreachable switches in codegen). Does SimplifyCFG not normally run fore LowerSwitch?

Thanks for working on this :-)

Usually LowerSwitch runs pretty late in the pipeline, in preparation for CodeGen.

hans updated this revision to Diff 17977.Jan 10 2015, 2:25 PM
hans updated this object.
hans edited edge metadata.

The main problem is that the presence of a default block confuses the UpperBound and LowerBound computations , that cannot rely on skipping gaps between ranges of switch values anymore, which is a good optimization if the default block is absent.

Your test case is an example of code that gets worse in this case with the patch that without.

I think the problem was just that my patch prevented us from setting LowerBound and UpperBound. We should still set them even if the unreachable default gets replaced with a reachable destination. With that, I think there is no trade-off here - replacing the unreachable default is always profitable or neutral.

Thanks for catching that my test case was an example of where things got worse; that's embarrassing :) I've added a new test that benefits both from replacing the default and having UpperBound and LowerBound set.

Usually LowerSwitch runs pretty late in the pipeline, in preparation for CodeGen.

Looking forward to getting this transformation out of SimplifyCFG so LowerSwitch can benefit, then :)

hans updated this revision to Diff 18283.Jan 15 2015, 5:13 PM

Updating the patch to handle the situation where all cases get moved to the default, and simplifying the code a little.

Hi Hans, thanks for your work on this! I'm looking into your patch now :-)

Marcello

2015-01-15 17:13 GMT-08:00 Hans Wennborg <hans@chromium.org>:

Updating the patch to handle the situation where all cases get moved to
the default, and simplifying the code a little.

http://reviews.llvm.org/D6697

Files:

lib/Transforms/Utils/LowerSwitch.cpp
test/Transforms/LowerSwitch/2014-06-11-SwitchDefaultUnreachableOpt.ll
test/Transforms/LowerSwitch/fold-popular-case-to-unreachable-default.ll

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

I still see some potential drawbacks on some CFGs.

Lets take this example, derived from your original test:

In this case there is a gap between the values of the cases.
Your Min/MaxCase approach works fine on the edges of the range of the cases, but doesn't do anything in the case there is a gap between cases.
If there is a gap between the cases the fact that there is no Default block still gives us the possibility to avoid having to check if the value falls into the gap or not.
Basically we are still losing the boundary information on the bounds that fall on gaps.

Here are the CFG of the example with and without your patch.

Maybe there is a way to actually also check for the boundaries on the gaps and integrating them in the algorithm.
I have to think about it, maybe we can also speak about it on IRC if you want :-)

hans added a comment.Jan 15 2015, 9:41 PM

Ah, I see what you mean. I didn't notice that the code was exploiting that.

I guess we could try to come up with a heuristic for when replacing the unreachable default is profitable even though we can't exploit the unreachable gaps. For example, if we can remove half or more of the case clusters, it's probably profitable.

I'm not sure how to proceed here though. My patch is really just preserving current functionality, but moving it out of SimplifyCFG (and now with the bonus of allowing this code to set Lower/UpperBound.)

If you think it's better for LowerSwitch to not do this transformation, I'm fine with that too. Or we could try to come up with a heuristic for when it's more profitable than exploiting the unreachable gaps.

I think there is probably a way to make it such that we take advantage of your work.

Originally, before your algorithm runs the switch case ranges have naturally holes that if the default is unreachable are unreachable as well and can be used as bounds.
Basically your algorithm detects that the Default is unreachable and adds additional holes by removing the cases that point to the most common successor.
Now though you introduce an ambiguity. Some of the holes are actually unreachable (which are the original "holes" before your algorithm run) , but some other are not (which are the ones you introduced) , but we cannot differentiate between the two.

If we instead , before running your algorithm, we collect the ranges that are true unreachable gaps and use this information in the lowering algorithm to make the best assumptions between upper and lower bounds I think we can reach the optimum.

hans updated this revision to Diff 18334.Jan 16 2015, 10:46 PM

If we instead , before running your algorithm, we collect the ranges that are true unreachable gaps and use this information in the lowering algorithm to make the best assumptions between upper and lower bounds I think we can reach the optimum.

That sounds like a good idea. I've uploaded a patch that does this. It might need some polish, but please take a look and let me know if you think it's on the right track.

Yeah, that sounds like it!
This is exactly what I meant :)

hans updated this revision to Diff 18470.Jan 20 2015, 5:39 PM

Yeah, that sounds like it!
This is exactly what I meant :)

Great! I've tidied up the patch a little, and made sure to use signed integers for IntRange since we're treating the case values as signed in the rest of the code.

Please take a look when you have time.

kariddi accepted this revision.Jan 23 2015, 9:49 AM
kariddi edited edge metadata.

Hi Hans!
Sorry for the delay. Your patch is very good. Thank you!

This revision is now accepted and ready to land.Jan 23 2015, 9:49 AM
This revision was automatically updated to reflect the committed changes.