dotty linker

Join the chat at and call for @Darkdimius if you have questions.

This is a modified version of Dotty compiler, that includes optimization phases. Currently included phases are:

• auto-specialization, enabled by passing -lto:spec or -lto:all flag;
• rewrite rules, enabled by passing -rewrites.

Rewrite rules

This a mechanism that allows to define custom optimizations alongside with a library. See this illustaration:

import dotty.linker._

@rewrites
object rules{
  // Library authors can define rewrite rules alongside with a library.
  // Rules are applied by a phase that runs after pickler. Thus they do not interact with type checking.
  // Rules can be defined in other compilation units, as they are discovered through TASTY.
  // The following examples are already working in my prototype:

  def isEmpty(x: Seq[Int]) =
    Rewrite(from = x.length == 0,               // linker will look for pattern in `from`, where method arguments are variables to be bound to trees
            to   = x.isEmpty)                   // if the pattern matches, it will rewrite it to `to`, replacing arguments with bound trees

  def twoDropRights(x: List[Int], a: Int, b: Int) =
    Rewrite(from = x.dropRight(a).dropRight(b), // multiple variables can be bound at once
            to   = x.dropRight(a + b))
  
  def bigIntShift(bi: BigInt, a: Int)(implicit evi: Literal[a.type]) =
  Rewrite(from = bi / a,
     to = 
      if (Integer.bitCount(a) == 1) // one of those 2 branches will be eliminated either by Linker or by JIT as dead code
        bi >> java.lang.Integer.numberOfTrailingZeros(a) 
      else bi / a
     )

  def twoFilters(x: List[Int], a: Int => Boolean, b: Int => Boolean)(implicit apure: IsPure[a.type]) =
                                                // implicits can be used to specify additional constraints. 
                                                // my prototype currently supports IsPure and IsLiteral
                                                // IsPure is a tweaked check from tpd.
    Rewrite(from = x.filter(a).filter(b), 
            to   = x.filter(x => a(x) && b(x)))

  def customFancyWarning(x: ParSeq[Int], x: (Int, Int) => Int) =
    Warn(pattern = x.reduceLeft(x)),            // custom warnings are also supported
             msg = “reduceLeft on parallel collection makes no sense”)

  def customFancyError(a: BigInt) =
    Error(pattern = a / 0,                      // custom errors are also supported
              msg = “This code is going to fail in runtime“)

  // the following examples are not _yet_ implemented in the prototype.

  def twoFiltersGeneric[T](x: List[T], a: T => Boolean, b: T => Boolean)(implicit apure: IsPure[a.type]) =
                                                // in case method takes type arguments, T becomes a similar type-variable to-be-bound.  
    Rewrite(from = x.filter(a).filter(b), 
            to   = x.filter(x => a(x) && b(x)))

  def metaExample[T](x: List[T])(implicit apure: IsPure[a.type]) =
                                                // in case method takes type arguments, T becomes a similar type-variable to-be-bound.  
    RewriteMeta(from = x.toString, 
            to = meta { /* entry point to interpreted scala-meta macros */})
}

object Test{
  def myPrettyPrint(a: Any): Unit = ()
  def main(args: Array[String]): Unit = {
     List(1,2,3).length == 0                    // will be rewritten to List(1,2,3).isEmpty
     List(1,2,3).drop(1).drop(1)                // will be rewritten to List(1, 2, 3).drop(2)
     List(1,2,3).dropRight(1).dropRight(1)      // will be rewritten to List(1, 2, 3).dropRight(1 + 1)
     List(1,2,3).filter(_ > 2).filter(_ > 1)    // will be rewritten to List(1, 2, 3).filter(x =>  _ > 2 && _ > 1)
     myPrettyPrint(args.length)                 // will be rewritten to println(“args.length” + “ = “ + args.length)
  }
}

Auto specialization

Build a callgraph, sees which specializations are needed and generates only the required ones. Enabled by -lto:spec or -lto:all.

For details, see

Talks:

• Scala Days 2015 Amsterdam: Dotty Liker: Making your Scala applications smaller and faster [slides], [video]
• FlatMap 2016 Oslo: AutoSpecialization in Dotty [slides]