Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

NegativeArraySizeException during code gen compiling a large project #6547

Closed
scabug opened this issue Oct 20, 2012 · 28 comments
Closed

NegativeArraySizeException during code gen compiling a large project #6547

scabug opened this issue Oct 20, 2012 · 28 comments

Comments

@scabug
Copy link

scabug commented Oct 20, 2012

(actually RC1, but that's not an option in jira yet.)

The breeze-math code base crashes when compiling against 2.10.0-RC1.

(Branch here: https://github.com/dlwh/breeze/tree/scala-2.10.0RC1, sbt clean compile should do it.)

The error is:

java.lang.NegativeArraySizeException
        at scala.tools.asm.Frame.merge(Unknown Source)
        at scala.tools.asm.MethodWriter.visitMaxs(Unknown Source)
        at scala.tools.nsc.backend.jvm.GenASM$JPlainBuilder.genMethod(GenASM.scala:1633)
        at scala.tools.nsc.backend.jvm.GenASM$JPlainBuilder$$anonfun$genClass$5.apply(GenASM.scala:1466)
        at scala.tools.nsc.backend.jvm.GenASM$JPlainBuilder$$anonfun$genClass$5.apply(GenASM.scala:1466)
        at scala.collection.immutable.List.foreach(List.scala:309)
        at scala.tools.nsc.backend.jvm.GenASM$JPlainBuilder.genClass(GenASM.scala:1466)
        at scala.tools.nsc.backend.jvm.GenASM$AsmPhase.run(GenASM.scala:182)
        at scala.tools.nsc.Global$Run.compileUnitsInternal(Global.scala:1574)
        at scala.tools.nsc.Global$Run.compileUnits(Global.scala:1548)
        at scala.tools.nsc.Global$Run.compileSources(Global.scala:1544)
        at scala.tools.nsc.Global$Run.compile(Global.scala:1654)

It claims it's in the file math/src/main/scala/breeze/util/Terminal.scala, but that file compiles fine on its own in its own project. Also, significant changes to the file don't seem to matter.

NB, with specialization disabled breeze-math compiles fine. There are other miscellaneous compile errors if you get passed this project, but nothing that generates compiler stack traces.

@scabug
Copy link
Author

scabug commented Oct 20, 2012

Imported From: https://issues.scala-lang.org/browse/SI-6547?orig=1
Reporter: @dlwh
Assignee: @magarciaEPFL
Affected Versions: 2.10.0-M7

@scabug
Copy link
Author

scabug commented Oct 20, 2012

@paulp said:
Minimized. Has to be compiled with -optimise to crash.

trait ConfigurableDefault[@specialized V] {
  def fillArray(arr: Array[V], v: V) = (arr: Any) match {
    case x: Array[Int]  => null
    case x: Array[Long] => v.asInstanceOf[Long]
  }
}

@scabug
Copy link
Author

scabug commented Oct 20, 2012

@paulp said:
Regression from 2.9.2.

@scabug
Copy link
Author

scabug commented Oct 20, 2012

@retronym said:
As a workaround, you can use -target:jvm-1.6. The default, jvm-1.6-asm, is a new implementation of the code generation, based on the ASM bytecode framework.

@scabug
Copy link
Author

scabug commented Oct 20, 2012

@dlwh said:
I have no idea how you figured that out so fast, Paul... I am in awe.

@scabug
Copy link
Author

scabug commented Oct 20, 2012

@retronym said:
Although, with specialization enabled, that leads you into the jaws of the next bug.

[warn] Class breeze.storage.Storage$mcD$sp not found - continuing with a stub.
[error] error while loading OpenAddressHashArray$mcD$sp, class file '/Users/jason/code/breeze/math/target/scala-2.10/classes/breeze/collection/mutable/OpenAddressHashArray$mcD$sp.class' is broken
[error] (class java.lang.NullPointerException/)
[warn] 153 warnings found
[error] one error found
[debug] Compilation failed (CompilerInterface)
[error] (breeze-math/compile:compile) Compilation failed

@scabug
Copy link
Author

scabug commented Oct 20, 2012

@paulp said:
Let's just say I haven't skipped bug-isolating practice in a while.

@scabug
Copy link
Author

scabug commented Oct 20, 2012

@retronym said (edited on Oct 20, 2012 7:18:04 AM UTC):
Incidentally, there are a few interesting warnings logged under -Ydebug.

ticket/6547 ~/code/scala ./build/quick/bin/scalac -Dfile.encoding=UTF-8 -Ylog:jvm -Ydebug test/files/run/t6547.scala
[running phase parser on t6547.scala]
[running phase namer on t6547.scala]
[running phase packageobjects on t6547.scala]
[running phase typer on t6547.scala]
warning: Checkability checker says 'Uncheckable', but uncheckable type cannot be found:
Checking checkability of (x: scala.this.Any) against pattern scala.this.Array[scala.this.Int]
[P1] false  X <: P             // scala.this.Any  <: scala.this.Array[scala.this.Int]
[P2] false  x ∉ P              // (x ∈ scala.this.Any) ⇒ (x ∉ scala.this.Array[scala.this.Int])
[P3] false  XR <: P            // scala.this.Array[T] <: scala.this.Array[scala.this.Int]
[P4] true   None of the above  // !(P1 || P2 || P3)
warning: Checkability checker says 'Uncheckable', but uncheckable type cannot be found:
Checking checkability of (x: scala.this.Any) against pattern scala.this.Array[scala.this.Long]
[P1] false  X <: P             // scala.this.Any  <: scala.this.Array[scala.this.Long]
[P2] false  x ∉ P              // (x ∈ scala.this.Any) ⇒ (x ∉ scala.this.Array[scala.this.Long])
[P3] false  XR <: P            // scala.this.Array[T] <: scala.this.Array[scala.this.Long]
[P4] true   None of the above  // !(P1 || P2 || P3)
...
[running phase specialize on t6547.scala]
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
warning: issue error: not found: type T0
[running phase explicitouter on t6547.scala]

@scabug
Copy link
Author

scabug commented Oct 20, 2012

@paulp said:
Noise, unfortunately.

@scabug
Copy link
Author

scabug commented Oct 20, 2012

@magarciaEPFL said:
To recap, -optimise comprises

  -Yinline -Yinline-handlers -Yclosure-elim -Ydead-code

Leaving out -Yclosure-elim keeps both GenASM and GenJVM happy.

Let's compare the bytecode emitted with and without "closelim", and all other optimization phases on.

(BTW, the ASM crash results from computing stack-map frames to emit 1.6 classfiles, that's skipped with -target:1.5-asm but then one also skips noticing non-wellformed bytecode).

The ASM crash occurs for:

  class:  ConfigurableDefault$mcZ$sp$class
  method: fillArray$mcZ$sp

The problematic snippet is "v.asInstanceOf[Long]". In both cases below the method signature is:

    public static java.lang.Object fillArray$mcZ$sp(ConfigurableDefault$mcZ$sp, boolean[], boolean);

ie local 1 is a boolean[] and local 2 a boolean.

Without "closelim" it looks like:

   25:	iload_2
   26:	invokestatic	#22; //Method scala/runtime/BoxesRunTime.boxToBoolean:(Z)Ljava/lang/Boolean;
   29:	invokestatic	#26; //Method scala/runtime/BoxesRunTime.unboxToLong:(Ljava/lang/Object;)J
   32:	invokestatic	#30; //Method scala/runtime/BoxesRunTime.boxToLong:(J)Ljava/lang/Long;
   35:	astore	6
   37:	aload	6
   39:	areturn

With "closelim" it looks like:

   19:	iload_2
   20:	invokestatic	#22; //Method scala/runtime/BoxesRunTime.boxToLong:(J)Ljava/lang/Long;
   23:	astore_3
   24:	aload_3
   25:	areturn

The last snippet is problematic because a iload_2 pushes a boolean and that's no good input for boxToLong which expects a long.

@scabug
Copy link
Author

scabug commented Oct 20, 2012

@magarciaEPFL said:
Regarding specialization.

One reason -no-specialization avoids the crash under -target:jvm-1.6 (which also runs GenASM) is that
ConfigurableDefault$mcZ$sp$class is not emitted, but also because the method signature in ConfigurableDefault$class

public static java.lang.Object fillArray(ConfigurableDefault, java.lang.Object, java.lang.Object);

plus the snippet

   19:	aload_2
   20:	invokestatic	#16; //Method scala/runtime/BoxesRunTime.unboxToLong:(Ljava/lang/Object;)J
   23:	invokestatic	#20; //Method scala/runtime/BoxesRunTime.boxToLong:(J)Ljava/lang/Long;
   26:	astore_3
   27:	aload_3
   28:	areturn

are accepted by the verifier.

When specialized to something other than Long, the case body for "case x: Array[Long]" is unreachable, yet GenASM attempts to compute stack-map frames for it (that in general is not possible, although the 1.6 verifier always insists on getting stack-map frames, even for unreachable code, see http://asm.ow2.org/doc/developer-guide.html#deadcode ).

In detail (when specialized to something other than Long) the case body for "case x: Array[Long]" will never be reached by fall-through from the code below (ie the conditional branch is always taken, in fact we can determine statically that an array of something-other-than-long is not an instance of array of long):

   17:	aload	1
   19:	instanceof	#16; //class "[J"
   22:	ifeq	40

The combination

-Yinline -Yinline-handlers -Ydead-code -target:1.6

(ie specialization on) might pass the verifier, but the code described above is unreachable all the same. With "closelim" it's additionally non-well-formed.

@scabug
Copy link
Author

scabug commented Oct 20, 2012

@paulp said:
"When specialized to something other than Long, the case body for "case x: Array[Long]" is unreachable"

We only know this by applying information the compiler does not have. I don't see how asm can know it either. The match is this:

(unknown: Any) match { case _: Array[Int] => ; case _: Array[Long] => }

You can't say statically whether those cases will match.

Here is a version without Arrays, to further illuminate the problem.

trait C[@specialized(Boolean) V] {
  def f(v: V) = (null: Any) match {
    case _: Int  =>
    case _: Long => v.asInstanceOf[Long]
  }
}

It looks like erasure will be the winner here. Man, the boxing code really sucks the air out of the room.

@scabug
Copy link
Author

scabug commented Oct 20, 2012

@magarciaEPFL said:
That's right, in the general "boxed" case ie

public static java.lang.Object fillArray(ConfigurableDefault, java.lang.Object, java.lang.Object);

it can't be determined statically that "after unboxing the 2nd arg, the element type of that array matches the third arg's unboxed type".

I was thinking about the specialization I was examining,

public static java.lang.Object fillArray$mcZ$sp(ConfigurableDefault$mcZ$sp, boolean[], boolean);

for which a bytecode-level type-flow analysis (detailed enough to track array component and element types) could be used to rule out success for:

instanceof	#16; //class "[J"

Anyway, that was a comment "just for completeness". Fixing the bug most likely involves patching ClosureElim some more :)

@scabug
Copy link
Author

scabug commented Oct 20, 2012

@retronym said (edited on Oct 20, 2012 11:02:31 AM UTC):
One more curiosity. Remove any of the options and it arrives at the originally reported error.

ticket/6547 ~/code/scala ./build/quick/bin/scalac -Ydead-code -Xprint:closelim -Ydebug test/files/run/t6547.scala

[running phase dce on t6547.scala]
in: 11 -> IState(, )
1 -> IState(, )
2 -> IState((value x1,1,1), )
6 -> IState(, )
10 -> IState(, )
3 -> IState(, )
7 -> IState(, )
out: 11 -> IState(, )
1 -> IState((value x1,1,1), )
2 -> IState((value x1,1,1), )
6 -> IState(, )
10 -> IState(, )
3 -> IState(, )
7 -> IState(, )
java.util.NoSuchElementException: key not found: 5
	at scala.collection.MapLike$class.default(MapLike.scala:228)
	at scala.collection.AbstractMap.default(Map.scala:58)
	at scala.collection.mutable.HashMap.apply(HashMap.scala:64)
	at scala.tools.nsc.backend.icode.analysis.DataFlowAnalysis$$anonfun$forwardAnalysis$1$$anonfun$1.apply(DataFlowAnalysis.scala:69)
	at scala.tools.nsc.backend.icode.analysis.DataFlowAnalysis$$anonfun$forwardAnalysis$1$$anonfun$1.apply(DataFlowAnalysis.scala:69)
	at scala.collection.TraversableLike$$anonfun$map$1.apply(TraversableLike.scala:244)
	at scala.collection.TraversableLike$$anonfun$map$1.apply(TraversableLike.scala:244)
	at scala.collection.immutable.List.foreach(List.scala:309)
	at scala.collection.TraversableLike$class.map(TraversableLike.scala:244)
	at scala.collection.AbstractTraversable.map(Traversable.scala:105)
	at scala.tools.nsc.backend.icode.analysis.DataFlowAnalysis$$anonfun$forwardAnalysis$1.apply(DataFlowAnalysis.scala:69)
	at scala.tools.nsc.backend.icode.analysis.DataFlowAnalysis$$anonfun$forwardAnalysis$1.apply(DataFlowAnalysis.scala:68)
	at scala.collection.immutable.List.foreach(List.scala:309)
	at scala.tools.nsc.backend.icode.analysis.DataFlowAnalysis$class.forwardAnalysis(DataFlowAnalysis.scala:68)
	at scala.tools.nsc.backend.icode.analysis.ReachingDefinitions$ReachingDefinitionsAnalysis.forwardAnalysis(ReachingDefinitions.scala:62)
	at scala.tools.nsc.backend.icode.analysis.ReachingDefinitions$ReachingDefinitionsAnalysis.run(ReachingDefinitions.scala:143)
	at scala.tools.nsc.backend.opt.DeadCodeElimination$DeadCode.collectRDef(DeadCodeElimination.scala:99)
	at scala.tools.nsc.backend.opt.DeadCodeElimination$DeadCode.dieCodeDie(DeadCodeElimination.scala:82)

@scabug
Copy link
Author

scabug commented Oct 20, 2012

@paulp said:
Oh wonderful. That's all kinds of trouble. You mean remove any of the options and it compiles, right? You have three options but none of them is an optimizer option. This would appear to implicate symbol initialization during specialization. I hate it when printing something changes the behavior, we need to put a stop to that.

@scabug
Copy link
Author

scabug commented Oct 20, 2012

@paulp said:
I see now -Ydead-code is the dead code elimination option, I confused it with another.

@scabug
Copy link
Author

scabug commented Oct 20, 2012

@retronym said (edited on Oct 20, 2012 11:16:14 AM UTC):
If you start with: -Ydead-code -Xprint:closelim -Ydebug -target:jvm-1.6 test/files/run/t6547.scala, you can remove any of the first three options to get things compiling. Alternatively, add -no-specialization.

@scabug
Copy link
Author

scabug commented Oct 20, 2012

@paulp said:
Nice. -Xprint:all, compiles; -Ylog:all, compiles; -Xprint:clos, crashes.

@scabug
Copy link
Author

scabug commented Oct 20, 2012

@paulp said:
Do you guys with your fancy ides have a way to say "show me the diff of the internal program state between -Xprint:all and -Xprint:clos"? Some kind of deterministic ascii memory dump which I could diff, I think if I had that it'd be short work from there. Or I could go build that yak from individual molecules.

@scabug
Copy link
Author

scabug commented Oct 20, 2012

@paulp said:
Well lookie there. Is it a trait? It is a class? Roll the dice!

<         17587#class Annotation
---
>         17587#trait Annotation
5700c5988
<     58#trait Function1$mcDF$sp
---
>     58#class Function1$mcDF$sp
14937c15229
<       3024#class FractionalProxy
---
>       3024#trait FractionalProxy
16122c16414
<       3483#trait BufferedIterator
---
>       3483#class BufferedIterator

@scabug
Copy link
Author

scabug commented Oct 25, 2012

@adriaanm said:
Miguel, "As a workaround, you can use -target:jvm-1.6." indicates it's at least related to the genasm back-end.

@scabug
Copy link
Author

scabug commented Oct 25, 2012

@magarciaEPFL said:
I'll take a deeper look at why ClosureElim elides this:

   26:	invokestatic	#22; //Method scala/runtime/BoxesRunTime.boxToBoolean:(Z)Ljava/lang/Boolean;
   29:	invokestatic	#26; //Method scala/runtime/BoxesRunTime.unboxToLong:(Ljava/lang/Object;)J

from the snippet in [#comment-60509] . That's the least risky fix I can think of.

@scabug
Copy link
Author

scabug commented Oct 29, 2012

@magarciaEPFL said:
scala/scala#1533

@scabug
Copy link
Author

scabug commented Oct 29, 2012

@magarciaEPFL said:
Apparently duplicate of #6248

@scabug
Copy link
Author

scabug commented Oct 29, 2012

@magarciaEPFL said:
Pull request closed by @gkossakowski so the fix won't show up in 2.10.

@scabug
Copy link
Author

scabug commented Oct 29, 2012

@adriaanm said (edited on Oct 29, 2012 9:49:21 PM UTC):
"won't show up in 2.10_.0_" -- it should go into 2.10.1, the RC1 of which is planned for Feb 11

@scabug
Copy link
Author

scabug commented Dec 2, 2012

@retronym said:
2.10.x PR: scala/scala#1692

@scabug
Copy link
Author

scabug commented Dec 10, 2012

@adriaanm said:
scala/scala#1692

@scabug scabug closed this as completed Dec 10, 2012
@scabug scabug added the critical label Apr 7, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant