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

[AndrewScheidecker]

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.

[AndrewScheidecker]

Include full context in diff, as suggested on IRC

[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.

[AndrewScheidecker]

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]

LGTM

[AndrewScheidecker]

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

[kariddi]

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.

lib/Transforms/Utils/SimplifyCFG.cpp

if (!GetCaseResults(SI, CaseVal, I.getCaseSuccessor(), &CommonDest, Results,
                         DL, TTI))
       return false;
 
     // Only one value per case is permitted
     if (Results.size() > 1)
       return false;
     MapCaseToResult(CaseVal, UniqueResults, Results.begin()->second);
 
+    // No more than two unique results can be selected between.
+    if (UniqueResults.size() > 2)
+      return false;
+
+    // No result may have more than one case that selects it.
+    for(const auto &RI : UniqueResults)
+      if (RI.second.size() > 1)
+        return false;
+
     // Check the PHI consistency.
     if (!PHI)
       PHI = Results[0].first;
     else if (PHI != Results[0].first)
       return false;
   }
   // Find the default result value.
   SmallVector<std::pair<PHINode *, Constant *>, 1> DefaultResults;