Graal: Incorrect behaviour when compiling the Scala compiler

[vjovanov]

To reproduce:

git clone [email protected]:scala/scala.git
cd scala
sbt -java-home <path-to-graal-vm> compiler/compile

The failure is:

java.util.NoSuchElementException: key not found: method matchEnd7
    at scala.collection.MapOps.default(Map.scala:203)
    at scala.collection.MapOps.default$(Map.scala:202)
    at scala.collection.AbstractMap.default(Map.scala:318)
    at scala.collection.MapOps.apply(Map.scala:122)
    at scala.collection.MapOps.apply$(Map.scala:121)
    at scala.collection.AbstractMap.apply(Map.scala:318)

The method that misbehaves is probably

scala.tools.nsc.backend.jvm.BCodeIdiomatic$LabelDefsFinder.traverse

as changing it with println statements made the bug go away.
Big thanks to @lrytz for finding the bug and identifying the method that fails.

[dougxc]

I've struggling to reproduce:

dsimon@kruger-7 ~/g/scala> git show
commit 4ffaf3935388f389d4b9034b7c0957a473cc8e84 (HEAD -> 2.13.x, origin/HEAD, origin/2.13.x)
dsimon@kruger-7 ~/g/scala> sbt -java-home /Library/Java/JavaVirtualMachines/graalvm-1.0.0-rc1/Contents/Home compiler/compile
[info] Loading project definition from /Users/dsimon/github/scala/project/project
[info] Loading project definition from /Users/dsimon/github/scala/project
[info] Compiling 15 Scala sources to /Users/dsimon/github/scala/project/target/scala-2.10/sbt-0.13/classes...
[info] Resolving key references (10981 settings) ...
[info] *** Welcome to the sbt build definition for Scala! ***
[info] Check README.md for more information.
[info] Compiling 393 Scala sources and 119 Java sources to /Users/dsimon/github/scala/build/quick/classes/library...
[error] /Users/dsimon/github/scala/src/library/scala/collection/mutable/WeakHashMap.scala:36: overriding method mapFactory in trait Map of type => scala.collection.MapFactory[WeakHashMap.this.MapCC];
[error]   method mapFactory has incompatible type
[error]   override def mapFactory: MapFactory[WeakHashMap] = WeakHashMap
[error]                ^
[error] /Users/dsimon/github/scala/src/library/scala/collection/mutable/WeakHashMap.scala:36: type arguments [scala.collection.mutable.WeakHashMap] do not conform to class MapFactory's type parameter bounds [CC[A, B] <: scala.collection.Map[A,B] with scala.collection.MapLike[A,B,CC[A,B]]]
[error]   override def mapFactory: MapFactory[WeakHashMap] = WeakHashMap
[error]                            ^
[error] /Users/dsimon/github/scala/src/library/scala/collection/mutable/WeakHashMap.scala:46: overriding method newBuilder in class GenMapFactory of type [A, B]=> scala.collection.mutable.Builder[(A, B),scala.collection.mutable.WeakHashMap[A,B]];
[error]   method newBuilder needs `override' modifier
[error]   def newBuilder[K, V]: Builder[(K, V), WeakHashMap[K,V]] = new GrowableBuilder(WeakHashMap.empty[K, V])
[error]       ^
[error] /Users/dsimon/github/scala/src/library/scala/collection/mutable/WeakHashMap.scala:43: type arguments [scala.collection.mutable.WeakHashMap] do not conform to class MapFactory's type parameter bounds [CC[A, B] <: scala.collection.Map[A,B] with scala.collection.MapLike[A,B,CC[A,B]]]
[error] object WeakHashMap extends MapFactory[WeakHashMap] {
[error]                            ^
[error] four errors found
[error] (library/compile:compileIncremental) Compilation failed
[error] Total time: 31 s, completed May 17, 2018 4:21:07 PM

That looks like a different error right?

[lrytz]

That looks unexpected. Is it a fresh checkout / can you run git clean -dffx? MapLike is something from 2.12 land, should not show up/exist in 2.13.

[dougxc]

After running git clean -dffx, I can now reproduce - thanks.

[lrytz]

Once diagnosed or fixed, we'd be interested to hear what the issue was. Is the Scala compiler emitting exotic bytecode patterns?

For a long while, we had intermittent failures on CI that we could never nail down (https://github.com/scala/bug/issues/9264). That was on HotSpot. We could not reproduce the issue reliably. Maybe there is a small chance the the issue we're seeing here on Graal is related.

[dougxc]

@lrytz what kind of println statements make the problem go away? Adding -XX:CompileCommand=exclude,scala.tools.nsc.backend.jvm.BCodeIdiomatic\$LabelDefsFinder::traverse confirms your suspicion that the problem is in the compilation of scala.tools.nsc.backend.jvm.BCodeIdiomatic$LabelDefsFinder.traverse and I'm now trying to work out which Graal phase is causing the problem.

[dougxc]

@lrytz II know it's a big ask, but is there anyway you can boil this error down to a simple(r) reproducer?

[mukel]

Triggers only on graal-enterprise.
Disabling or crippling the inliner -Dgraal.ExpansionInertiaBaseValue=200 solves the problem; still the graphs are terribly huge.
/cc @axel22

[lrytz]

@dougxc to minimize the number of players in the game, you can run java directly without sbt, and use the scala compiler "as a library".

Download 2.13.0-M4 from https://downloads.lightbend.com/scala/2.13.0-M4/scala-2.13.0-M4.tgz

➜  scala13 git:(2.13.x) ✗ git checkout v2.13.0-M4
➜  scala13 git:(a002630512) ✗ find src/compiler -name '*.scala' > files
➜  scala13 git:(a002630512) ✗ S=/Users/luc/scala/scala-2.13.0-M4
➜  scala13 git:(a002630512) ✗ /Library/Java/JavaVirtualMachines/graalvm-1.0.0-rc1/Contents/Home/bin/java -Xmx1536m -Xms1536m -Xss5m -classpath $S/lib/scala-compiler.jar:$S/lib/scala-library.jar:$S/lib/scala-reflect.jar scala.tools.nsc.Main -cp $S/lib/scala-compiler.jar:$S/lib/scala-library.jar:$S/lib/scala-reflect.jar @files -d sandbox
java.util.NoSuchElementException: key not found: method matchEnd7
    at scala.collection.MapOps.default(Map.scala:203)
    at scala.collection.MapOps.default$(Map.scala:202)
    at scala.collection.AbstractMap.default(Map.scala:318)
    at scala.collection.MapOps.apply(Map.scala:122)
    at scala.collection.MapOps.apply$(Map.scala:121)
    at scala.collection.AbstractMap.apply(Map.scala:318)
    at scala.tools.nsc.backend.jvm.BCodeBodyBuilder$PlainBodyBuilder.genApply(BCodeBodyBuilder.scala:654)

I don't have a good idea how to minimize the issue further. Compiling fewer files will probably lead to different profiles and might not trigger the bug in Graal.

[mukel]

Narrowed it down to -Dgraal.OptimizeLoopAccesses=false which is one of the latest phases.

[mukel]

A fix ~is being~ was merged, will be out for RC2.
The culprit was one of the optimization phases that went rogue with the List implementation in Scala, specifically with the mutable var next trick. The pattern was exotic enough that we couldn't reproduce it in Java.

[lrytz]

Is the fix in one of the recent commits here https://github.com/oracle/graal/commits/master/compiler?

Could you share what the exotic bytecode pattern is? Mutable varialbes seem pretty common in Java 😃.

[dougxc]

The fix is in an enterprise extension so unfortunately it won't show up on GitHub. The problem (as I understand it) was that a node was hoisted outside a loop but one of its usages was not rewired correctly. In any case, the fix will be part of the next GraalVM release.

[mukel]

Until then you can disable the phase by passing -Dgraal.OptimizeLoopAccesses=false

Not a bytecode pattern; but a very particular "code pattern" that aligned with other very unlikely conditions to trigger the bug. scalac is exotic on it's own :wink:.

[dougxc]

Please re-open this issue if there's still a problem in the next GraalVM release (in the next few days).