[Compiler] 20. Modern Compiler Development and Applications

Source code    Frontend      LLVM IR      Middle End     LLVM IR      Backend       Machine code
                                        (Optimization)
C/C++   --> Clang    -->            -->           -->          --> x86
Rust    --> rustc    -->  Common IR -->  Common Opt -->  Common IR --> ARM
Swift   --> swiftc   -->            -->           -->          --> RISC-V
Fortran --> flang    -->            -->           -->          --> WebAssembly

; LLVM IR example: sum of two numbers
define i32 @add(i32 %a, i32 %b) {
entry:
  %result = add i32 %a, %b
  ret i32 %result
}

; Conditional example
define i32 @max(i32 %a, i32 %b) {
entry:
  %cmp = icmp sgt i32 %a, %b
  br i1 %cmp, label %then, label %else

then:
  br label %merge

else:
  br label %merge

merge:
  %result = phi i32 [%a, %then], [%b, %else]
  ret i32 %result
}

Key optimization passes:
- mem2reg: Promote memory accesses to registers (SSA construction)
- instcombine: Instruction combination optimization
- gvn: Global value numbering
- licm: Loop-invariant code motion
- indvars: Induction variable simplification
- loop-unroll: Loop unrolling
- inline: Function inlining
- sccp: Sparse conditional constant propagation
- dce: Dead code elimination
- simplifycfg: Control flow simplification

-O0: No optimization (for debugging)
-O1: Basic optimization (fast compilation)
-O2: Standard optimization (recommended for most cases)
-O3: Aggressive optimization (allows code size increase)
-Os: Code size optimization
-Oz: Extreme size optimization

History: Started by Richard Stallman in 1987
Languages: C, C++, Fortran, Go, Ada, etc.
Features:
- Nearly 40 years of history, extensive architecture support
- GIMPLE (intermediate repr) -> RTL (low-level repr) two-stage structure
- Powerful optimization (especially Fortran)
- GPL license

History: Started by Chris Lattner in 2003 (UIUC)
Clang: LLVM's C/C++/Objective-C frontend
Features:
- Modular library design
- Better error messages
- Faster compilation speed
- Apache 2.0 license (favorable for commercial use)
- Easy IDE integration (libclang, clangd)

AOT (Ahead-Of-Time) compilation:
  Source code -> [Compile] -> Machine code -> [Execute]
  Examples: C/C++ (gcc, clang), Rust, Go

JIT (Just-In-Time) compilation:
  Source code -> [Start with interpreter] -> [Detect hotspots] -> [Compile during execution] -> [Switch to optimized code]
  Examples: Java (HotSpot), JavaScript (V8), .NET (RyuJIT)

// 1. Profile-Guided Optimization (PGO)
// Optimization decisions based on information collected during execution
if (type == "string") {   // True 95% of the time
    // JIT: Optimize this branch (inline cache)
}

// 2. Speculative Optimization
// Run fast code as long as assumptions hold
// If assumptions fail, deoptimize and fall back to interpreter

// 3. Adaptive Optimization
// Optimize only hot code, run cold code in interpreter
// Balance between compilation time and execution time

Execution flow:
1. Start with bytecode interpreter
2. When call count exceeds threshold, C1 compiler (fast compilation, simple optimization)
3. If executed more, C2 compiler (slow compilation, aggressive optimization)

Tiered Compilation:
Level 0: Interpreter
Level 1: C1 (no profiling)
Level 2: C1 (limited profiling)
Level 3: C1 (full profiling)
Level 4: C2 (optimized code)

Execution flow:
1. Parser: JavaScript -> AST
2. Ignition (interpreter): AST -> bytecode execution
3. Sparkplug (baseline JIT): Fast machine code generation
4. Maglev (mid-tier JIT): Mid-level optimization
5. TurboFan (optimizing JIT): Aggressive optimization

Key techniques:
- Hidden Classes: Give structure to dynamically typed objects
- Inline Caching: Optimize property access
- Deoptimization: Fall back to interpreter when speculation fails

// Generic implementation strategies:

// 1. Monomorphization - Rust, C++
//    Generate separate code for each concrete type
//    Pros: Fast execution (inlining, specialized optimization)
//    Cons: Code size increase (code bloat)

// 2. Type Erasure - Java, Kotlin
//    Remove generic type information at compile time, process as Object
//    Pros: Small code size
//    Cons: Boxing/unboxing overhead, loss of runtime type information

// 3. Dictionary Passing - Haskell
//    Pass type class method tables as arguments
//    Pros: Small code size
//    Cons: Indirect call overhead

// Closure: A function that captures free variables

// Compilation handling:
// 1. Store captured variables in a struct (environment)
// 2. Closure = function pointer + environment pointer

// Example (pseudocode):
// Original:
// fn make_adder(x):
//     return fn(y): x + y

// After compilation:
// struct Env { int x; }
// int closure_fn(Env* env, int y) { return env->x + y; }
// Closure make_adder(int x) {
//     Env* env = alloc(Env);
//     env->x = x;
//     return (closure_fn, env);
// }

// Pattern matching compilation strategies:

// 1. Decision Tree
//    Test each pattern sequentially
//    Construct tree to minimize number of checks

// 2. Backtracking Automaton
//    Match multiple patterns simultaneously
//    Memory-efficient but complex to implement

// Example:
// match value {
//     (0, y) => ...,
//     (x, 0) => ...,
//     (x, y) => ...,
// }
//
// Decision tree:
//   value.0 == 0?
//     yes -> Pattern 1 (y = value.1)
//     no  -> value.1 == 0?
//              yes -> Pattern 2 (x = value.0)
//              no  -> Pattern 3 (x = value.0, y = value.1)

Key static analysis tools:
- Clang Static Analyzer: Path-sensitive analysis, memory bug detection
- Coverity: Commercial static analysis tool
- Infer (Meta): Memory safety checking on large codebases
- CodeQL (GitHub): Query-based code analysis

Detectable issues:
- Null pointer dereference
- Buffer overflow
- Memory leak
- Use-after-free
- Data races

Key sanitizers (LLVM/GCC supported):

AddressSanitizer (ASan):
- Detects memory access errors (buffer overflow, use-after-free)
- About 2x performance overhead
- Compile: clang -fsanitize=address

MemorySanitizer (MSan):
- Detects uninitialized memory reads
- About 3x performance overhead

ThreadSanitizer (TSan):
- Detects data races
- About 5-15x performance overhead

UndefinedBehaviorSanitizer (UBSan):
- Detects undefined behavior (integer overflow, invalid shifts, etc.)
- Minimal performance overhead

// Original code:
int a[10];
a[15] = 42;  // Buffer overflow!

// Code inserted by ASan (conceptual):
// 1. Set up "red zones" around memory
// 2. Check boundaries before every memory access
// 3. Report error if access touches red zone

// Runtime output:
// ERROR: AddressSanitizer: stack-buffer-overflow
// WRITE of size 4 at address ...
// [Stack trace]

// Control Flow Integrity (LLVM CFI):
// Verifies that calls through function pointers target only valid targets

// clang -fsanitize=cfi
// Verifies the signature of target functions at indirect calls

Traditional approach:
  PyTorch/TensorFlow -> Framework runtime -> cuDNN/MKL -> GPU/CPU

Compiler approach:
  Model definition -> Graph IR -> Optimization -> Code generation -> GPU/CPU/TPU/NPU

Advantages:
- Automate hardware-specific optimization
- Rapid support for new hardware
- Minimize memory access through operator fusion

XLA optimizations:
1. Operation Fusion
   - Combine multiple element-wise operations into a single kernel
   - Eliminate memory allocation for intermediate tensors

2. Layout Optimization
   - Optimize tensor memory layout for hardware

3. Constant Folding
   - Pre-compute tensor operations determinable at compile time

TVM stack:
  Frontend: Import PyTorch, TensorFlow, ONNX models
       |
  Relay IR: High-level graph representation
       |
  Relay optimization: Graph-level optimization (fusion, quantization, etc.)
       |
  Tensor IR (TIR): Low-level tensor operation representation
       |
  AutoTVM/Ansor: Automatic performance tuning (schedule search)
       |
  Code generation: CUDA, OpenCL, Metal, LLVM, etc.

- MLIR (Multi-Level IR): Multi-level IR framework in the LLVM project
  Unified compiler infrastructure supporting various abstraction levels

- Triton: Python-based language/compiler for GPU kernel writing
  Backend for PyTorch 2.0's torch.compile

- IREE: Compiler for deploying ML models to embedded/mobile environments

- StableHLO: Portable serialization format for ML models

Features:
- Stack-based virtual machine
- Static type system
- Memory safety (linear memory model)
- Can be used as compilation target from various languages
- Expanding use beyond browsers to servers and embedded

C/C++   -> Emscripten -> LLVM -> Wasm backend -> .wasm
Rust    -> rustc      -> LLVM -> Wasm backend -> .wasm
Go      -> TinyGo     -> LLVM -> Wasm backend -> .wasm
Kotlin  -> Kotlin/Wasm                       -> .wasm

;; WAT (WebAssembly Text Format) example: Fibonacci
(module
  (func $fib (param $n i32) (result i32)
    (if (i32.lt_s (local.get $n) (i32.const 2))
      (then (return (local.get $n)))
    )
    (i32.add
      (call $fib (i32.sub (local.get $n) (i32.const 1)))
      (call $fib (i32.sub (local.get $n) (i32.const 2)))
    )
  )
  (export "fib" (func $fib))
)

Key challenges:
1. GC integration: Reference types and GC support (Wasm GC proposal)
2. SIMD: Vector operation support (128-bit SIMD implemented)
3. Threads: Shared memory and atomic operations
4. Exception handling: Zero-cost exception handling
5. Tail calls: Support for functional languages

Optimization tools:
- Binaryen: Wasm-specific optimization (wasm-opt)
  - Dead code elimination
  - Function inlining
  - Constant folding
  - Code size optimization

Application areas:
- Serverless computing: Cloudflare Workers, Fastly Compute
- Container alternative: Docker + Wasm
- Plugin systems: Safe extension execution environments
- Embedded systems: Resource-constrained environments

1. AI-based Compiler Optimization
   - Reinforcement learning for optimization pass ordering
   - Neural network-based register allocation
   - LLM-based code analysis and optimization suggestions

2. Domain-Specific Compilers (DSL Compilers)
   - Compilers optimized for specific fields (ML, graphs, databases)
   - Halide (image processing), GraphIt (graph algorithms)

3. Verified Compilers
   - CompCert: Mathematically verified C compiler
   - Formally prove correctness of optimizations

4. Heterogeneous Computing Support
   - Compilers that manage CPU + GPU + FPGA + NPU together
   - Standards like SYCL, OneAPI (Intel)

5. Security-Embedded Compilers
   - Spread of memory-safe languages (Rust)
   - Utilization of hardware security features (ARM MTE, Intel CET)