Dataflow Analysis TODO
Concept
Dataflow analysis is a static-analysis technique that sets up equations for facts that hold at each point on a program's control-flow graph, then iterates to a fixed point over a lattice. Constant propagation attaches each variable a lattice value of "not yet known / constant c / not a constant," propagates it forward, and at merge points takes the meet of the two values — when different constants meet, the result drops to "not a constant." Dead-code elimination works in the opposite direction, using backward liveness analysis: if a definition of a variable is never used afterward and has no side effects, that definition is removed. The reason this approach is guaranteed to terminate is that the lattice has finite height and the transfer functions are monotone. Once code is in SSA form, each variable is defined exactly once, so the use-def relation is explicit, making both analyses considerably simpler and faster to implement.
Understanding why an optimizer removes some code and keeps other code — especially why optimization stops in front of an operation with side effects — is necessary to read generated bytecode or machine code and explain performance or gas differences.
Code & Formula
# 데이터플로 분석 — 상수 전파(전방향 격자 고정점)와 죽은 코드 제거(후방향 liveness)를 작은 IR에 적용한다.
# IR: (dest, op, args) 튜플의 리스트. op 는 "const" 또는 이항 연산자 이름.
program = [
("a", "const", 3),
("b", "const", 4),
("c", "+", ("a", "b")), # c = a + b = 7 (상수로 전파됨)
("d", "const", 10), # 이후 어디서도 쓰이지 않음 -> 죽은 코드
("e", "*", ("c", "b")), # e = c * b
("out", "+", ("e", 0)), # 반환값
]
def constant_propagate(program):
consts = {}
folded = []
for dest, op, args in program:
if op == "const":
consts[dest] = args
folded.append((dest, "const", args))
continue
a, b = args
va = consts.get(a) if isinstance(a, str) else a
vb = consts.get(b) if isinstance(b, str) else b
if va is not None and vb is not None:
val = va + vb if op == "+" else va * vb
consts[dest] = val
folded.append((dest, "const", val))
else:
folded.append((dest, op, args)) # NAC: 상수 아님, 그대로 둠
return folded, consts
def dead_code_eliminate(program, root="out"):
used = {root}
changed = True
while changed: # 고정점까지 반복 (후방향 liveness)
changed = False
for dest, op, args in program:
if dest in used and op != "const":
for a in args:
if isinstance(a, str) and a not in used:
used.add(a)
changed = True
return [instr for instr in program if instr[0] in used]
folded, consts = constant_propagate(program)
live = dead_code_eliminate(folded)
print("상수 전파 결과:", consts)
print("죽은 코드 제거 전:", [i[0] for i in folded])
print("죽은 코드 제거 후:", [i[0] for i in live], "(d 제거됨)")
docs/code/algorithms/algorithms-21.py
Exercise
Build a small IR by hand with about three basic blocks and a branch, tabulate the constant-propagation lattice values at each iteration until you reach a fixed point, and then remove the dead instructions.
Practical Connection
Compiling a Solidity contract with optimization turned on and off and comparing the assembly lets you see directly which SSTOREs and operations constant propagation and dead-code elimination actually removed to cut gas.
Where it lands in Jayverse
- CI: diff optimizer-on vs optimizer-off bytecode for DeFi and Verex contracts. Flag unexpectedly large SSTORE removals for manual review before merge, not just to explain gas after the fact.
- Auditor: check what dead-code elimination removed near any side-effect-bearing branch. A slash or liquidation path is exactly where a wrongly-elided store would be costly, so verify the "no side effects" assumption actually holds there.
- DeFi: compare optimized vs unoptimized assembly specifically on the slash/reward paths. These are the highest-cost places for constant propagation or DCE to have removed something it shouldn't have.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| fixed point | 고정점(더 이상 변하지 않는 상태) · 반복 계산이 수렴하는 지점을 말할 때. "iterates to a fixed point over a lattice." |
| the meet | (격자 이론에서) 만남 연산 · 두 값을 합쳐 하나의 값으로 만들 때. "takes the meet of the two values" |
| drop to | (값이) ~로 떨어지다, 낮아지다 · 상태가 더 낮은·불확실한 값으로 바뀔 때. "the result drops to 'not a constant'" |
| have no side effects | 부작용(부수 효과)이 없다 · 어떤 코드가 다른 상태를 바꾸지 않을 때. "and has no side effects" |
| guaranteed to terminate | 종료가 보장된 · 알고리즘이 무한루프 없이 끝남이 증명될 때. "is guaranteed to terminate" |
| finite height | 유한한 높이 · 격자 구조가 무한하지 않고 유한한 단계로 끝날 때. "the lattice has finite height" |
| monotone | 단조(증가/감소)인 · 함수가 방향을 바꾸지 않고 변할 때. "the transfer functions are monotone." |
| in front of | ~바로 앞에서 · 최적화가 특정 지점 직전에서 멈출 때. "optimization stops in front of an operation" |
| IR | 중간 표현(Intermediate Representation) · 컴파일러가 소스코드와 기계어 사이에 쓰는 내부 표현 형태. "Build a small IR by hand with about three" |
| SSA | 정적 단일 대입 형태(Static Single Assignment) · 각 변수가 한 번만 정의되는 컴파일러 중간표현, 데이터흐름 분석을 단순화함. "Once code is in SSA form, each variable is" |
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/.