Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest Chrome, Safari or Firefox browser.

An Optimization-Driven Incremental Inline Substitution Algorithm for Just-In-Time Compilers


Aleksandar Prokopec, Gilles Duboscq,
David Leopoldseder, Thomas W├╝rthinger

Inlining for JIT Compilers


Inlining Problem

        
def main(args: Array[String]) = log(args)
var log: Seq[String] => Unit =
  (xs: Seq[String]) => xs.foreach(println)











        
      

Inlining Problem

        
def main(args: Array[String]) = log(args)
var log: Seq[String] => Unit =
  (xs: Seq[String]) => xs.foreach(println)
trait Seq[T] {
  def apply(i: Int): T
  def length: Int
  def foreach(f: T => Unit) = {
    var i = 0
    while (i < this.length) {
      f(this.apply(i))
      i += 1
    }
  }
}
        
      

Inlining Problem

        
def main(args: Array[String]) =
  args.foreach(println)

trait Seq[T] {
  def apply(i: Int): T
  def length: Int
  def foreach(f: T => Unit) = {
    var i = 0
    while (i < this.length) {
      f(this.apply(i))
      i += 1
    }
  }
}
        
      

Inlining Problem


Choose callsites to inline, so that program execution time is minimized.

Online Inlining Problem


Algorithm Overview





        
def main(args: Array[String]) = log(args)
var log: Seq[String] => Unit =
  (xs: Seq[String]) => xs.foreach(println)
trait Seq[T] {
  def apply(i: Int): T
  def length: Int
  def foreach(f: T => Unit) = {
    var i = 0
    while (i < this.length) {
      f(this.apply(i))
      i += 1
    }
  }
}
        
      
        
def main(args: Array[String]) = log(args)













        
      

Algorithm Overview



Algorithm Overview



Algorithm Overview


        
def main(args: Array[String]) = log(args)
var log: Seq[String] => Unit =
  (xs: Seq[String]) => xs.foreach(println)
trait Seq[T] {
  def apply(i: Int): T
  def length: Int
  def foreach(f: T => Unit) = {
    var i = 0
    while (i < this.length) {
      f(this.apply(i))
      i += 1
    }
  }
}
        
      

Expansion Phase


Expansion Phase


Expansion Phase


Expansion Phase


        



trait Seq[T] {
  def apply(i: Int): T
  def length: Int
  def foreach(f: T => Unit) = {
    var i = 0
    while (i < this.length) {
      f(this.apply(i))
      i += 1
    }
  }
}
        
      

Expansion Phase


Expansion Phase


Analysis Phase


  1. Dataflow analysis and call-tree simplification.
  2. Clustering analysis.

Dataflow Analysis


Dataflow Analysis


Dataflow Analysis


Dataflow Analysis


Dataflow Analysis


Dataflow Analysis


        



class Array[T](val length: Int)
extends Seq[T] {
  def apply(i: Int) = READ(this + i)
  def foreach(f: T => Unit) = {
    var i = 0
    while (i < this.length) {
      f(this.apply(i))
      i += 1
    }
  }
}
        
      

Dataflow Analysis


Dataflow Analysis


Clustering Analysis


Clustering Analysis


Clustering Analysis


Clustering Analysis


Clustering Analysis


Inlining Phase


Inlining Phase


Inlining Phase


Inlining Phase


2nd Expansion Phase


2nd Analysis Phase


2nd Inlining Phase


        
def main(args: Array[String]) = {
  var i = 0
  while (i < args.length) {
    println(READ(args + i))
    i += 1
  }
}
        
      

Priority Heuristic


  1. Which callsites to explore first?
  2. Which clusters to inline first?




Benefit Estimation


Benefit: the expected decrease in program execution time.


Benefit Estimation


Benefit: the expected decrease in program execution time.


Cost-Benefit Tuples


Cost c: the increase in the program size from inlining the method.


Cost-Benefit Tuples




Adaptive Threshold Heuristic


Adaptive Threshold Heuristic


Evaluation


Callsite clustering results in better performance.

Adaptive thresholds result in better performance than fixed thresholds.



Thank you.

Clustering Heuristic



Clustering Heuristic


Clustering Heuristic


Clustering Heuristic


Clustering Heuristic


Clustering Heuristic


Clustering Heuristic


Use a spacebar or arrow keys to navigate