Page MenuHomePhabricator

Add early out to O(n^2) switch analysis in switch-to-select conversion
ClosedPublic

Authored by AndrewScheidecker on Dec 6 2017, 5:05 AM.

Details

Summary

This adds an early out to the switch->select conversion analysis as soon as we've seen more than two unique results or cases. The conversion ultimately aborts in this case, but currently only does so after fully analyzing the switch, which takes O(NumCases^2) time if the switch is in a form that doesn't early out for other reasons.

In my WebAssembly VM that uses LLVM to generate machine code, I was running into this on a test case with a large, but simple, switch from the WebAssembly reference interpreter test suite: https://github.com/WebAssembly/spec/blob/master/test/core/br_table.wast#L110

To find the bottleneck, I increased the number of cases in the switch statement further, which caused it to spend 10 seconds in LLVM optimization passes. Adding this early out reduced that to tens of milliseconds.

Diff Detail

Repository
rL LLVM

Event Timeline

Include full context in diff, as suggested on IRC

kariddi requested changes to this revision.Dec 11 2017, 9:29 AM
kariddi added a reviewer: kariddi.
kariddi added a subscriber: kariddi.

Hi Andrew, your change modifies the semantics of the function, in the sense that it becomes specialized into just collecting the data to perform "ConvertTwoCaseSwitch()" and it will not be possible to use it for other potential optimization that require the same data.

Maybe we could add configurable cut-off points instead (in the form of default parameters) that default to what "ConvertTwoCaseSwitch()" requires for now (that would be 2 and 2)

Otherwise if we think that this function is not gonna be useful for any other optimization we could rename it and maybe it could even be simplified and the comment before it then should be updated to clarify the new use of it.

I added parameters to the InitializeUniqueCases function to control the early-outs, so it could theoretically be called by another transform that can support more complex switch statements.

kariddi accepted this revision.Jan 4 2018, 7:13 PM

LGTM

This revision is now accepted and ready to land.Jan 4 2018, 7:13 PM

I don't have commit access. Can somebody please commit this for me?

kariddi closed this revision.Jan 10 2018, 6:08 PM

Pushed as r322248

I forgot to mention that the patch was made by you in the original commit, so I made an extra commit (r322249) that mentions that the patch is actually yours :(

Sorry about that.