JIT Compiling Domain Specific Languages

• Survey of DSLs
• LLVM
• Implementing a Compiled DSL

Domain Specific Languages are programming languages biased towards a particular problem domain.

• Expressive
• Share language with domain experts
• Hide implementation details
• Emphasis on meaning

The embedded language technique dates back to 1966, in Peter Landin's The Next 700 Programming Languages

• Represent domain concepts
• Use the language
• In identifiers
• In program structure

Interpreted or compiled?

• Easiest to implement
• Easiest to maintain
• Good choice in absence of performance requirements

• Greater initial overhead
• Generate code in some target language
• JIT compilation
• Generate machine code directly

External DSLs define a custom syntax and semantics.

Embedded DSLs reuse the syntax and semantics of their host language.

• Csound
• ChucK
• Faust
• ...

• A reusable compiler backend
• An umbrella for compiler tools
• Clang
• MC
• compiler-rt
• KLEE

• Generate IR
• Run Passes
• Generate Code

• Single Static Assignment
• Type System
• Modules
• Metadata
• Target Independent
• Excellent Documentation

; ModuleID = 'Factorial'

define i64 @fac(i64) {
; <label>:1
  %2 = icmp eq i64 %0, 1                ; <i1> [#uses=1]
  br i1 %2, label %7, label %3

; <label>:3                             ; preds = %1
  %4 = sub i64 %0, 1                    ; <i64> [#uses=1]
  %5 = call i64 @fac(i64 %4)            ; <i64> [#uses=1]
  %6 = mul i64 %0, %5                   ; <i64> [#uses=1]
  br label %7

; <label>:7                             ; preds = %3, %1
  %8 = phi i64 [ 1, %1 ], [ %6, %3 ]    ; <i64> [#uses=1]
  ret i64 %8
}

• Built-in passes
• Instruction Combining
• Loop Unrolling
• ...
• Custom pass API

• Define queue of passes
• Passes may be repeated
• Run at module or function level

• Promote Memory To Register
• Combine Redundant Instructions
• Reassociate Expressions
• Global Value Numbering
• Dead Store Elimination
• Simplify Control Flow Graph
• ...

• C++ classes
• C bindings (incomplete)
• ll
• bc

• Ruby
• OCaml
• Haskell
• Python
• C bindings are versatile

• Written in pure Ruby
• Interfaces to C via FFI

• IR Builder
• Pass Manager
• Execution Engine

mod = LLVM::Module.create("Factorial")

mod.functions.add(
  "fac",
  [LLVM::Int], LLVM::Int
) do |fac, p0|
  entry   = fac.basic_blocks.append
  recur   = fac.basic_blocks.append
  result  = fac.basic_blocks.append
  # continued →
end

  builder = LLVM::Builder.create
  
  builder.position_at_end(entry)
  builder.cond(
    builder.icmp(:eq, p0, LLVM::Int(1)),
    result, recur)
  
  builder.position_at_end(recur)
  fac_call = builder.call(fac,
               builder.sub(p0, LLVM::Int(1)))
  fac_result = builder.mul(p0, fac_call)
  builder.br(result)
  
  builder.position_at_end(result)
  builder.ret(
    builder.phi(LLVM::Int,
      LLVM::Int(1), entry,
      fac_result,   recur))

; ModuleID = 'Factorial'

define i64 @fac(i64) {
; <label>:1
  %2 = icmp eq i64 %0, 1                ; <i1> [#uses=1]
  br i1 %2, label %7, label %3

; <label>:3                             ; preds = %1
  %4 = sub i64 %0, 1                    ; <i64> [#uses=1]
  %5 = call i64 @fac(i64 %4)            ; <i64> [#uses=1]
  %6 = mul i64 %0, %5                   ; <i64> [#uses=1]
  br label %7

; <label>:7                             ; preds = %3, %1
  %8 = phi i64 [ 1, %1 ], [ %6, %3 ]    ; <i64> [#uses=1]
  ret i64 %8
}

• Migrate to LLVM 2.7
• Binary distribution
• Bitcode reader/writer
• C backend
• Clang bindings

• Embedded, JIT compiled DSL
• Realtime execution
• Events for control
• Voices for synthesis

Time      = ℝ
Amplitude = ℝ
Sound     = Time → Amplitude

Time      = Float
Amplitude = Float
Sound     = Time → Amplitude

• Defines constants
• Leverages host language
• Untyped
• Easy to compile

• Techniques vary by host language
• Tagged unions
• Class hierarchy
• Algebraic data type

AST = FloatLit Float
    | FAdd AST AST
    | ...
    | Cos AST
    | ...
    | IntLit Int
    | ...

• Code generator is a semantic function
• Traverse AST from bottom up, making LLVM IR builder calls
• Visitor pattern
• Fold

• Semantic function maps DSL terms to their meaning

 E = Int z | E + E
〚Int z〛= z
〚x + y〛=〚x〛+〚y〛

An embedded DSL's user interface

• Integrate with host language
• Catch type errors early
• Facilitate construction of programs in abstract syntax

• Don't generate everything
• Reuse support code
• C calling convention is ubiquitous:
• Call C from generated code
• Call generated code from C

• http://llvm.org/
• http://github.com/jvoorhis
• http://jvoorhis.com/
• @jvoorhis