Propsal for try/catch lifting

[James Iry]

I've posted a proposal for a different form of try/catch lifting in scalac http://james-iry.blogspot.com/2013/01/scala-trycatch-lifting-proposal.html . Leave comments here, there, or everywhere.

[Paul Phillips]

On Fri, Jan 25, 2013 at 10:10 AM, James Iry <jame...@typesafe.com> wrote:

I've posted a proposal for a different form of try/catch lifting in scalac http://james-iry.blogspot.com/2013/01/scala-trycatch-lifting-proposal.html . Leave comments here, there, or everywhere.

Do I understand correctly: rather than deal with non-empty stack matching, wish the problem into the cornfield by always having an empty stack? That is, move what would have been the stack into locals.

It seems like a reasonable thing to try/catch you later.

[James Iry]

Yes, although to clarify only force empty stack when we do try/catch. Otherwise we can continue to use the stack with impunity.

[martin odersky]

That's what Pizza did. But the details turned out to be a bit complex, and the transformed code was difficult to debug afterwards. That's why we changed the scheme to the one which we have now.  The silent boxing is indeed nasty, I agree with that.

Can we maybe offload the responsibility to keep an empty stack to the bytecode generator? It keeps track of stack maps anyway. So, whenever it hits a try with a non-empty stack it generates bytecodes to pop all stack entries into fresh variables, and then after the try code stashes all popped variables behind the result.

WDYT?

 - Martin

 

--
 
 

--
Martin Odersky
Prof., EPFL and Chairman, Typesafe
PSED, 1015 Lausanne, Switzerland
Tel. EPFL: +41 21 693 6863
Tel. Typesafe: +41 21 691 4967

[Miguel Garcia]

Here goes my attempt at this problem.

After Cleanup, whether via bytecode emitter or via nsc.transform.Transform, the algorithm to guarantee empty-stack-on-try-entry is mostly the same. Unlike conversion to three-address form the following achieves empty-stack-on-try-entry while minimizing extra temporary variables.

Usually a Transform visits children in order 1 to n. In our case instead n to 1 is needed, as can be seen more clearly for a Tree node standing for an n-ary operation (to recap, the bytecode instructions for that node push n values onto the operand stack, consume them, and may leave a value for the result on the stack). Before emitting as just suggested, we need to know what the highest argument a_i is that encloses a Try node, say a_m , so as to emit instead:

Block(
  val temp_1 = arg_1
  . . .
  val temp_m = arg_m
 
  Op(temp_1 ... temp_m , arg_(m+1) ... arg_n)
)

(In the notation above, the receiver of an instance-method is shown as a_1 , akin to bytecode)

Besides n-ary operations with n > 1, the other nodes of interest are:

  (a) New with one or more constructor arguments. The difference with n-ary op with n > 1 has to do with the way the code emitter lowers New:

        NEW C
        DUP
        . . . instructions loading ctor-args
        INVOKESPECIAL <init>

      ie the first ctor-arg already finds a non-empty stack, unlike for a unary-op.

  (b) Try

The candidate solution (pseudocode below) fills in details (e.g. what to do for non-op nodes like Block). It's formulated in terms of Transform, which should be fast enough because most transforms are the identity, and a lazy tree copier is our friend. The additional time this transform takes should be more than offset by reduced IntRefs etc resulting from dropping all code for liftTree from UnCurry.

As the example of n-ary ops shows, the status of the visitor changes upon a successor node being a Try (due to reverse visit order, we've already been there by the time the current node is visited). We represent this "status" as boolean field of our Transform subclass.

The cases and corresponding actions for the current node are:


case Op(a_1 ... a_n) with n > 1
   | New(...) with one ore more args
=>
   val saved   = status
   status      = false
   var highest = -1 // position of the last argument for which a temp var is needed
                    // (for all args coming before a temp var will be needed too)

   for i <- n to 1 {

     val xformed_i = transform(arg_i) // visiting this successor node may set the status field

     if status && (i > highest) {
       highest = i
     }
   
   }

   if status {
     assert highest != -1
    
     // now comes the transformed node to return

     Block(
       ValDef(temp_1, xformed_1)
       . . .
       ValDef(temp_highest, xformed_highest)

       Op /* resp. New */ (temp_1 ... temp_highest , xformed_(highest+1) ... xformed_n )
     )

   } else {
      super.transform(tree) // identity transform (to recap, with children visited in reverse order)
   }

   status |= saved


case Try
=> status = true // sticky status, gets propagated to all previous nodes (ie those visited later in our reverse visit order)


case _
=> super.transform


Looks like that's it. Well almost (paragraph below). Only the cases above? What about Block(stmt_1 ... stmt_n expr) ? The identity transform should be enough: consider a Try enclosed in some stmt_i. Upon being visited, status becomes true, but all stmts before stmt_i are not touched. That's fine: their values will be cleared from the operand stack by the time a next stmt starts. Same goes for expr. By setting status however, code preceding the Block in question is requested to leave an empty stack.

Why "almost"? The above tells us in advance what temporary vars to create and how to drain the stack, assuming there's nothing yet on the stack. An exception handler however has on entry an exception on the stack. But that can be stored (usually is) into a temp var anyway. Thus the Try case above needs to take care of that before setting status = true.

As with any other candidate solution, the above assumes the pipeline from UnCurry till CleanUp can handle (in practice) Try nodes in any expression position (so far, they showed up only in statement poisition, or that was the idea, thanks to UnCurry's liftTree)


Miguel
http://lampwww.epfl.ch/~magarcia/ScalaCompilerCornerReloaded/

[James Iry]

I considered doing it during code gen. As you say, code gen already needs to have a deep understanding of the stack.

However, while the direct approach of finding a try/catch, popping the stack into variables, then pushing after the try/catch would work it would lead to a fair amount of extra noise for foo(bar(), try/catch, baz(), try/catch). So even if we do it in code gen I think we'd still want to do the same algorithm of finding the the last in a series of args and stuffing everything prior into variables (recursively)

Things to consider: right now we have tree -> icode -> byte code. Miguel is working on tree -> byte code. Someday somebody may revive the MSIL backend, or create a Dalvik backend, or whatever. AFAIK they'll all have the same problem. So doing the transform on trees before going to code gen means everybody doesn't have to independently invent this solution. Or, more likely, independently screw it up :-)

Independently of whether it's a tree-> tree transform or done during code gen, there is a legitimate question of how much harder the resulting byte code will be to understand. But, except for verify errors, I usually prefer to look for problems in trees before I try to look at byte code. And verify errors are just going to be tough without a minimized test case pretty much no matter what the code looks like.

--
 
 

[iulian dragos]

Hi James,

On Sat, Jan 26, 2013 at 11:54 PM, James Iry <jame...@typesafe.com> wrote:

I considered doing it during code gen. As you say, code gen already needs to have a deep understanding of the stack.

However, while the direct approach of finding a try/catch, popping the stack into variables, then pushing after the try/catch would work it would lead to a fair amount of extra noise for foo(bar(), try/catch, baz(), try/catch). So even if we do it in code gen I think we'd still want to do the same algorithm of finding the the last in a series of args and stuffing everything prior into variables (recursively)

Things to consider: right now we have tree -> icode -> byte code. Miguel is working on tree -> byte code. Someday somebody may revive the MSIL backend, or create a Dalvik backend, or whatever. AFAIK they'll all have the same problem. So doing the transform on trees before going to code gen means everybody doesn't have to independently invent this solution. Or, more likely, independently screw it up :-)

I don't see any issues with your proposal, and I agree that it might improve inlining decisions (though it's not clear to me how to remove the safety checks in the backend, assuming some inlining decisions are still taken at that point). At the time we chose this scheme over the other because it was 1) on trees and 2) simple to implement.

It's a tough decision if the additional complexity of implementation, plus the additional 'noise' in the debugger (though there are precedents, like pattern matching and default arguments) is worth the gains from removing an indirection. Maybe the names-arguments transformation can be reused, and then there's no additional complexity.

 

Independently of whether it's a tree-> tree transform or done during code gen, there is a legitimate question of how much harder the resulting byte code will be to understand. But, except for verify errors, I usually prefer to look for problems in trees before I try to look at byte code. And verify errors are just going to be tough without a minimized test case pretty much no matter what the code looks like.

On Jan 25, 2013, at 11:49 PM, martin odersky <martin....@epfl.ch> wrote:

On Fri, Jan 25, 2013 at 7:33 PM, James Iry <jame...@typesafe.com> wrote:

That's what Pizza did. But the details turned out to be a bit complex, and the transformed code was difficult to debug afterwards. That's why we changed the scheme to the one which we have now.  The silent boxing is indeed nasty, I agree with that.

Can we maybe offload the responsibility to keep an empty stack to the bytecode generator? It keeps track of stack maps anyway. So, whenever it hits a try with a non-empty stack it generates bytecodes to pop all stack entries into fresh variables, and then after the try code stashes all popped variables behind the result.

WDYT?

 - Martin

 

--
 
 

--
Martin Odersky
Prof., EPFL and Chairman, Typesafe
PSED, 1015 Lausanne, Switzerland
Tel. EPFL: +41 21 693 6863
Tel. Typesafe: +41 21 691 4967

--
 
 

--
 
 

--
« Je déteste la montagne, ça cache le paysage »
Alphonse Allais

[Pavel Pavlov]

Hi James, Martin and all,

I'm afraid that none of the variants of "evacuate-bytecode-stack-into-locals" scheme will not work in all cases.
The reason is bytecode verifier rules for uninitialized objects.
Here uninitialized objects are objects created by `new` instruction but not yet completed their constructors (i.e. `invokespecial Foo.<init>` calls).

For each such object verifier creates new singleton type `uninitialized(Offs)` where `Offs` is the bytecode offset of corresponding `new` instruction.

There are special rules and checks for such types:
1) Check that uintialized objects does not escape to fields/arrays/return values/method arguments

2) Define point where object becomes fully initialized: Rewrite all occurences of U=`uinitialized(X)` in bytecode stack & locals to valid class type `Foo` after completion of `invokespecial Foo.<init>` instruction that have `U` as type of its first argument

3) Check that at most one object of type `unitialized(X)` live at any program point for any X. For this:
3a) At the point of any `new` instruction N check that there are no live `unitialized(X)` objects, where X is offset of N
3b) For any backward branch (i.e. for any potential loop backchain) check that if values `unitialized(X)` and `unitialized(Y)` are merged at the target of the branch then X = Y.
3c) For any bytecode instruction from within protected region check that no locals contain a value of `unitialized(X)` type.

Last rule is a real bummer for try/catch inlining: you cannot live uninitialized objects on the stack as they will be dropped nor you can save them into locals as the resulting bytecode will be unverifiable.

JVM 7 Spec, Section 4.9.2 Structural Constraints:
There must never be an uninitialized class instance in a local variable in code protected by an exception handler (§4.10.2.4).

[Jason Zaugg]

On Wed, Jan 30, 2013 at 3:31 PM, Pavel Pavlov <pavel.e...@gmail.com> wrote:

Hi James, Martin and all,

I'm afraid that none of the variants of "evacuate-bytecode-stack-into-locals" scheme will not work in all cases.
The reason is bytecode verifier rules for uninitialized objects.
Here uninitialized objects are objects created by `new` instruction but not yet completed their constructors (i.e. `invokespecial Foo.<init>` calls).

It turns out that other compiler transformations (e.g. lifting local defs, closure conversion) lead into the same bear pit. I'm putting some backstops in place that emit an implementation restriction [1]. So I think we're willing to limit what you can express in self-/super-calls, and early initializers if it simplifies the implementation. Of course, detecting when we're in this situation isn't trivial, as I've found trying to plug all of the holes in the dike for SI-6666.

-jason

[1] https://github.com/retronym/scala/compare/ticket/6666

[James Iry]

Can you give a concrete example of Scala code the proposal could not handle?

The proposal is that

  new Foo(try/catch)

would become

  val temp0 = try/catch

  new Foo(temp0)

which at bytecode level would be

  try/catch region initializing temp0

  new Foo

  load_local temp0

  invokespecial Foo init

Whether done at the byte code level or as a tree->tree transform we'd keep the uninitialized Foo safely outside of the try/catch region.

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[James Iry]

Oops, missed a dup in the bytecode. Insert accordingly. Doesn't change the point since it still lies outside the protected region.

[Pavel Pavlov]

So, you propose to change the program order of `new` instruction and constructor's arguments evaluation (or two `new` instructions as in `new Foo(new Bar())`).
The idea looks attractive at the first sight, however there may be some problems with the order of effects.

Bytecode instruction `new T` has some side-effects, which (according to JVM spec) are:
1) Class resolution/loading of T
2) Class initialization of T
3) Exception due to failure of `new`-specific checks (e.g. if T is not an interface nor an abstract class)
4) OutOfMemoryError while trying to allocate memory for an instance of class T

Of these, last one is uninteresting as it's is fact non-deterministic error. Changing the order of others may produce very subtle errors:
Class initialization executes user-defined code ("static initializer" aka `<clinit>` method).
In Scala, you normally has no clinits as there are (still yet) no statics & classes' companions are compiled into different VM classes.
But you can perfectly still inherit a Java class which have non-trivial code in their clinit (let's suppose now this Java class resides in 3rd-party library and it does really nasty stuff - loads native libraries, creates threads, downloads stuff from the net etc.).

Changing order of class loading/resolution may lead to even more subtle errors:
- Class T in `new T` can be: non-verifiable, inaccessible, it can not exist at all: in all these cases `new T` throws an exception.
- For classes loaded with custom (user-defined) classloaders any amount of user-defined code can be executed. For example, Eclipse/OSGi platform does its bundle wiring through classloader hooks and is infamously known as critically depending on the class loading order.

Moreover with this transformation one can produce non-local change of program semantics with only innocent-looking local change in code:
  object OneOfHundredLibrariesIUse {
    @inline def getNumber(s: String): Int = Integer.parse(s)
  }
  class Foo(i: Int) exetnds OneOThousand3rdPartyClasses(i)
  new Foo(util.getNumber("qwe"))

Then I've got new library version from maven:
  object OneOfHundredLibrariesIUse {
    @inline def getNumber(s: String): Int = try { Integer.parse(s) } catch { _ => -1 }
  }

And unexpectedly started giving strange errors as class loading of `OneOThousand3rdPartyClasses` (which may do non-trivial initialization) and inlined call to `getNumber` are swapped in time.

The partial solution to this is to insert bytecode instruction `ldc T` where `new T` instruction originally was placed but ldc only performs class loading for T and does not perform class initialization.

[James Iry]

Ooh, nasty. And good catch. I'll look into reasonably low overhead ways to force initialization.

[James Iry]

Two ways to ensure class init has happened when you don't know anything else about the class. 

The officially sanctioned ways is one of the two variants of java.lang.Class.forName, e.g. http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Class.html#forName(java.lang.String, boolean, java.lang.ClassLoader).  I think we'd want to do Class.forName(classOf[Foo].getName, true, classOf[Foo].getClassLoader). Probably push it to a helper method in the library so we don't generate quite so much byte code every time. Still, that's probably expensive at runtime.

The unofficial way is sun.misc.Unsafe#ensureClassInitialized http://www.docjar.com/docs/api/sun/misc/Unsafe.html#ensureClassInitialized(Class) . Probably fast but pretty much off the table because it's not portable, which is ungood in a compiler for the JVM.

Grzegorz suggested doing it the slow way but hiding behind invokeDynamic to ensure it only happens once. That's obviously a Java 7+ thing only. We could create the same once-only semantics by hiding behind a static boolean field (which could be volatile if we don't care about duplicating work across threads or it could be synchronized if we do). But…ugh.

Adriaan suggested that we just emit a warning in cases where we're reordering the "new" operations, but that warning would need an easy way to disable it locally because most of the time the user just won't care about static initialization order.

[James Iry]

A third way to ensure class init, and it's crazy: create an uninitialized object and then throw it away.

new Foo

pop

Cheap, cheerful, and valid. On paper. It's not something that javac would ever produce so who knows what various JVM implementations will do with it in practice.

Some more discussion http://james-iry.blogspot.com/2013/02/the-best-laid-schemes-o-mice.html