Compiler performance regression in pattern matcher analysis

[scabug]

A large performance regression on scala 2.12.x in compiling https://github.com/martijnhoekstra/switchbench commit 6b48c3

(contains a large amount of synthesized code)

Compile time for 2.11.x 186 seconds, for 2.12.x ~ 1100 seconds after increasing stack size, and stackoverflow otherwise.

This is a very much not minimized test-case, though it's largely very repetitive. I hope I'll have the time to minimize.

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-10092?orig=1 Reporter: @martijnhoekstra Affected Versions: 2.12.0, 2.12.1 See #10057

[scabug]

@retronym said: Upcasting the scrutinees of the patterns disables pattern matcher analysis, which is the part that blows the stack and/or takes ages to compute:

diff --git a/src/main/scala/intswitch/PlainBenchmark1024.scala b/src/main/scala/intswitch/PlainBenchmark1024.scala
index 0e69923..33badb5 100644
--- a/src/main/scala/intswitch/PlainBenchmark1024.scala
+++ b/src/main/scala/intswitch/PlainBenchmark1024.scala
@@ -1091,5 +1091,5 @@ class PlainBenchmark1024 {

     def selectSelf(caze: Plain) = {
-      caze match {
+      (caze: Any) match {

         case NthSelector1(p) => bh.consume(p)
@@ -2129,5 +2129,5 @@ class PlainBenchmark1024 {

     def selectSelf(caze: Plain) = {
-      caze match {
+      (caze: Any) match {

         case NthSelector1(p) => bh.consume(p)

[scabug]

@retronym said: Minimized: https://gist.github.com/f865bae6271477425eda2b436352ddb8

test.scala compiles in 12s (although takes significant heap in the backend to eliminate dead code)

test2.scala blows the default stack in:

	at scala.tools.nsc.transform.patmat.Solving$Solver.findTseitinModelFor$(Solving.scala:471)
	at scala.tools.nsc.transform.patmat.PatternMatching$OptimizingMatchTranslator.findTseitinModelFor(PatternMatching.scala:89)
	at scala.tools.nsc.transform.patmat.Solving$Solver.findTseitinModelFor(Solving.scala:484)

With a larger enough stack, it compiles in 1m26s.

[scabug]

@retronym said (edited on Dec 5, 2016 10:21:47 PM UTC): Might be a duplicate of #10057, although this one seems to manifest in a compilation without exhaustiveness warnings, which is a little bit different from the other ticket.

[scabug]

@retronym said: I was trying a few things to optimize findTseitinModelFor (patch; https://gist.github.com/6ba30b3bbfd76715cfd1821f77c6075a), but we need to look at this in the broader context of the unreachable analysis, which appears to me to be quadratic in complexity wrt the number of cases in the match.

We have some (configurable) bailouts that disable analysis for large matches and/or large ADTs, but this test comes in under the limit.

[SethTisue]

both Scala 2.13.16 and Scala 3.6.3 compile test.scala on my machine in the 5–8 second range

for test2.scala, Scala 2 (~2 minutes) is still substantially slower than Scala 3 (~7 seconds)