Fold Constants, Build a CFG, Place φ Nodes

Goal

You fold the constants of the AST and strip away decided branches, build basic blocks and a CFG from module 6's chunk and delete unreachable code. From that graph, you compute dominators and dominance frontiers to work out the blocks where SSA's φ goes. The optimized program must produce the same result while executing fewer instructions.

Why it matters

In optimization, "what you must not do" comes before "what you can do." If you precompute a division by zero, or delete code without reconnecting the jumps, you get a program that is fast but wrong. And the CFG, dominators, and SSA are the data structures on which all the optimizations of practical compilers stand, so what you compute by hand here becomes the eye that reads LLVM IR in module 10.

The rules

fold(식)          양쪽이 리터럴이면 계산해 리터럴 하나로(64비트 감기·0 쪽 나눗셈은 인터프리터와 같다).
                  0 으로 나누기·나머지, 음수 지수, 타입이 다른 ==, 타입이 맞지 않는 연산은 접지 않는다.
                  접은 값은 원래 노드의 위치를 물려받는다. 원래 트리는 바꾸지 않는다(copy 로 새 노드).
                  && 의 왼쪽이 false(|| 는 true)면 그 왼쪽 리터럴, 반대면 오른쪽을 접은 것.
fold_program      식을 모두 접고: if(true) → then 블록, if(false) → else(없으면 문장째 삭제), while(false) → 삭제.
leaders(code)     0, 점프 목적지(코드 끝이 아니면), 점프·RETURN 바로 다음(끝이 아니면) — 오름차순
basic_blocks      [[시작, 끝)] · cfg(code) → {"blocks", "succ"}: 흘러내리는 쪽 먼저, 점프하는 쪽 다음
                  JUMP 는 흘러내리지 않고 RETURN 은 다음이 없다. 코드 끝으로 가는 것은 적지 않는다.
remove_unreachable  입구(블록 0)에서 닿지 않는 블록을 지우고, 남은 점프의 오프셋을 새 자리로 다시 잰다.
                  상수 풀의 함수 청크도 같은 방법으로. 이름·인자 수·상수 풀은 그대로.
dominators(succ)  블록마다 지배자(자기 포함, 오름차순). 닿지 않는 블록은 []. 고정점까지 되풀이.
idom(succ)        직속 지배자(입구와 닿지 않는 블록은 None)
dominance_frontier / phi_blocks(succ, {변수: [정의 블록]})  반복 지배 경계로 φ 가 필요한 블록(오름차순)
optimize_source   (전 청크, 뒤 청크, 오류) = 파싱·의미 분석 → compile(원래) / compile(fold_program) → remove_unreachable

Steps

1. Fill in fold(n) in /root/mini/opt.py — the grader compares the folded trees and node positions of fixed expressions and 250 random ones.
2. Fill in fold_stmt, fold_list, and fold_program — the execution results before and after folding must be the same.
3. Fill in JUMPS, jump_target, leaders, and basic_blocks.
4. Fill in cfg(code).
5. Fill in reachable(succ) and remove_unreachable(chunk).
6. Fill in dominators(succ) and idom(succ).
7. Fill in dominance_frontier(succ) and phi_blocks(succ, defs).
8. Fill in optimize_source(src), and for each program in the opt list of /opt/fixtures/mini/programs/manifest.json, run the before and after chunks on the VM and write {이름: {"before": 명령 수, "after": 명령 수, "same_output": true/false}} into /root/mini/opt_report.json (the placeholders are the program name and the instruction counts).

Notes

• python3 /root/mini/mini.py opt /opt/fixtures/mini/programs/const.mini shows the instruction counts before and after optimization.
• The files up to the compiler and VM are laid out when you start the lab.
• Common mistakes: the compiler dying while folding a division by zero, discarding the position of a folded value, folding true && x to true, leaving the jump offsets as they are after deleting, treating JUMP as falling through too, and widening φ only once.
• The session starts at 60 minutes and you can extend it with the +time button, and when it ends /root/mini disappears.

Fold constants — starting with what must not be folded

Copy the node with copy.copy and fold the children first. Compute only when both sides are Int or Bool literals and the types match, but if the divisor is 0 or the exponent is negative, leave it as it is. Make the new literal with the original node's line and col.

Strip away decided branches

For each statement, fold its expressions. If the condition of an if becomes a Bool literal, run fold_stmt again on the chosen branch (it is a Block, so the scope remains), and if there is no branch, delete the statement by returning None. fold_list discards None. Do not forget function bodies.

Basic blocks

Put 0 in the set of leaders, and for each instruction, if it is a jump and its destination (i + 1 + offset) is inside the code, add it, and if it is a jump or RETURN and the next one (i + 1) is inside the code, add it. If you pair up the sorted leaders with their neighbors, you get [start, end).

The control flow graph

Look at the last instruction of the block. If it is RETURN there is no next; if it is JUMP, one destination block; if it is a conditional jump, the fall-through block (the block whose start is the end position) and the destination block — just one if they are the same. Anything else is one fall-through block. If the destination is the end of the code, do not record it.

Delete unreachable code and reconnect the jumps

Collect the blocks reachable from block 0 by following succ. Build a table from the old position to the new position of the instructions you keep (with the end of the code as the new end too), and re-measure each jump as new offset = new destination - (new position + 1). The dict in the constant pool does the same thing recursively.

Dominators

Start every reachable block as "all reachable blocks" and only the entrance as {0}. For blocks that are not the entrance, replace with the intersection of the dominators of the predecessor blocks (reachable ones only) plus itself, repeating until nothing changes during a full pass. The immediate dominator is the closest one among the strict dominators (the one whose dominator set is largest).

Dominance frontiers and φ placement

For each block b with two or more predecessors, starting from a predecessor p, climb the chain of immediate dominators until you reach b's immediate dominator, and put b in the frontier of each block you pass. For φ placement, start from the frontiers of the defining blocks, count the newly placed φ blocks as definitions too, and keep widening until it stops growing.

Measure before and after optimization

optimize_source compiles the same program twice — once as it is and once after fold_program and then remove_unreachable. The report writes the executed from running the two chunks with run_chunk, and whether the output and error are the same. Produce the numbers with code.