Highly Optimizing Ahead-of-Time Compilers for Dynamic Languages

Soutenance de thèse de doctorat

Highly Optimizing Ahead-of-Time Compilers for Dynamic Languages

Olivier Melançon

Jury

  1. Eugène Syriani

    PrésidentDIRO

  2. Sébastien Roy

    MembreDIRO

  3. Marc Feeley

    Directeur de rechercheDIRO

  4. Manuel Serrano

    Co-directeur de rechercheINRIA UCA

  5. Matthew Flatt

    Examinateur externeUniversity of Utah

Preface

First, some background

Example: My Favorite Polynomial

Suppose you want to compute values of your favorite polynomial: p(x) = x^2 + x.

Naturally, you write a program. You choose C because you heard it's fast!

intp(intx){returnx*x+x;}p(5)//30p(10)//110p(3.14)//12staticf_intstaticdoublef_dbl(doublex){returnx*x+x;}#definef(x)_Generic((x),int:f_int,double:f_dbl)(x)~.9996p(46341)//-2147432674int p(int x) {
  return x * x + x;
}
  • Statically typed for int
  • Workaround gymnastics for float
  • It does not cover overflows!

Example: My Favorite Polynomial (Attempt 2)

You turn to OCaml!

letfx=x*x+xlet_=(f5)(*30*)let_=(f3.14)(*typeerror*)(typea)(moduleN:NUMwithtypet=a)(:a)N.add(N.mul)fmoduleInt)fmoduleFloat)~12.9996let f x = x * x + x
  • Compile-time type error for float input
  • There is a fix, but...
  • Still a silent wrap-around for int overflow

Example: My Favorite Polynomial (Attempt 3)

You decide to try dynamic languages.

Scheme
(define (p x)  (+ (* x x) x)) (p 5)      ; 30(p 3.14)   ; ~12.9996(p 46341)  ; 2147534622
Python
def p(x):    return x * x + x p(5)      # 30p(3.14)   # ~12.9996p(46341)  # 2147534622

It just works! But what is the catch?

Performance of Dynamic Languages

What makes dynamic languages slower?

polynomial.scm
(define(px)(+(*xx)x))let(y(cond((fixnum?x)(or(fx*?xx)(##))((flonum?x)(fl*x(else(##*xx)))))(cond((and(fixnum?y)(fixnum?x))(or(fx+?yx)(##+yx)))((and(flonum?y)(flonum?x))(fl+yx))(else(##+yx)))))(define (p x)
  (+ (* x x) x))
  • static languages (C, OCaml) test types at compile time
  • dynamic languages (Scheme, JavaScript, Python) check them at run time
    • type checks
    • overflow checks
  • More flexible, but degrades performance

Related work

Trading flexibility for performance:

  • gradual typing (Siek & Taha 2006)

Object of this Thesis

How can an ahead-of-time compiler eliminate run-time checks, so that dynamic languages run as fast as static ones without losing their flexibility?

Table of Contents

  1. Background on Static Analysis

  2. Static Basic Block Versioning (SBBV)

  3. Lambda Versioning (ΛV)

  4. Technique Improvements

  5. Experimental Evaluation

  6. Future Work

Static Analysis

What is it and why does it fall short?

Intuition on Static Analysis

Even to the human eye, some tests beg to be removed.

findv.scm
(define(findvvpred)(letloop((i0))(cond((>=i(vector-lengthv))#f)((predvi)i)(else(loop(+i1))))))(vector-refv(findvvpred))if(vector?v)(##(fail))cond((fixnum?i)(or(fx+?i1)(##+i1)))((flonum?i)(fl+i1.0))(else(##))let((arg)(if(and(vector?v)(fixnum?arg)(fx>=arg0)(fx<arg(##vector-lengthv)))(##vector-refvarg)(fail)))(if(vector?v)fx>=)#f)(else(loop(fx+i1)))))(define (findv v pred)
  (let loop ((i 0))
    (cond
      ((>= i (vector-length v)) #f)
      ((pred v i) i)
      (else (loop (+ i 1))))))

(vector-ref v (findv v pred))
  • operators have implicit run-time checks
  • many of which are redundant
  • eliminating them can make the program more efficient
    • lift vector? out of the loop
    • fixnum arithmetic
    • eliminated bound checks
    • can this test be removed?

Related work

Inserting checks only where needed:

  • soft typing (Cartwright & Fagan 1991)

Static Analysis Overview

  • Based on abstract interpretation
  • Technique for sound approximation of program semantics
  • Executes on abstract values (sets of concrete values)

Related work

  • Abstract interpretation (Cousot & Cousot 1977)

Algorithm sketch:

  • Propagate abstract values through the control-flow graph
  • Start from an entry point with a generic context
  • A block's context is at least the union of its predecessors'
  • Branches narrow contexts flowing to their successors
  • Repeat until a fixed point is reached

Dynamic languages

  • Wide range of run-time behaviors: approximation is coarse.

Union of Incoming Contexts

∅ {0} {1} {2} ··· ··· [0, 1] ··· [1, 2] ··· [0, 2] ··· ··· [0, maxfix-1] [1, maxfix] [0, maxfix] ··· [1, maxfix+1] [0, maxfix+1] ··· ··· [0, ∞) (-∞, ∞)

Narrowing of Outgoing Contexts

  • gain information at conditional branches
    • arithmetic comparisons
    • type checks

Static Analysis of findv

expanded operators
(define(findvvpred)(letloop((i0))(cond((>=i(if(vector?v)(##vector-lengthv)(fail)))#f)((predvi)i)(else(loop(cond((fixnum?i)(or(fx+?i1)(##+i1)))((flonum?i)(fl+i1.0))(else(##+i1))))))))(let((arg(findvvpred)))(if(and(vector?v)(fixnum?arg)(fx>=arg0)(fx<arg(##vector-lengthv)))(##vector-refvarg)(fail)))fx>=(define (findv v pred)
  (let loop ((i 0))
    (cond
      ((>= i (if (vector? v) (##vector-length v)
                             (fail)))
       #f)
      ((pred v i) i)
      (else (loop (cond ((fixnum? i)
                         (or (fx+? i 1) (##+ i 1)))
                        ((flonum? i) (fl+ i 1.0))
                        (else (##+ i 1))))))))

(let ((arg (findv v pred)))
  (if (and (vector? v) (fixnum? arg)
           (fx>= arg 0) (fx< arg (##vector-length v)))
      (##vector-ref v arg) (fail)))

Static Basic Block Versioning

Unifying abstract interpretation and code duplication

Overview of Static Basic Block Versioning

Static analysis and dynamic languages

  • Tug of war between union and narrowing operations
  • Inputs exist that produce wide ranges of behaviors
  • Union wins over narrowing

Core idea

  • Delay the union operation
  • Duplicate basic blocks for different contexts
  • When a version limit is exceeded, perform a merge

Related work

AOT counterpart of:

  • Lazy BBV, in a JIT (Chevalier-Boisvert & Feeley 2015)

SBBV: A first example

polynomial.scm
(define(polynomialx)(+(*xx)1))let(y(cond((fixnum?x)(or(fx*?xx)(##))((flonum?x)(fl*xx))(else(##*xx)))))(cond((fixnum?y)(or(fx+?y1)(##+y)((flonum?y)(fl+y1.0))(else(##+y1)))))(define (polynomial x)
   (+ (* x x) 1))

SBBV: Behavior with loops

vector-print.scm
(define(vprintv)(letloop((i0))(when(<i(vector-lengthv))(display(vector-refvi))(loop(+i1)))))if(vector?v)(##vector-lengthv)(fail)))(display(if(and(vector?v)(fixnum?i)(fx>=i0)(fx<i(##)##(fail))cond((fixnum?i)(or(fx+?i1)(##+i1)))((flonum?i)(fl+i1.0))(else(##))(define (vprint v)
  (let loop ((i 0))
    (when (< i (vector-length v))
      (display (vector-ref v i))
      (loop (+ i 1)))))

SBBV: Back to findv

expanded operators
(define(findvvpred)(letloop((i0))(cond((>=i(if(vector?v)(##vector-lengthv)(fail)))#f)((predvi)i)(else(loop(cond((fixnum?i)(or(fx+?i1)(##+i1)))((flonum?i)(fl+i1.0))(else(##+i1))))))))(let((arg(findvvpred)))(if(and(vector?v)(fixnum?arg)(fx>=arg0)(fx<arg(##vector-lengthv)))(##vector-refvarg)(fail)))(define (findv v pred)
  (let loop ((i 0))
    (cond
      ((>= i (if (vector? v) (##vector-length v)
                             (fail)))
       #f)
      ((pred v i) i)
      (else (loop (cond ((fixnum? i)
                         (or (fx+? i 1) (##+ i 1)))
                        ((flonum? i) (fl+ i 1.0))
                        (else (##+ i 1))))))))

(let ((arg (findv v pred)))
  (if (and (vector? v) (fixnum? arg)
           (fx>= arg 0) (fx< arg (##vector-length v)))
      (##vector-ref v arg) (fail)))

SBBV Experimental Results

SBBV: Experimental Setup

Implemented in two production-ready Scheme compilers: Bigloo and Gambit

Bigloo 4.6a Gambit 4.9.4 Scheme benchmarks existing optimizations existing optimizations SBBV C C compiler SBBV C executable

19 benchmarks

12 macro, up to 11,740 lines

7 micro: fib, tak, ack...

8 configurations

No SBBV: own optimizations

Version limit 1 to 5, 10, 20

4 measures

Dynamic checks, program size

Execution and compile time

Bigloo and Gambit Are Already Fast

Execution time in seconds, SBBV with a limit of 2 versions (highlighted: fastest)

ProgramNode.jsBiglooBigloo + SBBVGambitGambit + SBBVChezRacket
almabench6.3115.6814.4614.6413.8617.6919.30
boyer40.317.407.228.216.498.0912.38
earley56.7514.9013.8310.8710.349.5324.73
leval18.427.536.4712.039.747.1616.96
maze10.077.476.706.755.7312.0112.12
bague305.0412.9011.1915.5412.9321.0119.33

SBBV Results: Dynamic Checks

SBBV Results: Program Size

SBBV Results: Execution Time

SBBV Results: Compile Time

Lambda Versioning

Whole-program ahead-of-time basic block versioning

Overview of Lambda Versioning

The missing puzzle piece of SBBV

  • Intraprocedural technique: limited propagation across abstraction barriers (functions)

Why?

  1. SBBV propagates information forward only.
    • Propagating from a function's exit site to the call site requires backward propagation.
  2. Call sites have a single return point.
    • This acts as a join point for all exit sites, losing context precision.

Solution

  1. Backward propagation from functions' exit sites to call sites.
  2. Duplicate entry points and return points to preserve context precision.

Framing the problem with an example

polynomial-square.scm
(define(polynomialx)(+(squarex)x))(define(squarex)(*xx))let((y))(cond((and(fixnum?y)(fixnum?(or(fx+?yx)(##+yx)))((and(flonum?y)(flonum?x))(fl+yx))(else(##+yx)))))cond((fixnum?x)(or(fx*?xx)(##)((flonum?x)(fl*xx))(else(##*xx))))(define (polynomial x)
  (+ (square x) x))

(define (square x)
  (* x x))
  • This conditional type information is lost at the return point
  • We want the analysis to define specialized call interfaces:
    • If the argument is a fixnum, provide one return point for fixnum and one for bignum
    • If the argument is a flonum, the result is always a flonum
    • If the argument is unknown, it could be a fixnum, flonum or another number, provide a return point for each

Core idea of Lambda Versioning

Core idea

  • Transform the source program into one with multi-entry/multi-return functions
  • Context at call sites propagates information to generate specialized entry points
  • Entry points track the exit sites they can reach
  • When a specialized exit site is discovered/removed, its call sites are notified and updated

Related work

Also duplicates entries and exits:

  • Interprocedural branch elimination, in C (Bodík, Gupta & Soffa 1997)
  • Interprocedural lazy BBV, in a JIT (Saleil & Feeley 2017)

Algorithm sketch

  • Associate entry points and exit sites (multi-source reachability algorithm)
  • New exit site \implies generate a specialized return point for its call sites
  • Merge removes an exit site \implies remove the corresponding return points
  • Return points duplication is governed version limit

Example: polynomial and square

(define (polynomial x)  (let ((y (square x)))    (cond ((and (fixnum? y) (fixnum? x))           (or (fx+? y x)               (##+ y x)))          ((and (flonum? y) (flonum? x))           (fl+ y x))          (else (##+ y x))))) (define (square x)  (cond ((fixnum? x)         (or (fx*? x x)             (##* x x)))        ((flonum? x) (fl* x x))        (else (##* x x)))) (polynomial (read))

Recursive example: Fibonacci

fib.scm
(define(fibn)(if(<=n1)n(+(fib(-n1))(fib(-n2)))))(fib(read))if(fixnum?n)(fx<=n1)(##)let((acond((fixnum?n)(or(fx-?n1)(##)((flonum?n)(fl-n1.0))(else(##-n1)))))(bcond((fixnum?n)(or(fx-?n2)(##-n2)))((flonum?n)(fl-n2.0))(else(##)(cond((and(fixnum?a)(fixnum?b))(or(fx+?ab)(##+ab)))((and(flonum?a)(flonum?b))(fl+ab))(else(##+ab))))))(define (fib n)
  (if (<= n 1)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

(fib (read))

Example: findv

findv.scm
(define(findvvpred)(letloop((i0))(cond((>=i(vector-lengthv))#f)((predvi)i)(else(loop(+i1))))))(vector-refv(findvvpred))if(vector?v)(##(fail))cond((fixnum?i)(or(fx+?i1)(##+i1)))((flonum?i)(fl+i1.0))(else(##))let((arg)(if(and(vector?v)(fixnum?arg)(fx>=arg0)(fx<arg(##vector-lengthv)))(##vector-refvarg)(fail)))(define (findv v pred)
  (let loop ((i 0))
    (cond
      ((>= i (vector-length v)) #f)
      ((pred v i) i)
      (else (loop (+ i 1))))))

(vector-ref v (findv v pred))

ΛV Experimental Results

ΛV: Experimental Setup

Implemented source to source: Scheme in, specialized Scheme out, run on Gambit

Scheme benchmarks CPS + lambda lifting ΛV SBBV (ΛV without interprocedural parts) specialized Scheme (hyperfunctions) Gambit + hyperfunction macro profiled run: count type checks

27 benchmarks

12 macro, over 400 lines

15 micro: fib, tak, sum...

60 configurations

3 heuristics, 2 operator forms

Version limit 1 to 10

3 measures

Type checks executed

Compile time, code duplication

Why No Execution Time?

  • Multi-return functions through CPS: one continuation per return point
  • No native implementation of hyperfunctions: a Scheme macro emulates them, slower than the source program
square, calling * as a hyperfunction
(define square  (hyperfunction    entries:      (any: A1        K: (fx→fx  fl→fl  fx|fl|bg→fx|fl|bg))      (fx: A2        K: (fx→fx  #f     fx→bg))      (fl: A3        K: (#f     fl→fl))    blocks:      A1: (lambda (K x)            (call *.any×arg[0]                  fx×arg[0]→fx: K[0]                  fl×arg[0]→fl: K[1]                  fx|fl|bg×arg[0]→fx|fl|bg: K[2]                  x x))      A2: ...      A3: ...))

ΛV Results: Type Checks

ΛV Results: Compile Time

ΛV Results: Code Duplication

Related work

  • Using Slicing to Identify Duplication in Source Code (Komondoor & Horwitz 2001)

Various Improvements

Three refinements.

Vector bound checks

intervals with symbolic bounds

  • A bound is ⟦v⟧-i: the length of vector v minus i
  • (fx< x len) narrows the index x to [0, ⟦v⟧-1]
  • The bound check of vector-ref is removed

Operators as functions

specializations are reused

  • SBBV requires inlined operators
  • ΛV supports + and * as functions
  • Each specialization is computed once

Merge heuristics

similarity vs arithmetic

  • similarity merges the closest contexts
  • arithmetic preserves pure arithmetic
  • arithmetic is better on all benchmarks

Vector Bound Check Elimination

Vector Support: New Rules

Intervals with symbolic bounds

  • A bound is written ⟦v⟧-i, with i ≥ 0: the length of vector v minus i

New rules

  • (##vector-length v) returns the singleton ⟦v⟧
    • ⟦v⟧: exactly the length of v, some fixnum in [0, maxfix]
  • (fx< x len) with len = ⟦v⟧ narrows the upper bound of x to ⟦v⟧-1 when true
  • (fx< x len) with x in [0, ⟦v⟧-1] and len == ⟦v⟧ is always true

Example: vector-ref

vector-simple.scm
(define(vector-safe-refvi)(if(and(fixnum?i)(>=i0)(<i(vector-lengthv)))(vector-refvi)#f))(vector-safe-ref#(123)(read))if(vector?v)(##vector-lengthv)(fail))))(if(and(vector?v)(fixnum?i)(fx>=i0)(fx<i(####(fail))(define (vector-safe-ref v i)
  (if (and (fixnum? i) (>= i 0) (< i (vector-length v)))
      (vector-ref v i)
      #f))

(vector-safe-ref #(1 2 3) (read))

Example: findv with vector bounds

findv.scm
(define(findvvpred)(letloop((i0))(cond((>=i(vector-lengthv))#f)((predvi)i)(else(loop(+i1))))))(vector-refv(findvvpred))if(vector?v)(##(fail))cond((fixnum?i)(or(fx+?i1)(##+i1)))((flonum?i)(fl+i1.0))(else(##))let((arg)(if(and(vector?v)(fixnum?arg)(fx>=arg0)(fx<arg(##vector-lengthv)))(##vector-refvarg)(fail)))(define (findv v pred)
  (let loop ((i 0))
    (cond
      ((>= i (vector-length v)) #f)
      ((pred v i) i)
      (else (loop (+ i 1))))))

(vector-ref v (findv v pred))

Operators as Functions

Operators as functions: the polynomial

p.scm
(define(px)(+(*xx)x))(p(read))(define(*ab)(cond((and(fixnum?a)(fixnum?b))(or(fx*?ab)(##*ab)))((and(flonum?a)(flonum?b))(fl*ab))(else(##*ab))))(define(+ab)(cond((and(fixnum?a)(fixnum?b))(or(fx+?ab)(##+ab)))((and(flonum?a)(flonum?b))(fl+ab))(else(##+ab))))(define (p x)
  (+ (* x x) x))

(p (read))
  • SBBV requires inlined operators
  • ΛV can support operators as functions

Operators as functions: compile time

Operators as functions re-use specializations. Inlined operators had to re-specialize at every site.

Merge Heuristics

Arithmetic vs Similarity

similarity

merge closest

arithmetic

prefer pure arithmetic

Empirical Comparison

  • arithmetic fares better on all benchmarks
  • generates optimal program for recursive functions such as fib
  • heuristic has a larger impact on ΛV than SBBV

Future Work

Native Multi-Return Functions

  • Efficient native implementation
  • Here is a work-in-progress

Related work

Explored some designs:

  • Multi-return function call (Shivers & Fisher 2004)
  • Entry and return point tables (Saleil & Feeley 2017)
  • Alternate returns (FORTRAN 77)
HVM: a VM for hyperfunctions
.hyper + nregs=3 nk=2 nfree=0  .entry 1 params=2 label=A   ; any x any  .entry 2 params=2 label=B   ; fx x fxA:  brntag r0, fixnum, GEN    brntag r1, fixnum, GENB:  fxadd? r2, r0, r1, GEN    ret   0, r2               ; fixnum resultGEN: add  r2, r0, r1    ret   1, r2               ; generic result .hyper fib nregs=4 nk=2 nfree=0  ...C2: ldclo r3                  ; fib(n-1)    calld r3, @fib, 2, K(D2, D1), (rv)

Heterogeneous Data Structures

  • Most remaining checks in benchmarks are on values read from heterogeneous structures (vector, pair, box, etc.)
  • Include mutability/escapability information in contexts to track the type of values within structures
(let ((v (make-vector 1 0)))  (##vector-set! v 0 42)  (##vector-ref v 0))

Built-in Constant Folding

(define (incr x) (+ x 1))(incr 0)

Conclusion

SBBV eliminates run-time checks

54–62%

fewer dynamic checks in Bigloo and Gambit with only 2 versions per block, about 10% faster.

ΛV removes nearly all type checks

1

type check per input, then none; ΛV specializes fib, ack and tak optimally.

whole-program specialization

AOT

code duplication to anticipate multiple run-time behaviors.

Remerciements

Merci à Marc Feeley et Manuel Serrano pour vos conseils et soutiens indéfectibles.

Merci au jury de thèse. Un merci particulier à Matthew Flatt.

Merci à toute la communauté du DIRO.

Merci à tous mes collègues et amis du LTP. 🤽

Merci à mes amis.

Merci à ma famille, pour votre soutien, votre amour et votre fierté.

A Dream of Islands, Philip Teece, p. 33