today's tangent: specialized non-local returns

[Paul Phillips]

On Tue, Dec 20, 2011 at 5:42 PM, Sébastien Bocq
<sebasti...@gmail.com> wrote:
> def isEmpty: Boolean = {
>         var result = true
>         breakable {
>           for (x <- this) {
>             result = false
>             break
>           }
>         }
>         result
>       }
> It is much too complex for what it is and most of these methods are
> overriden in subclasses anyway.

Rather than responding in any direct way, I'll tell you that example
got me wondering once again why I can't write that method the way
which comes to mind first, which is:

def isEmpty: Boolean = {
this foreach (_ => return false)
true
}

Here's (a simulation of) the real isEmpty vs. mine (for the
non-closure part: the real isEmpty creates two additional objects,
mine creates one.)

public static boolean isEmpty1(Trav);
0: new #15; //class scala/runtime/BooleanRef
3: dup
4: iconst_1
5: invokespecial #19; //Method scala/runtime/BooleanRef."<init>":(Z)V
8: astore_1
9: getstatic #25; //Field
scala/util/control/Breaks$.MODULE$:Lscala/util/control/Breaks$;
12: new #27; //class Trav$$anonfun$isEmpty1$1
15: dup
16: aload_0
17: aload_1
18: invokespecial #30; //Method
Trav$$anonfun$isEmpty1$1."<init>":(LTrav;Lscala/runtime/BooleanRef;)V
21: invokevirtual #36; //Method
scala/util/control/Breaks.breakable:(Lscala/Function0;)V
24: aload_1
25: getfield #40; //Field scala/runtime/BooleanRef.elem:Z
28: ireturn

public static boolean isEmpty2(Trav);
0: new #45; //class java/lang/Object
3: dup
4: invokespecial #48; //Method java/lang/Object."<init>":()V
7: astore_1
8: iconst_0
9: istore_2
10: aload_0
11: new #50; //class Trav$$anonfun$isEmpty2$1
14: dup
15: aload_0
16: aload_1
17: invokespecial #53; //Method
Trav$$anonfun$isEmpty2$1."<init>":(LTrav;Ljava/lang/Object;)V
20: invokeinterface #58, 2; //InterfaceMethod
Trav.foreach:(Lscala/Function1;)V
25: iconst_1
26: istore_2
27: goto 47
30: astore_3
31: aload_3
32: invokevirtual #64; //Method
scala/runtime/NonLocalReturnControl.key:()Ljava/lang/Object;
35: aload_1
36: if_acmpne 49
39: aload_3
40: invokevirtual #67; //Method
scala/runtime/NonLocalReturnControl.value:()Ljava/lang/Object;
43: invokestatic #73; //Method
scala/runtime/BoxesRunTime.unboxToBoolean:(Ljava/lang/Object;)Z
46: istore_2
47: iload_2
48: ireturn
49: aload_3
50: athrow

Hmmm, hey, let's specialize NonLocalReturnControl, and hack hack hack.
Some time later:

public static boolean isEmpty2(Trav);
Code:
Stack=5, Locals=3, Args_size=1
0: new #45; //class java/lang/Object
3: dup
4: invokespecial #48; //Method java/lang/Object."<init>":()V
7: astore_1
8: aload_0
9: new #50; //class Trav$$anonfun$isEmpty2$1
12: dup
13: aload_0
14: aload_1
15: invokespecial #53; //Method
Trav$$anonfun$isEmpty2$1."<init>":(LTrav;Ljava/lang/Object;)V
18: invokeinterface #58, 2; //InterfaceMethod
Trav.foreach:(Lscala/Function1;)V
23: iconst_1
24: goto 40
27: astore_2
28: aload_2
29: invokevirtual #64; //Method
scala/runtime/NonLocalReturnControl.key:()Ljava/lang/Object;
32: aload_1
33: if_acmpne 41
36: aload_2
37: invokevirtual #68; //Method
scala/runtime/NonLocalReturnControl.value$mcZ$sp:()Z <--- look ma,
specialized
40: ireturn
41: aload_2
42: athrow

It's not as if the real version avoids the throw/catch, it just outsources it.

And for the coup de grace, the specialized closure:

public boolean apply$mcZI$sp(int);
0: new #26; //class scala/runtime/NonLocalReturnControl$mcZ$sp
3: dup
4: aload_0
5: getfield #28; //Field nonLocalReturnKey1$1:Ljava/lang/Object;
8: iconst_0
9: invokespecial #32; //Method
scala/runtime/NonLocalReturnControl$mcZ$sp."<init>":(Ljava/lang/Object;Z)V
12: athrow

Of course to get that one I had to write isEmpty like this, which is
safe regardless of what's really in the Traversable although it may
not meet every company's style guidelines. (WE TYPE SAFELY.)

def isEmpty: Boolean = {
this.asInstanceOf[Traversable[Int]] foreach (_ => { return false }: Boolean)
true
}

That's a thing of beauty right there. Maybe not at the source level.
But on the inside.

[Miguel Garcia]

I also played with making non-local returns less non-local returnish,

  - motivation on slides 13-14,
  - approach   on slides  8-11

http://lamp.epfl.ch/~magarcia/ScalaNET/slides/2011-11-22-BetterInlining.pdf

The prototype emits faster code, but at this point can't duplicate all tree shapes with DefTree's that show up in practice.

Miguel

[Paul Phillips]

On Wed, Dec 21, 2011 at 3:25 AM, Miguel Garcia <mgarc...@yahoo.com> wrote:
> I also played with making non-local returns less non-local returnish,

That brings me to my next couple questions.  To get those results I had to disable this transformation in cleanup, which as the comment deftly notes is only necessary for MSIL:

     /* MSIL requires that the stack is empty at the end of a try-block.
      * Hence, we here rewrite all try blocks with a result != {Unit, All} such that they
      * store their result in a local variable. The catch blocks are adjusted as well.
      * The try tree is subsituted by a block whose result expression is read of that variable. */

JVM does fine without it.  I attach the bytecode diff before and after (the differences enclose both specializing non-local-returns and disabling that transformation.) Is there some reason we can't disable this on the jvm? It cannot possibly be assisting with the optimization of those methods to create an unnecessary local and store the result only to then pop and return it.  The reason it matters is not so much try/catch as try/finally.  Right now this:

 def f[T](body: => T) = try body finally println("hi")

Becomes this:

 def f(body: Function0): Object = {
   var exceptionResult1: Object = _;
   try {
     exceptionResult1 = body.apply()
   } finally scala.this.Predef.println("hi");
   exceptionResult1
 };

But with my patch it becomes this:
 
 def f(body: Function0): Object = try {
   body.apply()
 } finally scala.this.Predef.println("hi");  

> http://lamp.epfl.ch/~magarcia/ScalaNET/slides/2011-11-22-BetterInlining.pdf

Why can't I reproduce this, from slide 14:

 blocks: [1,7,16,15,26,28,27,25,9,12,10,13,18,19,20,17,11,8,14,22,23,29,24,21,3,4,2,5]

When I compile that with -optimise here's what's in the icode saved from -Xprint-icode:

A$$anonfun$nonLocalReturnExample$1.icode:  blocks: [1]
A$$anonfun$nonLocalReturnExample$1.icode:  blocks: [1,2,4]
A$$anonfun$nonLocalReturnExample$1.icode:  blocks: [1]
A$$anonfun$nonLocalReturnExample$1.icode:  blocks: [1]
A.icode:  blocks: [1,2,3,4,5,6,7]
A.icode:      consisting of blocks: List(6, 5, 4, 3)
A.icode:  blocks: [1]

I'm getting the icode without inlining I guess? Even if I -Xprint:jvm -Xprint-icode I see the same thing.  How are you extracting it?

[Miguel Garcia]

Paul,

In order to print ICode not just after GenICode but also after any of the optimization phases, I use this in Global:

        // print trees
        if (opt.printPhase || opt.printLate && runIsAt(cleanupPhase)) {
          if(runIsAtBackend) {
            writeICode() // write icode to *.icode files
          } else {
            if (opt.showTrees) nodePrinters.printAll()
            else printAllUnits()
          }
        }

where `runIsAtBackend` was added to Run:

  def runIsAtBackend       = (runIsAt(icodePhase) || runIsPast(icodePhase))

Regarding the

  case theTry @ Try(block, catches, finalizer)

in CleanUp, I see no problem guarding it with `if forMSIL`

Regarding the codegen recipe you're cooking for non-local returns, my slides explore solving a slightly more general problem (anon-closures passed as argument to functions using them only once). I believe it takes approx the same effort smarting up codegen in both cases (thus, going for the general case seems better).

Also, this "early inlining" idea can be applied to those local methods which are invoked just once ("inlining" them just before lambdalift). There are ~170 such cases in the library, and over 800 in the compiler. The Android people should be happy! Each callsite and each method def adds to some metadata-table that Android limits to 64K entries. Or so I understood.


Miguel

[Paul Phillips]

On Wed, Dec 21, 2011 at 8:52 AM, Miguel Garcia <mgarc...@yahoo.com> wrote:

Also, this "early inlining" idea can be applied to those local methods which are invoked just once ("inlining" them just before lambdalift).

That seems like a very good, easily doable idea.  I'm sorry I haven't looked more closely at the inliner notes you sent me a while back, I'm failing to keep up with even a fraction of the stuff I would like / ought to.  I'll do that now.

[Miguel Garcia]

The applicability conditions of "local method inlining" that worked for me can be gleaned from the attached snippet (no better documentation yet, sorry about that).

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