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

UnCurry forgets to liftTree, causing java.lang.VerifyError down the road #6863

Closed
scabug opened this issue Dec 22, 2012 · 18 comments
Closed
Milestone

Comments

@scabug
Copy link

scabug commented Dec 22, 2012

I'm trying to use a modified version of https://github.com/romix/akka-kryo-serialization with Scala 2.10.0-RC5. It compiles fine (without -optimise, with the flag it crashes, but that's a different issue), but then at class load-time I get the following error:

Could not run test org.hyflow.KryoTest: java.lang.VerifyError: (class: com/romix/scala/serialization/kryo/ScalaSetSerializer, method: create signature: (Lcom/esotericsoftware/kryo/Kryo;Lcom/esotericsoftware/kryo/io/Input;Ljava/lang/Class; )Lscala/collection/Set; ) Inconsistent stack height 1 != 3

Even Soot refuses to load the class properly, and gives the following:

Considering 111: invokenonvirtual[111]
Exception in thread "main" java.lang.RuntimeException: TypeStack merging failed; unequal stack lengths: 1 and 3
	at soot.coffi.TypeStack.merge(TypeStack.java:137)
	at soot.coffi.CFG.jimplify(CFG.java:1196)
	at soot.coffi.CFG.jimplify(CFG.java:955)
	...

The code that causes the problem appears to be at the end of this block, as the three branches are collected into the final result (line labeled 111 in the 2.10 bytecode file):

var coll: Map[Any, Any] = 
if(classOf[SortedMap[_,_]].isAssignableFrom(typ)) {
// Read ordering and set it for this collection 
implicit val mapOrdering = kryo.readClassAndObject(input).asInstanceOf[scala.math.Ordering[Any]]
	try typ.getDeclaredConstructor(classOf[scala.math.Ordering[_]]).newInstance(mapOrdering).asInstanceOf[Map[Any,Any]].empty 
	catch { case _ => kryo.newInstance(typ).asInstanceOf[Map[Any,Any]].empty }
} else {
	kryo.newInstance(typ).asInstanceOf[Map[Any,Any]].empty
}

This code worked on 2.9.1, and it appears the generated bytecode is indeed different. I've attached the source code excerpt and disassembled bytecode for 2.9.1 and 2.10.0-RC5, and highlighted the line with the problem in the 2.10 bytecode.

@scabug
Copy link
Author

scabug commented Dec 22, 2012

Imported From: https://issues.scala-lang.org/browse/SI-6863?orig=1
Reporter: Alex Turcu (talex)
Assignee: @JamesIry
Affected Versions: 2.10.0-RC5, 2.10.0, 2.11.0
Attachments:

@scabug
Copy link
Author

scabug commented Dec 23, 2012

Alex Turcu (talex) said:
The minimal test case that generates the error seems to be:

def test(kryo: Kryo, input:Input, typ: Class[Map[_,_]]): Map[_,_] = {
	val len = 7
	var coll: Map[Any, Any] = {
		try { 
			val someVar = null;
			Map[Any,Any]().empty 
		} catch { 
			case _ => Map[Any,Any]().empty 
		}
	}
	0 until len foreach {_ => coll += Tuple2( 0, 0) }
	coll
}

Looks similar to #5380 , and seems to be related to the wrapping of "coll" into a scala.runtime.ObjectRef . someVar is required but probably just prevents some other optimization.

@scabug
Copy link
Author

scabug commented Dec 23, 2012

@magarciaEPFL said:
The snippet in [#comment-61645] doesn't cause a VerifyError as of v2.10.0 (after removing the method params to make the snippet self-contained). Some of the differences with the snippet in the Description must explain why the VerifyError appears there. It would be great if you could minimize into a self-contained program.

@scabug
Copy link
Author

scabug commented Dec 23, 2012

Alex Turcu (talex) said:
How about this?

object Main extends App {
	def test(): Map[_,_] = {
		//val typ = classOf[Map[Int,Int]]
		var coll: Map[Int, Int] = {
			val key = 4
			try {
				Map[Int,Int](key -> 5).empty 
			} catch { case _ => Map[Int,Int](2 -> 3).empty }
		}
		0 until 7 foreach {_ => coll += Tuple2( 0, 0) }
		coll
	}
}

It fails for me using 2.10.0-RC5 and:

#!/bin/bash
rm ./*.class
scalac  bug.scala
scala -classpath . Main

@scabug
Copy link
Author

scabug commented Dec 23, 2012

@magarciaEPFL said:
Further minimization:

object Test {

  def main(args: Array[String]) {

    var coll = {
      val key = 4
      try   { null }
      catch { case _ => null }
    }

    { () => coll } // the purpose of this is making `coll` an ObjectRef

  }
}

After compiling with v2.10.0 and master we get:

java.lang.VerifyError: (class: Test$, method: main signature: ([Ljava/lang/String;)V) Inconsistent stack height 1 != 3

@scabug
Copy link
Author

scabug commented Dec 23, 2012

@magarciaEPFL said:
As a sidenote, removing val key = 4 also removes the VerifyError: the emitted bytecode contains two code sections, one for the try-clause and another for the catch-clause (both doing the same, ie building an ObjectRef with null as payload). In this case, there's no VerifyError because on control-flow merge those stacks have same height.

@scabug
Copy link
Author

scabug commented Dec 23, 2012

@magarciaEPFL said:
Back to the example in [#comment-61651]. Here's the javap:

public void main(java.lang.String[]);
  Code:
   0:   new     #16; //class scala/runtime/ObjectRef
   3:   dup
   4:   iconst_4
   5:   istore_3
   6:   aconst_null
   7:   goto    12
   10:  pop
   11:  aconst_null
   12:  pop
   13:  aconst_null
   14:  invokespecial   #19; //Method scala/runtime/ObjectRef."<init>":(Ljava/lang/Object;)V
   17:  astore_2
   18:  new     #21; //class Test$$anonfun$main$1
   21:  dup
   22:  aload_2
   23:  invokespecial   #24; //Method Test$$anonfun$main$1."<init>":(Lscala/runtime/ObjectRef;)V
   26:  pop
   27:  return
  Exception table:
   from   to  target type
     6    10    10   any

Two blocks (B1 and B2) get merged at instruction 12. B1 comprises instructions [0 to 7] and B2 (an exception handler) [10 to 11].

On exit from B1, the stack is [ObjectRef ObjectRef null]
On exit from B2, the stack is [null]
Therefore the VerifyError Inconsistent stack height 1 != 3

Usually liftTree() in UnCurry avoids the situation above, by creating a local method for the try expression:

 *  - convert try-catch expressions in contexts where there might be values on the stack to
 *      a local method and a call to it (since an exception empties the evaluation stack):
 *
 *      meth(x_1,..., try { x_i } catch { ..}, .. x_b0) ==>
 *        {
 *          def liftedTry$1 = try { x_i } catch { .. }
 *          meth(x_1, .., liftedTry$1(), .. )
 *        }

That would have saved the day.

@scabug
Copy link
Author

scabug commented Jan 8, 2013

@JamesIry said (edited on Jan 8, 2013 6:19:35 PM UTC):
Appears to be related to scala/scala@b2f3fb2

@scabug
Copy link
Author

scabug commented Jan 8, 2013

@JamesIry said:
Here's the story.

Remove some redundant code
scala/scala@b2f3fb2

Remove the code that it was redundant to, so now it
can't work
scala/scala@beb8751

Then destroy the evidence that it ever existed
scala/scala@ffc2389

Moral of the story: tests are good.

@scabug
Copy link
Author

scabug commented Jan 10, 2013

@JamesIry said:
scala/scala#1870

@scabug
Copy link
Author

scabug commented Jan 18, 2013

@magarciaEPFL said:
There is a (way) simpler solution. The bug results from UnCurry not anticipating that the location of a try-catch will become non-statement after LambdaLift. That's because LambdaLift turns a statement-position try-catch into non-statement-position (by giving the enclosing RHS as argument to new OBjectRef(initialValue). The only way to lower such New() is:

NEW ObjectRef
DUP
... instructions loading initialValue
INVOKESPECIAL scala.runtime.ObjectRef.<init>(initialValue)

Alternatively, if the above were lowered into:

... instructions loading initialValue
INVOKESTATIC scala.runtime.ObjectRef.create(initialValue)

then UnCurry wouldn't need to anticipate anything (no code resurrection, no code duplication, more compact code). For bonus points, it would be great to have:

INVOKESTATIC scala.runtime.ObjectRef.zero()

which returns an ObjectRef initialized to null. Similarly for the zeroes of IntRef and others.

About binary compatibility, what if ObjectRef et al. had been designed from the start with the above in mind? It's never too late.

@scabug
Copy link
Author

scabug commented Jan 18, 2013

@JamesIry said:
I totally agree that that's a cleaner solution. But it would have to wait until 2.11 when we can break forward binary compatibility by adding the factory methods to ObjectRef.

@scabug
Copy link
Author

scabug commented Jan 18, 2013

@JamesIry said (edited on Jan 18, 2013 4:49:17 PM UTC):
An alternative that doesn't break binary compatibility is

var x = try{...}catch{...}

transforms to

val temp$ = try {...}catch{...}
var x = temp$

which, when x is captured, turns turns into

... instructions loading initialValue
STORE temp$
NEW ObjectRef
DUP
LOAD temp$
INVOKESPECIAL scala.runtime.ObjectRef.<init>(initialValue)

It wastes a variable slot in cases when var is not captured, though (unless we're smarter about optimizing away variables than I think we are), so we'd want to replace it with the cleaner static factory version in 2.11.

@scabug
Copy link
Author

scabug commented Jan 18, 2013

@adriaanm said:
Based on a meatspace discussion with James, I agree we should pursue Miguel's factory approach for 2.11 and try to implement James's extra-variable fix for 2.10.1-RC1.

@scabug
Copy link
Author

scabug commented Jan 18, 2013

@magarciaEPFL said:
The extra-variable is actually lightweight, and apparently LambdaLift isn't too late to apply it (I'm guessing here). Perhaps detecting new Foo(try{...}catch{...}) during LambdaLift is also amenable to a local rewriting

var temp = try {} catch {}
new Foo(temp)

I agree getting this fixed first in a binary-compatible way is the best for now.

@scabug
Copy link
Author

scabug commented Jan 19, 2013

@JamesIry said:
It turns out to be even simpler than all this discussion. So simple I feel quite stupid for not seeing it the first time through. The original problem was that var x = try {...} catch {...} works fine but that var x = { blah; try{...} catch{...} does not. Well, in lambda lift there's a transformation that turns var x = try {block} catch {case blah => catchBlock} into var x = try {new Ref(block)} catch {case blah => new Ref(catchBlock)}. But that didn't catch the case where x was initialized from a block. The fix is easy. Just look at a block used for captured var assignment and do the same rewrite on the block's result expression. Do it recursively since we could have var x = {blah {blurg { try...}}.

@scabug
Copy link
Author

scabug commented Jan 25, 2013

@JamesIry said:
The previous comment turns out to be, um, wrong. Ish. We need to deal with var x = if(blah) try/catch and var x = blah match {case whatever => try/catch}. Etc. The final pull request does the "val temp = whatever; new *Ref(temp)" transformation as a last ditch approach when it can't figure things out, but try/catch, if/else, match/case, and block expressions all get a more direct translation moving the new *Ref construction to "leaf" expressions that don't have try/catch.

The pull is: scala/scala#1927

A proposed alternative for 2.11+ is here: http://james-iry.blogspot.com/2013/01/scala-trycatch-lifting-proposal.html

@scabug scabug closed this as completed Jan 28, 2013
@scabug
Copy link
Author

scabug commented Jan 28, 2013

@magarciaEPFL said:
One of the sub-problems when try-catch's are left in expression positions is a post-CleanUp step to guarantee empty-stack-on-try-entry. Other backends (in particular MSIL) also stand to benefit.

A proposal (in the form of pseudocode) for that transformation can be found at https://groups.google.com/d/msg/scala-internals/VkEL7wOVQpE/aSiNnF3ym-cJ

@scabug scabug added this to the 2.10.1 milestone 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