折叠常量、构建 CFG、求出 φ 的位置

目标

折叠 AST 中的常量并清除已确定的分支，在第 6 个模块的 chunk 里建立基本块和 CFG，并删除不可达的代码。再根据这张图求出支配节点和支配边界，计算 SSA 的 φ 应该放进哪些块。优化后的程序必须在给出同样结果的同时，执行更少的指令。

为什么重要

优化中，“不能做的事”比“能做的事”更重要。如果提前计算了除以 0，或者删掉代码之后没有重新接好跳转，就会得到快但错误的程序。另外，CFG、支配节点和 SSA 是实用编译器所有优化赖以存在的数据结构，在这里亲手算过的东西，会成为第 10 个模块里读懂 LLVM IR 的眼力。

规则

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

步骤

补全 /root/mini/opt.py 的 fold(n)——评分器会对照固定表达式和 250 个随机表达式折叠之后的树与节点位置。
补全 fold_stmt、fold_list 和 fold_program——折叠前后的运行结果必须相同。
补全 JUMPS、jump_target、leaders 和 basic_blocks。
补全 cfg(code)。
补全 reachable(succ) 和 remove_unreachable(chunk)。
补全 dominators(succ) 和 idom(succ)。
补全 dominance_frontier(succ) 和 phi_blocks(succ, defs)。
补全 optimize_source(src)，并对 /opt/fixtures/mini/programs/manifest.json 的 opt 列表中的每个程序，用 VM 运行优化前后的 chunk，把 {이름: {"before": 명령 수, "after": 명령 수, "same_output": true/false}}（占位符依次为程序名、指令数）写入 /root/mini/opt_report.json。

参考

python3 /root/mini/mini.py opt /opt/fixtures/mini/programs/const.mini 会显示优化前后的指令数。
直到编译器和 VM 为止的文件，在实验开始时已经铺好。
常见错误：折叠除以 0 时让编译器崩溃，丢弃折叠出的值的位置，把 true && x 折叠成 true，删除之后让跳转偏移量保持原样，把 JUMP 也当作会顺序落入下一条，φ 只扩展一次。
会话从 60 分钟开始，可以用＋时间延长，结束后 /root/mini 会消失。

折叠常量——先从不能折叠的做起

用 copy.copy 复制节点，然后先折叠子节点。只有两边都是 Int、Bool 字面量并且类型相符时才计算，除数为 0 或指数为负时保持原样。新字面量用原节点的 line 和 col 来创建。

清除已确定的分支

对每条语句的表达式做 fold。if 的条件变成 Bool 字面量后，对选中的分支（它是 Block，所以作用域得以保留）再次 fold_stmt，如果没有分支，就用 None 删掉这条语句。fold_list 会丢弃 None。别忘了函数体。

基本块

把 0 放入首指令集合；对每条指令，如果是跳转，当目的地（i + 1 + 偏移量）在代码范围内时放入；如果是跳转或 RETURN，当紧接着的位置（i + 1）在代码范围内时放入。把排序后的首指令两两配对，就是 [起点, 终点)。

控制流图

看块的最后一条指令。如果是 RETURN，就没有后继；如果是 JUMP，就是目的地块一个；如果是条件跳转，就是顺序落入的块（结束位置是首指令的那个块）和目的地块——两者相同则只记一个。其余情况是一个顺序落入的块。如果目的地是代码末尾，就不记。

删除不可达代码并重新接好跳转

从块 0 出发，沿着 succ 把能到达的块收集起来。建立要保留的指令的“旧位置 → 新位置”表（代码末尾也映射到新的末尾），对每个跳转，用新偏移量 = 新目的地 - (新位置 + 1) 重新计算。常量池里的 dict 用递归做同样的事。

支配节点

对每个可达的块，一开始先设为“所有可达的块”，只有入口设为 {0}。对不是入口的块，把它换成前驱块们（只算可达的）的支配节点的交集加上自己，如此反复，直到一整圈都没有任何变化。直接支配节点是严格支配节点中最近的（支配节点集合最大的）那个。

支配边界与 φ 的位置

对每个前驱块有两个以上的块 b，从前驱块 p 出发，沿着直接支配节点的链向上走，一直走到 b 的直接支配节点为止，把 b 放进途中经过的每个块的边界里。φ 的位置从定义块们的边界出发，把新放置的 φ 块也当作定义，一直扩展到不再增加为止。

测量优化前后

optimize_source 把同一个程序编译两次——一次原样，一次先 fold_program 再 remove_unreachable。报告写下两个 chunk 用 run_chunk 运行得到的 executed，以及输出和错误是否相同。数字请用代码生成再写入。