Split View: 컴파일러/인터프리터 설계 완전 정복: 파서부터 LLVM, AI 컴파일러(TVM/XLA)까지

Source Code
    ↓  Lexical Analysis (Lexing)
Token Stream
    ↓  Syntactic Analysis (Parsing)
AST (Abstract Syntax Tree)
    ↓  Semantic Analysis
Annotated AST
    ↓  IR Generation
Intermediate Representation (IR)
    ↓  Optimization Passes
Optimized IR
    ↓  Code Generation
Machine Code / Assembly

import re
from enum import Enum, auto
from dataclasses import dataclass
from typing import List, Optional

class TokenType(Enum):
    NUMBER   = auto()
    IDENT    = auto()
    PLUS     = auto()
    MINUS    = auto()
    STAR     = auto()
    SLASH    = auto()
    LPAREN   = auto()
    RPAREN   = auto()
    ASSIGN   = auto()
    SEMICOL  = auto()
    LET      = auto()
    EOF      = auto()

@dataclass
class Token:
    type: TokenType
    value: str
    line: int

KEYWORDS = {'let': TokenType.LET}

TOKEN_PATTERNS = [
    (r'\d+(\.\d+)?',  TokenType.NUMBER),
    (r'[a-zA-Z_]\w*', TokenType.IDENT),
    (r'\+',           TokenType.PLUS),
    (r'-',            TokenType.MINUS),
    (r'\*',           TokenType.STAR),
    (r'/',            TokenType.SLASH),
    (r'\(',           TokenType.LPAREN),
    (r'\)',           TokenType.RPAREN),
    (r'=',            TokenType.ASSIGN),
    (r';',            TokenType.SEMICOL),
]

def tokenize(source: str) -> List[Token]:
    tokens = []
    line = 1
    pos = 0
    while pos < len(source):
        if source[pos] in ' \t\r':
            pos += 1
            continue
        if source[pos] == '\n':
            line += 1
            pos += 1
            continue
        matched = False
        for pattern, ttype in TOKEN_PATTERNS:
            m = re.match(pattern, source[pos:])
            if m:
                value = m.group(0)
                if ttype == TokenType.IDENT and value in KEYWORDS:
                    ttype = KEYWORDS[value]
                tokens.append(Token(ttype, value, line))
                pos += len(value)
                matched = True
                break
        if not matched:
            raise SyntaxError(f"Unexpected character '{source[pos]}' at line {line}")
    tokens.append(Token(TokenType.EOF, '', line))
    return tokens

# Example usage
src = "let x = 10 + 20 * 3;"
for tok in tokenize(src):
    print(tok)

from dataclasses import dataclass
from typing import Union

# AST node definitions
@dataclass
class NumberLit:
    value: float

@dataclass
class Identifier:
    name: str

@dataclass
class BinOp:
    op: str
    left: 'Expr'
    right: 'Expr'

@dataclass
class LetStmt:
    name: str
    value: 'Expr'

Expr = Union[NumberLit, Identifier, BinOp]

# Recursive Descent Parser
class Parser:
    def __init__(self, tokens: List[Token]):
        self.tokens = tokens
        self.pos = 0

    def peek(self) -> Token:
        return self.tokens[self.pos]

    def consume(self, expected: Optional[TokenType] = None) -> Token:
        tok = self.tokens[self.pos]
        if expected and tok.type != expected:
            raise SyntaxError(f"Expected {expected}, got {tok.type} at line {tok.line}")
        self.pos += 1
        return tok

    def parse_let(self) -> LetStmt:
        self.consume(TokenType.LET)
        name = self.consume(TokenType.IDENT).value
        self.consume(TokenType.ASSIGN)
        expr = self.parse_expr()
        self.consume(TokenType.SEMICOL)
        return LetStmt(name=name, value=expr)

    def parse_expr(self) -> Expr:
        return self.parse_additive()

    def parse_additive(self) -> Expr:
        left = self.parse_multiplicative()
        while self.peek().type in (TokenType.PLUS, TokenType.MINUS):
            op = self.consume().value
            right = self.parse_multiplicative()
            left = BinOp(op=op, left=left, right=right)
        return left

    def parse_multiplicative(self) -> Expr:
        left = self.parse_primary()
        while self.peek().type in (TokenType.STAR, TokenType.SLASH):
            op = self.consume().value
            right = self.parse_primary()
            left = BinOp(op=op, left=left, right=right)
        return left

    def parse_primary(self) -> Expr:
        tok = self.peek()
        if tok.type == TokenType.NUMBER:
            self.consume()
            return NumberLit(value=float(tok.value))
        if tok.type == TokenType.IDENT:
            self.consume()
            return Identifier(name=tok.value)
        if tok.type == TokenType.LPAREN:
            self.consume()
            expr = self.parse_expr()
            self.consume(TokenType.RPAREN)
            return expr
        raise SyntaxError(f"Unexpected token {tok}")

# Source: x = (a + b) * (c - d)
t1 = a + b
t2 = c - d
x  = t1 * t2

# Original code
x = 1
x = x + 2    # x assigned twice

# SSA form
x_1 = 1
x_2 = x_1 + 2

if cond:
    x_1 = 10
else:
    x_2 = 20
# Merge point
x_3 = phi(x_1, x_2)

; Function: int add(int a, int b)
define i32 @add(i32 %a, i32 %b) {
entry:
  %result = add i32 %a, %b
  ret i32 %result
}

; Branching with SSA phi nodes
define i32 @max(i32 %a, i32 %b) {
entry:
  %cmp = icmp sgt i32 %a, %b      ; signed greater-than
  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
}

# Before
x = 2 * 3 + 4

# After (compiler computes at build time)
x = 10

def constant_fold(node):
    """Simple constant folding pass."""
    if isinstance(node, BinOp):
        left  = constant_fold(node.left)
        right = constant_fold(node.right)
        if isinstance(left, NumberLit) and isinstance(right, NumberLit):
            ops = {
                '+': lambda a, b: a + b,
                '-': lambda a, b: a - b,
                '*': lambda a, b: a * b,
                '/': lambda a, b: a / b,
            }
            return NumberLit(value=ops[node.op](left.value, right.value))
        return BinOp(op=node.op, left=left, right=right)
    return node

def dead_code_eliminate(stmts, used_vars):
    """Remove assignments to variables that are never read."""
    live = set()
    # Backward pass: collect used variables
    for stmt in reversed(stmts):
        if isinstance(stmt, LetStmt):
            if stmt.name in used_vars or stmt.name in live:
                live.update(collect_vars(stmt.value))
    return [s for s in stmts
            if not isinstance(s, LetStmt) or s.name in live]

// Original — 4 iterations with loop overhead
for (int i = 0; i < 4; i++) {
    a[i] = b[i] + c[i];
}

// Unrolled — zero loop overhead, can be vectorized
a[0] = b[0] + c[0];
a[1] = b[1] + c[1];
a[2] = b[2] + c[2];
a[3] = b[3] + c[3];

// Before
inline int square(int x) { return x * x; }
int y = square(5);

// After inlining (then constant folding)
int y = 25;

; C: int add(int a, int b) { return a + b; }
; Linux System V ABI: args in rdi, rsi; return in rax

add:
    push    rbp
    mov     rbp, rsp
    mov     DWORD PTR [rbp-4], edi
    mov     DWORD PTR [rbp-8], esi
    mov     edx, DWORD PTR [rbp-4]
    mov     eax, DWORD PTR [rbp-8]
    add     eax, edx
    pop     rbp
    ret

; With -O2 (optimized)
add:
    lea     eax, [rdi + rsi]    ; single instruction!
    ret

import numpy as np
from numba import njit, prange
import time

# Pure Python baseline
def matmul_python(A, B):
    N = A.shape[0]
    C = np.zeros((N, N))
    for i in range(N):
        for j in range(N):
            for k in range(N):
                C[i, j] += A[i, k] * B[k, j]
    return C

# Numba JIT with parallelism
@njit(parallel=True)
def matmul_numba(A, B):
    N = A.shape[0]
    C = np.zeros((N, N))
    for i in prange(N):       # parallel loop
        for j in range(N):
            for k in range(N):
                C[i, j] += A[i, k] * B[k, j]
    return C

N = 256
A = np.random.rand(N, N).astype(np.float32)
B = np.random.rand(N, N).astype(np.float32)

# First call triggers compilation (warmup)
_ = matmul_numba(A, B)

t0 = time.perf_counter()
C_py = matmul_python(A, B)
print(f"Python:     {time.perf_counter()-t0:.3f}s")

t0 = time.perf_counter()
C_nb = matmul_numba(A, B)
print(f"Numba JIT:  {time.perf_counter()-t0:.4f}s")
# Typical result: Python ~30s vs Numba ~0.01s

import torch
import torch.nn as nn

class SimpleNet(nn.Module):
    def __init__(self):
        super().__init__()
        self.fc1 = nn.Linear(128, 256)
        self.fc2 = nn.Linear(256, 10)
        self.relu = nn.ReLU()

    def forward(self, x):
        return self.fc2(self.relu(self.fc1(x)))

model = SimpleNet().cuda()
x = torch.randn(32, 128).cuda()

# Apply torch.compile
compiled = torch.compile(model, mode='max-autotune')

# First call: compilation happens (takes a few seconds)
out = compiled(x)

# Subsequent calls: reuse compiled kernels
for _ in range(100):
    out = compiled(x)

import torch._dynamo as dynamo

def my_func(x, y):
    return torch.sin(x) + torch.cos(y)

# Inspect the captured FX graph
explanation = dynamo.explain(my_func)(
    torch.randn(4), torch.randn(4)
)
print(explanation.graphs[0].print_tabular())
# opcode    | name   | target       | args
# ----------|--------|--------------|----------
# call_fn   | sin    | torch.sin    | (x,)
# call_fn   | cos    | torch.cos    | (y,)
# call_fn   | add    | operator.add | (sin, cos)
# output    | output | output       | (add,)

import tvm
from tvm import relay
import torch, torchvision
import numpy as np

# Start from a PyTorch model
model = torchvision.models.resnet18(pretrained=False).eval()
input_shape = [1, 3, 224, 224]
trace_input = torch.randn(input_shape)

# Trace to TorchScript, then import into TVM Relay IR
scripted = torch.jit.trace(model, trace_input)
mod, params = relay.frontend.from_pytorch(scripted, [("input0", input_shape)])

target = tvm.target.Target("cuda")

# AutoScheduler: search for optimal kernel parameters
from tvm import auto_scheduler
tasks, task_weights = auto_scheduler.extract_tasks(
    mod["main"], params, target
)
tuner = auto_scheduler.TaskScheduler(tasks, task_weights)
tune_option = auto_scheduler.TuningOptions(
    num_measure_trials=200,
    runner=auto_scheduler.LocalRunner(repeat=10),
    measure_callbacks=[auto_scheduler.RecordToFile("tuning.json")],
)
tuner.tune(tune_option)

# Compile with best-found schedules
with auto_scheduler.ApplyHistoryBest("tuning.json"):
    with tvm.transform.PassContext(opt_level=3):
        lib = relay.build(mod, target=target, params=params)

print("TVM compilation complete!")

# Without fusion: 3 separate GPU kernel launches
y1 = conv2d(x)        # kernel 1  — write to HBM
y2 = batch_norm(y1)   # kernel 2  — read+write HBM
y3 = relu(y2)         # kernel 3  — read+write HBM

# With fusion: 1 kernel launch
y3 = fused_conv_bn_relu(x)
# Intermediate results stay in L1/L2 cache
# HBM bandwidth saved = significant speedup

import jax
import jax.numpy as jnp

@jax.jit
def compute(x, W, b):
    # XLA automatically fuses: matmul + add + relu
    return jax.nn.relu(x @ W + b)

x = jnp.ones((32, 128))
W = jnp.ones((128, 256))
b = jnp.zeros(256)

# First call: XLA compilation
result = compute(x, W, b)
print(result.shape)  # (32, 256)

TensorFlow Graph
     ↓  TF Dialect
MLIR HLO Dialect
     ↓  Linalg Dialect
Loop Nest IR
     ↓  Affine Dialect
Affine Loop IR
     ↓  LLVM Dialect
LLVM IR
     ↓
Machine Code