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.
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/.