IR and SSA Form TODO

Algorithms · Day 20 / 100 · B. Compilers, Runtimes & VMs (Day 20-35)

Concept

An IR (intermediate representation) sits between the source language and the target machine so that optimization and code-generation logic scales as (languages + targets) instead of (languages x targets). SSA (static single assignment) is an IR form in which every variable is assigned exactly once; at points where control flow merges, a phi function picks a value depending on which predecessor block execution came from. Because every use points to a unique definition, def-use relationships are explicit in the representation itself, which makes optimizations like constant propagation, dead-code elimination, and common-subexpression elimination simpler without a separate dataflow analysis. Where to place phi functions is computed from the dominance frontier, derived from the dominance relation; just before register allocation, an out-of-SSA pass lowers phi nodes into copy instructions.

Modern optimization in LLVM, the Go compiler, most JITs, and even Solidity's Yul-based IR pipeline all run on top of SSA, so reading why some code gets optimized and some doesn't requires thinking in SSA.

Code & Formula

# IR과 SSA 형식 — 분기가 있는 프로그램을 SSA로 변환하고 phi 노드로 값을 합류시킨다.
# 원본: x=1; if cond: x=2; y = x+1   →  SSA: x1=1; (분기) x2=2; x3=phi(x1,x2); y=x3+1

def original(cond):
    x = 1
    if cond:
        x = 2
    y = x + 1
    return y

def ssa_form(cond):
    x1 = 1                          # entry 블록에서의 정의
    x2 = None
    if cond:
        x2 = 2                      # then 블록에서의 새 정의 (재대입이 아니라 새 이름)
        pred = "then"
    else:
        pred = "entry"
    # 합류 지점의 phi: 어느 선행 블록에서 왔는지에 따라 값을 고른다
    x3 = x2 if pred == "then" else x1
    y = x3 + 1
    return y

for cond in (True, False):
    o, s = original(cond), ssa_form(cond)
    print(f"cond={cond}: original={o}, ssa={s}, 일치={o == s}")
    assert o == s

docs/code/algorithms/algorithms-20.py

Exercise

Hand-convert a short function containing a branch and a loop into SSA form, placing the phi nodes yourself, then compare it side by side with an actual compiler's SSA dump (e.g., Go's GOSSAFUNC output).

Practical Connection

When judging why a particular construct in solc's optimizer settings or Go runtime code ends up using more instructions and more gas, looking at what folds away and what survives at the IR level — not the source level — is the most reliable evidence.

If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.

한국어

IR과 SSA 형식 TODO

Algorithms · Day 20 / 100 · B. 컴파일러·런타임·VM (Day 20–35)

최적화가 가능해지는 표현

개념

IR은 소스 언어와 타깃 기계 사이에 두는 중간 표현으로, 최적화와 코드 생성 로직을 언어 수 곱하기 타깃 수가 아니라 언어 수 더하기 타깃 수로 줄이기 위한 계층이다. SSA는 모든 변수가 정확히 한 번만 정의되도록 이름을 재부여한 IR 형식이며, 제어 흐름이 합류하는 지점에서는 어느 선행 블록에서 왔는지에 따라 값을 고르는 phi 함수를 둔다. 각 사용 지점이 유일한 정의를 가리키므로 def-use 관계가 표현 자체에 명시되고, 상수 전파·죽은 코드 제거·공통 부분식 제거 같은 최적화가 별도 자료 흐름 분석 없이도 단순해진다. phi를 어디에 넣을지는 지배 관계에서 나오는 dominance frontier로 계산하며, 레지스터 할당 직전에 phi를 복사 명령으로 풀어내는 out-of-SSA 단계를 거친다.

LLVM, Go 컴파일러, 대부분의 JIT, 그리고 Solidity의 Yul 기반 IR 파이프라인까지 현대 최적화가 전부 SSA 위에서 돌아가므로, 어떤 코드가 왜 최적화되고 왜 안 되는지 읽으려면 SSA 사고가 필요하다.

코드 · 수식

# IR과 SSA 형식 — 분기가 있는 프로그램을 SSA로 변환하고 phi 노드로 값을 합류시킨다.
# 원본: x=1; if cond: x=2; y = x+1   →  SSA: x1=1; (분기) x2=2; x3=phi(x1,x2); y=x3+1

def original(cond):
    x = 1
    if cond:
        x = 2
    y = x + 1
    return y

def ssa_form(cond):
    x1 = 1                          # entry 블록에서의 정의
    x2 = None
    if cond:
        x2 = 2                      # then 블록에서의 새 정의 (재대입이 아니라 새 이름)
        pred = "then"
    else:
        pred = "entry"
    # 합류 지점의 phi: 어느 선행 블록에서 왔는지에 따라 값을 고른다
    x3 = x2 if pred == "then" else x1
    y = x3 + 1
    return y

for cond in (True, False):
    o, s = original(cond), ssa_form(cond)
    print(f"cond={cond}: original={o}, ssa={s}, 일치={o == s}")
    assert o == s

docs/code/algorithms/algorithms-20.py

연습

분기와 루프를 각각 포함한 짧은 함수를 손으로 SSA로 변환해 phi 노드를 배치하고, 같은 코드를 실제 컴파일러의 SSA 덤프(예: Go의 GOSSAFUNC 출력)와 나란히 비교하라.

실무 · Verex 연결

solc 최적화 설정이나 Go 런타임 코드에서 특정 구문이 왜 더 많은 명령어와 가스를 쓰는지 판단할 때, 소스가 아니라 IR 수준에서 무엇이 접히고 무엇이 남았는지 보는 것이 가장 확실한 근거가 된다.

공부한 날 원본 커리큘럼(docs/knowledge/dev-100-curriculum.md)의 이 줄에 노트 링크와 ✅ 를 붙이면, 이 자리는 노트 본문으로 바로 이어집니다. 노트 없이 이 페이지에 바로 적어도 됩니다 — 다만 다시 생성하면 덮어쓰이므로, 남길 글은 docs/algorithms/ 의 마크다운으로 쓰는 편이 안전합니다.