Lec 15 - Baseline JIT compilers

Recap of JIT overview

- Three basic designs
  - baseline compiler, tracing compiler, optimizing compiler
- different tradeoffs:
  - code quality vs compile time
- Selecting what to compile
  - granularity: instruction, block, method, trace, module
  - Static hints: program or profiling run provides list of hints
  - Method/program characteristics: with or without certain features, size, etc
  - Dynamic selection: frequently executed, likely payoff
- Selecting when to compile
  - Lazy compilation: only compile when a unit (e.g. function) is first executed
  - Background compilation: concurrently compile using additional threads
  - Profiling techniques: sampling, counters, time
  - On-stack replacement: program stuck in a loop, not exiting function

- Single-pass compilation
  - Focus on simplicity (therefore correctness) and/or compile speed
  - Generally do not build a full intermediate representation of the bytecode or AST
  - AST-walking example
  - bytecode-by-bytecode
    - template JIT: copy code from per-bytecode-class code cache
      - copy & patch compilation: get templates from other compiler
    - by-hand JIT: manually write each of the cases
    - how faithfully to emulate interpreter data structures?
      - explicit operand stack?
      - frame layout: same as interpreter?
      - forward-pass optimizations:
        - register allocation
	- peephole optimizations
	- check elimination
    - incorporate any information from ICs?
  - can achieve better code quality via a form of abstract interpretation
    - basically, "running the code without running the code"
    - instead of concrete values, abstract values represent a possible set of runtime values
      - abstract values describe sets of values, properties of values
    - e.g. just the type, or the register in which the runtime value is stored
    - can also represent facts about a value that may be known, e.g. that it is a constant
    - abstract interpreters have to start with some unknown inputs
    - merges or loops in the control flow require approximation

  - Abstract values: represent symbolic sets of values
    - top element: the set of all values
    - bottom element: the empty set of values
    - constant: unitary abstract value
    - greatest lower bound(set of abs values) = intersection
    - least upper bound(set of abs values) = union

  - Example of abstract interpretation of Wasm code
                  top
		  /  \
  abs values = zero, not-zero
                 \    /
		 bottom


(module
  (func (param i32) (result i32)
    (local $y i32)
    (if (local.get 0)
      (then (local.set $y (i32.const 1)))
      (else (local.set $y (i32.const 2))))
    (local.get $y)
  )
)

With loops:

(module
  (func (param i32) (result i32)
    (local $y i32)
    (loop
      (if (local.get 0)
        (then (local.set $y (i32.const 1)))
        (else (local.set $y (i32.const 2))))
    )
    (local.get $y)
  )
)

  - Baseline compiler design for Wasm
    - abstract values include
      - register assignment for abstract values
    - abstract state may include
      - validity of interpreter state slot (stored)
      - checks performed, e.g. nullity of a ref
      - register state for metadata, like instance, mem0 base