Tutorial ~ Example (Part 3)

In the previous section, we managed to define a transformation object and apply it to the main method. We will now see why the `ildl-plugin` produced four warnings.

To understand the warnings, we will examine how the Scala compiler transforms the code. Luckily, this is not very difficult, as we can output the intermediate representation after every compiler phase as source code. While some parts of the tree are verbose and difficult to follow, the specific one we are interested in is quite clear.

Before we see the compiler output, we can see the compiler phases:

$ ildl-scalac -Xshow-phases
      phase name  id  description
      ----------  --  -----------
          parser   1  parse source into ASTs, perform simple desugaring
 ildl-postparser   2
           namer   3  resolve names, attach symbols to named trees
  packageobjects   4  load package objects
           typer   5  the meat and potatoes: type the trees
     ildl-inject   6
          patmat   7  translate match expressions
  superaccessors   8  add super accessors in traits and nested classes
      extmethods   9  add extension methods for inline classes
         pickler  10  serialize symbol tables
       refchecks  11  reference/override checking, translate nested objects
         uncurry  12  uncurry, translate function values to anonymous classes
     ildl-bridge  13
     ildl-coerce  14
     ildl-commit  15
       tailcalls  16  replace tail calls by jumps
      specialize  17  @specialized-driven class and method specialization
   explicitouter  18  this refs to outer pointers
         erasure  19  erase types, add interfaces for traits
     posterasure  20  clean up erased inline classes
ildl-tweakera...  21
        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 phases starting with ildl are the ones introduced by our plugin. Specifically, the interesting phase is ildl-commit (we will see a waltkthrough of what each phase does later on). For now, we can see the output at the ildl-commit phase:

$ ildl-scalac example.scala -Xprint:ildl-commit

... [warnings]

[[syntax trees at end of               ildl-commit]] // example.scala
package <empty> {
  object Test extends Object {

  ... [lots of code]

    def main(args: Array[String]): Unit = {
      val x1: Long = Test.this.IntPairAsComplex.toRepr(new (Int, Int)(3, 5));
      val x2: Long = Test.this.IntPairAsComplex.toRepr(new (Int, Int)(2, 8));
      scala.this.Predef.println(Test.this.IntPairAsComplex(Test.this.IntPairAsComplex.toHigh(x1)).+(Test.this.IntPairAsComplex.toHigh(x2)));
      scala.this.Predef.println(Test.this.IntPairAsComplex(Test.this.IntPairAsComplex.toHigh(x1)).*(Test.this.IntPairAsComplex.toHigh(x2)))
    }
  }
}

This is what the main method looks like after the ildl transformation. We can simplify it by hiding printing qualified names:

    def main(args: Array[String]): Unit = {
      val x1: Long = IntPairAsComplex.toRepr(new (Int, Int)(3, 5));
      val x2: Long = IntPairAsComplex.toRepr(new (Int, Int)(2, 8));
      println(IntPairAsComplex(IntPairAsComplex.toHigh(x1)).+(IntPairAsComplex.toHigh(x2)));
      println(IntPairAsComplex(IntPairAsComplex.toHigh(x1)).*(IntPairAsComplex.toHigh(x2)))
    }

In the code above, there are two suboptimal parts:

• for the new operator, the new tuple being created is immediately converted to a long integer value, creating useless heap garbage that needs to be collected later;
• for the + and * operations, the values are converted to tuples, the operations are executed and then the results are converted back to integer pairs, which allocates redundant objects.

Of course, we can correct his. And the warnings are exactly what we need:

$ ildl-scalac example.scala
example.scala:24: warning: The new operator can be optimized if you define a public,
non-overloaded and matching constructor method for it in object IntPairAsComplex, 
with the name ctor_Tuple2:
      val x1: Complex = (3, 5)
                        ^
example.scala:25: warning: The new operator can be optimized if you define a public,
non-overloaded and matching constructor method for it in object IntPairAsComplex,
with the name ctor_Tuple2:
      val x2: Complex = (2, 8)
                        ^
example.scala:26: warning: The method + can be optimized if you define a public,
non-overloaded and matching exension method for it in object IntPairAsComplex,
with the name implicit_IntPairAsComplex_+:
      println(x1 + x2)
                 ^
example.scala:27: warning: The method * can be optimized if you define a public,
non-overloaded and matching exension method for it in object IntPairAsComplex,
with the name implicit_IntPairAsComplex_*:
      println(x1 * x2)
                 ^
four warnings found

Let us now try to optimize the constructor. As suggested, we create a ctor_Tuple2 method in the IntPairAsComplex transformation. We won't go into explaining how to create this method, as this is done later in the tutorial.

To implement ctor_Tuple2 we refactor the transformation object:

  import ildl._
  object IntPairAsComplex extends TransformationDescription {
    // bitwise conversions:
    private def real(l: Long @high): Int = (l >>> 32).toInt
    private def imag(l: Long @high): Int = (l & 0xFFFFFFFF).toInt
    private def pack(re: Int, im: Int) =
      (re.toLong << 32l) | (im.toLong & 0xFFFFFFFFl)  	
    // conversions:
    def toRepr(p: (Int, Int)): Long @high = pack(p._1, p._2)
    def toHigh(l: Long @high): (Int, Int) = (real(l), imag(l))
    // constructor:
    def ctor_Tuple2(_1: Int, _2: Int): Long @high = pack(_1, _2)
  }

Now, if we compile the example, we only obtain two warnings:

$ ildl-scalac example.scala 
example.scala:32: warning: The method + can be optimized if you define a public,
non-overloaded and matching exension method for it in object IntPairAsComplex,
with the name implicit_IntPairAsComplex_+:
      println(x1 + x2)
                 ^
example.scala:33: warning: The method * can be optimized if you define a public,
non-overloaded and matching exension method for it in object IntPairAsComplex,
with the name implicit_IntPairAsComplex_*:
      println(x1 * x2)
                 ^
two warnings found

As you can probably imagine, the constructors have been transformed:

    def main(args: Array[String]): Unit = {
      val x1: Long = IntPairAsComplex.ctor_Tuple2(3, 5);
      val x2: Long = IntPairAsComplex.ctor_Tuple2(2, 8);
      println(IntPairAsComplex(IntPairAsComplex.toHigh(x1)).+(IntPairAsComplex.toHigh(x2)));
      println(IntPairAsComplex(IntPairAsComplex.toHigh(x1)).*(IntPairAsComplex.toHigh(x2)))
    }

We can now implement the operations:

    // operations:
    def implicit_IntPairAsComplex_+(c1: Long @high, c2: Long @high)=
      pack(real(c1) + real(c2), imag(c1) + imag(c2))
    def implicit_IntPairAsComplex_*(c1: Long @high, c2: Long @high)=
      pack(real(c1) * real(c2) - imag(c1) * imag(c2),
           real(c1) * imag(c2) + imag(c1) * real(c2))

And the compiler output will be:

    def main(args: Array[String]): Unit = {
      val x1: Long = IntPairAsComplex.ctor_Tuple2(3, 5);
      val x2: Long = IntPairAsComplex.ctor_Tuple2(2, 8);
      println(IntPairAsComplex.toHigh(IntPairAsComplex.implicit_IntPairAsComplex_+(x1, x2)));
      println(IntPairAsComplex.toHigh(IntPairAsComplex.implicit_IntPairAsComplex_*(x1, x2)));
    }

While we eliminated the warnings and this triggered a slight change in the code, what is the final result? If we follow the code, we notice it keeps the long integer encoding for as long as possible:

• the x1 and x2 values are created directly encoded as long integers by the ctor_Tuple2 method;
• the + and * operations occur directly on the long integer encoding
• only at the last step, before printing, the long integers are decoded into pairs, and this happens because any other translation would have been incorrect.

While these optimizations might not seem very productive, we will later see how exactly these transformations were able to speed up the a complex number example by almost 13x.

Now, we have developed our transformation into a rather large one:

object Test {
  // "define" type complex based on integer pairs
  type Complex = (Int, Int)

  // add the addition and multiplication operation to complex numbers
  implicit class IntPairAsComplex(val p1: Complex) extends AnyVal {
    def +(p2: Complex): Complex = (p1._1 + p2._1 , p1._2 + p2._2)
    def *(p2: Complex): Complex = (p1._1 * p2._1 - p1._2 * p2._2,
                                   p1._1 * p2._2 + p1._2 * p2._1)
    // we could define other operations here as well...
  }

  import ildl._
  // make Complex a long integer
  object IntPairAsComplex extends TransformationDescription {
    // bitwise conversions:
    private def real(l: Long @high): Int = (l >>> 32).toInt
    private def imag(l: Long @high): Int = (l & 0xFFFFFFFF).toInt
    private def pack(re: Int, im: Int) =
      (re.toLong << 32l) | (im.toLong & 0xFFFFFFFFl)  	
    // conversions:
    def toRepr(p: (Int, Int)): Long @high = pack(p._1, p._2)
    def toHigh(l: Long @high): (Int, Int) = (real(l), imag(l))
    // constructor:
    def ctor_Tuple2(_1: Int, _2: Int): Long @high = pack(_1, _2)
    // operations:
    def implicit_IntPairAsComplex_+(c1: Long @high, c2: Long @high)=
      pack(real(c1) + real(c2), imag(c1) + imag(c2))
    def implicit_IntPairAsComplex_*(c1: Long @high, c2: Long @high)=
      pack(real(c1) * real(c2) - imag(c1) * imag(c2),
           real(c1) * imag(c2) + imag(c1) * real(c2))
    def extension_toString(c: Long @high) = 
      "(" + real(c) + "," + imag(c) + ")"
  }

  adrt(IntPairAsComplex) {
    // test the output
    def main(args: Array[String]): Unit = {
      val x1: Complex = (3, 5)
      val x2: Complex = (2, 8)
      println(x1 + x2)
      println(x1 * x2)
    }
  }
}

In the next section we will be able to play with the transformation description we have painstakingly developed.

From Here:

• continue with the example, part four
• return to the main page