Skip to content

Transformation

Jump to bottom Edit New page
Vlad Ureche edited this page Jun 15, 2014 · 7 revisions

This page will describe the value class transformation.

Let us start with an example:

$ cd Workspace/value-plugin/sandbox/
$ cat complex.scala 

@value class Complex(val re: Double, val im: Double) {
  def +(c: Complex) = new Complex(re + c.re, im + c.im)
  override def toString: String = s"$re + $im * i"
}

object Test {
  def main(args: Array[String]): Unit = {
    val c1 = new Complex(1.0, 2.0)
    val c2 = new Complex(2.0, 1.0)
    val c = c1 + c2
    println(c.toString)
  }
}

$ va-scalac complex.scala 

$ va-scala Test
3.0 + 3.0 * i

Surprisingly, this execution creates a single instance of a class Complex! It is required for the + operation return, as the Java Virtual Machine specification does not allow multiple returns.

The translated low-level code is (simplified, only showing the Test object):

$ va-scalac -Xprint:valium-commit complex.scala 
[[syntax trees at end of             valium-commit]] // complex.scala
package <empty> {
  ...
  object Test extends Object {
    def main(args: Array[String]): Unit = {
      val c1$re: Double = 1.0;
      val c1$im: Double = 2.0;
      val c2$re: Double = 2.0;
      val c2$im: Double = 1.0;
      val $$21: Complex = Complex.this.+$xtension(c1$re, c1$im, c2$re, c2$im);
      val c$re: Double = $$21.re;
      val c$im: Double = $$21.im;
      println(Complex.this.toString$xtension(c$re, c$im))
    }
  }
}

As you can see, the Complex class has been inlined and instead of calling methods on the class itself, the code calls extension methods, which don't require creating the object. The single instance of Complex in the execution is produced by the call to the +$xtension extension method, which cannot return the individual fields.

How does the value class plugin get the code from the original form to the optimized form? Well, in 6 successive phases, using the Unified Data Representation Transformation:

$ va-scalac -Xshow-phases
    phase name  id  description
    ----------  --  -----------
        parser   1  parse source into ASTs, perform simple desugaring
         namer   2  resolve names, attach symbols to named trees
packageobjects   3  load package objects
         typer   4  the meat and potatoes: type the trees
        patmat   5  translate match expressions
superaccessors   6  add super accessors in traits and nested classes
    extmethods   7  add extension methods for inline classes
       pickler   8  serialize symbol tables
     refchecks   9  reference/override checking, translate nested objects
       uncurry  10  uncurry, translate function values to anonymous classes
     tailcalls  11  replace tail calls by jumps
    specialize  12  @specialized-driven class and method specialization
valium-prepare  13
 valium-verify  14
 valium-addext  15
 valium-inject  16
 valium-coerce  17
 valium-commit  18
 explicitouter  19  this refs to outer pointers
       erasure  20  erase types, add interfaces for traits
   posterasure  21  clean up erased inline classes
      lazyvals  22  allocate bitmaps, translate lazy vals into lazified defs
    lambdalift  23  move nested functions to top level
  constructors  24  move field definitions into constructors
       flatten  25  eliminate inner classes
         mixin  26  mixin composition
       cleanup  27  platform-specific cleanups, generate reflective calls
    delambdafy  28  remove lambdas
         icode  29  generate portable intermediate code
           jvm  30  generate JVM bytecode
      terminal  31  the last phase during a compilation run

The following subsections will describe each of the phases.

The Preparation Phase (valium-prepare)

This phase is just a technical requirement, as some of the Scala compiler abstract syntax tree patterns result in suboptimal code after the translation, and in this phase we can rewrite them to equivalent but more optimal cases. The most obvious example is this:

  val i = new Complex(0.0, 0.1)
  i.asInstanceOf[Complex] // requires boxing

In this code we know statically that i has type Complex, thus the cast is redundant. Still, keeping the cast forces boxing i into an object, which is suboptimal. For such a case, we remove the cast altogether. It should be noted that the cast needs not be written by the user -- earlier phases in the compiler also introduce casts to avoid type errors for complex expressions.

The Verify Phase (valium-verify)

The verification phase checks the properties of the value classes. For example, given the following class:

@value class Complex(var re: Double, var im: Double)

The valium-verify phase will complain about the mutable fields:

$ cd Workspace/value-plugin/sandbox/
$ va-scalac complex-bad.scala 
complex-bad.scala:1: error: there can only be immutable fields in valium classes
@value class Complex(var re: Double, var im: Double)
                         ^
complex-bad.scala:1: error: there can only be immutable fields in valium classes
@value class Complex(var re: Double, var im: Double)
                                         ^
two errors found

This phase will verify all the restrictions on value classes:

  • that value classes are classes and not traits of objects
  • that value classes are not abstract
  • that all fields are public
  • that all fields are immutable
  • that all fields are non-value classes (otherwise we may have infinite expansions)
  • that value classes don't contain type members
  • that value classes don't define additional parameters
  • that value classes don't define secondary constructors
  • that value classes don't define their own hashCode and equals implementations
  • that the value class constructor is side-effect-free
  • that no class extends a value class (and the final flag is set)

The AddExt Phase (valium-addext)

So far, the compiler phases focused on preparing and verifying the source code for transformation. It is only now that they actually start transforming the tree: The next phase moves value class methods to an object, thus making them extension methods. At this point, the extension methods still need boxing. Getting back to our running example in complex.scala (output simplified):

$ va-scalac complex.scala -Xprint:valium-addext
[[syntax trees at end of             valium-addext]] // complex.scala
package <empty> {
  @value final class Complex extends Object {
    private[this] val re: Double = _;
    def re(): Double = Complex.this.re;
    private[this] val im: Double = _;
    def im(): Double = Complex.this.im;
    def +(c: Complex): Complex = Complex.+$xtension(Complex.this, c);
    override def toString(): String = Complex.toString$xtension(Complex.this);
    override def equals(x$1: Any): Boolean = Complex.equals$xtension(Complex.this, x$1);
    override def hashCode(): Int = Complex.hashCode$xtension(Complex.this)
  };
  object Complex extends Object {
    final def +$xtension($this: Complex, c: Complex): Complex = new Complex($this.re().+(c.re()), $this.im().+(c.im()));
    final def toString$xtension($this: Complex): String = new StringContext(scala.this.Predef.wrapRefArray[String](Array[String]{"", " + ", " * i"})).s(scala.this.Predef.genericWrapArray[Any](Array[Any]{$this.re(), $this.im()}));
    final def equals$xtension($this: Complex, x$1: Any): Boolean = x$1.isInstanceOf[Complex]().&&({
      <synthetic> val Complex$1: Complex = x$1.asInstanceOf[Complex]();
      $this.re().==(Complex$1.re()).&&($this.im().==(Complex$1.im()))
    });
    final def hashCode$xtension($this: Complex): Int = -1679819632.+($this.re.hashCode()).+($this.im.hashCode())
  };
  object Test extends Object {
    def main(args: Array[String]): Unit = {
      val c1: Complex = new Complex(1.0, 2.0);
      val c2: Complex = new Complex(2.0, 1.0);
      val c: Complex = c1.+(c2);
      println(c.toString())
    }
  }
}

Once the extension methods have been extracted, the next step is applying the unified data representation transformation.

Unified Data Representation Transformation

The value class plugin follows exactly the patterns from the unified data representation transformation, which have been explained in miniboxing. In this tutorial, we will only show what each phase does and comment on it.

The Inject Phase (valium-inject)

Unlike miniboxing, the injection phase on the value class plugin is very simple: if a value has type V, where V is a value class, then mark it for unboxing: V @unboxed. Note that it will not transform deep inside generics, thus List[V] will remain List[V]:

$ va-scalac complex.scala -Xprint:valium-inject
[[syntax trees at end of             valium-inject]] // complex.scala
package <empty> {
  @value final class Complex extends Object {
    private[this] val re: Double = _;
    def re(): Double = Complex.this.re;
    private[this] val im: Double = _;
    def im(): Double = Complex.this.im;
    def +(c: Complex @unboxed): Complex = Complex.+$xtension(Complex.this, c);
    override def toString(): String = Complex.toString$xtension(Complex.this);
    override def equals(x$1: Any): Boolean = Complex.equals$xtension(Complex.this, x$1);
    override def hashCode(): Int = Complex.hashCode$xtension(Complex.this)
  };
  object Complex extends Object {
    final def +$xtension($this: Complex @unboxed, c: Complex @unboxed): Complex = new Complex($this.re().+(c.re()), $this.im().+(c.im()));
    final def toString$xtension($this: Complex @unboxed): String = new StringContext(scala.this.Predef.wrapRefArray[String](Array[String]{"", " + ", " * i"})).s(scala.this.Predef.genericWrapArray[Any](Array[Any]{$this.re(), $this.im()}));
    final def equals$xtension($this: Complex @unboxed, x$1: Any): Boolean = x$1.isInstanceOf[Complex]().&&({
      val Complex$1: Complex @unboxed = x$1.asInstanceOf[Complex]();
      $this.re().==(Complex$1.re()).&&($this.im().==(Complex$1.im()))
    });
    final def hashCode$xtension($this: Complex @unboxed): Int = -1679819632.+($this.re.hashCode()).+($this.im.hashCode())
  };
  object Test extends Object {
    def main(args: Array[String]): Unit = {
      val c1: Complex @unboxed = new Complex(1.0, 2.0);
      val c2: Complex @unboxed = new Complex(2.0, 1.0);
      val c: Complex @unboxed = c1.+(c2);
      println(c.toString())
    }
  }
}

This is a very simple transformation, with little secret sauce to it.

The Coerce Phase (valium-coerce)

The coerce phase is a bit more complex, in that it takes care of four aspects:

  • it adds coercions when required by subtyping and by generics
  • it boxes method receivers when necessary
  • but if method receivers have extension methods, it redirects to the extension method instead of boxing
  • it eliminates unstable unboxed expressions from the tree by boxing them (unboxed unstable expressions cannot be transformed to bytecode equivalents)

While the first 3 are common to all data representation transformations, the last one is specific to value classes. Unstable expressions are defined in the Scala language specification and intuitively are expressions that may change their value in time:

$ cat stable.scala 
object Test {
  val c = 3
  import c._

  def d = 4 // may change value in time
            // no stability guarantee!
  import d._
}
$ scalac stable.scala 
stable.scala:7: error: stable identifier required, but Test.this.d found.
  import d._
         ^
one error found

The coercions introduced by the valium-coerce phase to our running example are:

$ va-scalac complex.scala -Xprint:valium-coerce
[[syntax trees at end of             valium-coerce]] // complex.scala
package <empty> {
  @value final class Complex extends Object {
    private[this] val re: Double = _;
    def re(): Double = Complex.this.re;
    private[this] val im: Double = _;
    def im(): Double = Complex.this.im;
    def +(c: Complex @unboxed): Complex = Complex.+$xtension(scala.this.box2unbox[Complex](Complex.this), c);
    override def toString(): String = Complex.toString$xtension(scala.this.box2unbox[Complex](Complex.this));
    override def equals(x$1: Any): Boolean = Complex.equals$xtension(scala.this.box2unbox[Complex](Complex.this), x$1);
    override def hashCode(): Int = Complex.hashCode$xtension(scala.this.box2unbox[Complex](Complex.this))
  };
  object Complex extends Object {
    final def +$xtension($this: Complex @unboxed, c: Complex @unboxed): Complex = new Complex(scala.this.unbox2box[Complex]($this).re().+(scala.this.unbox2box[Complex](c).re()), scala.this.unbox2box[Complex]($this).im().+(scala.this.unbox2box[Complex](c).im()));
    final def toString$xtension($this: Complex @unboxed): String = new StringContext(scala.this.Predef.wrapRefArray[String](Array[String]{"", " + ", " * i"})).s(scala.this.Predef.genericWrapArray[Any](Array[Any]{scala.this.unbox2box[Complex]($this).re(), scala.this.unbox2box[Complex]($this).im()}));
    final def equals$xtension($this: Complex @unboxed, x$1: Any): Boolean = x$1.isInstanceOf[Complex]().&&({
      val Complex$1: Complex @unboxed = scala.this.box2unbox[Complex](x$1.asInstanceOf[Complex]());
      scala.this.unbox2box[Complex]($this).re().==(scala.this.unbox2box[Complex](Complex$1).re()).&&(scala.this.unbox2box[Complex]($this).im().==(scala.this.unbox2box[Complex](Complex$1).im()))
    });
    final def hashCode$xtension($this: Complex @unboxed): Int = -1679819632.+(scala.this.unbox2box[Complex]($this).re().hashCode()).+(scala.this.unbox2box[Complex]($this).im().hashCode())
  };
  object Test extends Object {
    def main(args: Array[String]): Unit = {
      val c1: Complex @unboxed = scala.this.box2unbox[Complex](new Complex(1.0, 2.0));
      val c2: Complex @unboxed = scala.this.box2unbox[Complex](new Complex(2.0, 1.0));
      val c: Complex @unboxed = scala.this.box2unbox[Complex](Complex.this.+$xtension(c1, c2));
      scala.this.Predef.println(Complex.this.toString$xtension(c))
    }
  }
}

We can also test the stable expression transformation:

$ cat complex2.scala 

@value class Complex(val re: Double, val im: Double)

object Test {
  def main(args: Array[String]): Unit = {
    val c1 = new Complex(1.0, 2.0)
    val c2 = new Complex(2.0, 1.0)
    def cond = true
    val c = if (cond) c1 else c2 //unstable
  }
}

$ va-scalac complex2.scala -Xprint:valium-coerce
[[syntax trees at end of             valium-coerce]] // complex2.scala
package <empty> {
  ...
  object Test extends Object {
    def <init>(): Test.type = {
      Test.super.<init>();
      ()
    };
    def main(args: Array[String]): Unit = {
      val c1: Complex @unboxed = scala.this.box2unbox[Complex](new Complex(1.0, 2.0));
      val c2: Complex @unboxed = scala.this.box2unbox[Complex](new Complex(2.0, 1.0));
      def cond(): Boolean = true;
      val c: Complex @unboxed = scala.this.box2unbox[Complex](if (cond())
        scala.this.unbox2box[Complex](c1)
      else
        scala.this.unbox2box[Complex](c2));
      ()
    }
  }
}

In this example, the unstable expression would have the type Complex @unboxed:

val c =
  if (cond)
    c1
  else
    c2

Yet, since this is unstable, the valium-coerce phase choses to box and unbox it:

val c: Complex @unboxed = 
  scala.this.box2unbox[Complex](
    if (cond)
      scala.this.unbox2box[Complex](c1)
    else
      scala.this.unbox2box[Complex](c2)
  )

This transformation is done since again, the JVM specification does not allow multiple returns, thus the commit phase would not have a proper lowering for such expressions.

The Commit Phase (valium-commit)

In the case of value classes, the commit phase is the most complex. It takes care of expanding unboxed value classes to their fields and transforming expressions accordingly. The rules for the transformation are documented here: https://github.com/miniboxing/value-plugin/blob/master/components/plugin/src/valium/plugin/transform/commit/ValiumCommitTreeTransformer.scala#L14-L74

Getting back to our running example, we get:

$ va-scalac complex.scala -Xprint:valium-commit
[[syntax trees at end of             valium-commit]] // complex.scala
package {
  @value final class Complex extends Object {
    private[this] val re: Double = _;
    def re(): Double = Complex.this.re;
    private[this] val im: Double = _;
    def im(): Double = Complex.this.im;
    def +(c$re: Double, c$im: Double): Complex = {
      val $$6: Complex = Complex.this;
      val 1$re: Double = $$6.re;
      val 1$im: Double = $$6.im;
      val this$re$2: Double = 1$re;
      val this$im$3: Double = 1$im;
      val arg$c$re$4: Double = c$re;
      val arg$c$im$5: Double = c$im;
      Complex.+$xtension(this$re$2, this$im$3, arg$c$re$4, arg$c$im$5)
    };
    override def toString(): String = {
      val $$10: Complex = Complex.this;
      val 7$re: Double = $$10.re;
      val 7$im: Double = $$10.im;
      val this$re$8: Double = 7$re;
      val this$im$9: Double = 7$im;
      Complex.toString$xtension(this$re$8, this$im$9)
    };
    override def equals(x$1: Any): Boolean = {
      val $$15: Complex = Complex.this;
      val 11$re: Double = $$15.re;
      val 11$im: Double = $$15.im;
      val this$re$12: Double = 11$re;
      val this$im$13: Double = 11$im;
      val 14: Any = x$1;
      Complex.equals$xtension(this$re$12, this$im$13, 14)
    };
    override def hashCode(): Int = {
      val $$19: Complex = Complex.this;
      val 16$re: Double = $$19.re;
      val 16$im: Double = $$19.im;
      val this$re$17: Double = 16$re;
      val this$im$18: Double = 16$im;
      Complex.hashCode$xtension(this$re$17, this$im$18)
    }
  };
  object Complex extends Object {
    final def +$xtension($this$re: Double, $this$im: Double, c$re: Double, c$im: Double): Complex = new Complex($this$re.+(c$re), $this$im.+(c$im));
    final def toString$xtension($this$re: Double, $this$im: Double): String = new StringContext(scala.this.Predef.wrapRefArray[String](Array[String]{"", " + ", " * i"})).s(scala.this.Predef.genericWrapArray[Any](Array[Any]{$this$re, $this$im}));
    final def equals$xtension($this$re: Double, $this$im: Double, x$1: Any): Boolean = x$1.isInstanceOf[Complex]().&&({
      val $$20: Complex = x$1.asInstanceOf[Complex]();
      val Complex$1$re: Double = $$20.re;
      val Complex$1$im: Double = $$20.im;
      $this$re.==(Complex$1$re).&&($this$im.==(Complex$1$im))
    });
    final def hashCode$xtension($this$re: Double, $this$im: Double): Int = -1679819632.+($this$re.hashCode()).+($this$im.hashCode())
  };
  object Test extends Object {
    def <init>(): Test.type = {
      Test.super.<init>();
      ()
    };
    def main(args: Array[String]): Unit = {
      val c1$re: Double = 1.0;
      val c1$im: Double = 2.0;
      val c2$re: Double = 2.0;
      val c2$im: Double = 1.0;
      val $$21: Complex = Complex.this.+$xtension(c1$re, c1$im, c2$re, c2$im);
      val c$re: Double = $$21.re;
      val c$im: Double = $$21.im;
      scala.this.Predef.println(Complex.this.toString$xtension(c$re, c$im))
    }
  }
}

Which is exactly what we have seen in the beginning of the article. While the code output could certainly be improved by a simple copy propagation phase, it is not necessary to do this in the plugin, since the backend already contains copy propagation and dead code elimination phases.

We encourage the readers to try out different examples. We are aware of an important bug which prevents value classes from working under separate compilation. It is a technical issue, not a fundamental limitation, but you will need to compile the value classes along with the code that uses them in the same file (or in different files, all compiled at the same time): https://github.com/miniboxing/value-plugin/issues/37

This said, the benchmarks show how well this transformation works to eliminate the overhead of the object-oriented representation.

Add a custom footer
Add a custom sidebar

Clone this wiki locally