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 algorithm for JIT compilers.
Implemented in the Enterprise version of GraalVM, a multi-language version of HotSpot JVM.
Significantly advances the program performance compared to the state-of-the-art inliners.

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

Compilation requests may arrive in any order.
Complete call graph not available.
Inlining decisions impact compilation time and subsequent compilation requests.
Excessive inlining puts pressure on limited hardware resources (e.g. I-cache).

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

        
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

        



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

Analysis Phase

Dataflow analysis and call-tree simplification.
Clustering 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

Clustering Analysis

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

Which callsites to explore first?
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

Evaluation

28 real-world benchmarks from DaCapo, Scalabench, SparkPerf, Neo4J, STMBench7 and others
Comparison against Graal's basic inliner and HotSpot C2
Evaluation of the individual aspects of the algorithm

Callsite clustering results in better performance.