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]

Abandoning so I can resubmit with llvm-commits as a subscriber

lib/Transforms/Utils/SimplifyCFG.cpp

       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;