[Topic11/CFG] 补齐寄存器分配与数据流分析所需的统一 CFG 接口

[yuki-328]

PR #41 应作为项目统一的 CFG 基础设施。寄存器分配相关 PR 只提供机器指令语义并消费 CFG，不再独立维护 CFG 实现。

需要完善

1. 统一 CFG 实现

• 统一 scratchv/analysis/cfg_builder.py 与 scratchv/ir/cfg.py，只保留一个正式 CFG API。
• 抽取可供 IR 和 Machine IR 共用的 CFG 数据结构与图算法。
• 明确 CFG 的构建、修改、失效和重新分析规则。
• 避免 IR 优化器与寄存器分配器分别维护不一致的 CFG。

2. 提供 IR 与 Machine IR adapter

IR adapter 和 Machine IR adapter 负责将不同指令表示转换为统一 CFG 所需的信息，包括：

• 基本块名称和入口 label
• 指令是否为 terminator
• 条件分支和无条件跳转目标
• 是否存在 fallthrough
• 每条指令的显式与隐式 uses/defs
• Machine IR 中的寄存器、立即数、label 和跳转目标分类
• CALL 的隐式使用、隐式定义和 clobber 集合

建议采用类似以下的适配接口：

class CFGAdapter(Protocol):
    def block_name(self, block) -> str: ...
    def instructions(self, block) -> Sequence[Instruction]: ...
    def is_label(self, instr) -> bool: ...
    def is_terminator(self, instr) -> bool: ...
    def branch_targets(self, instr) -> Sequence[str]: ...
    def has_fallthrough(self, instr) -> bool: ...

3. 提供通用反向活跃变量分析

活跃变量分析应独立于寄存器分配器，并可供 IR 和 Machine IR 共用。

适配器负责提供每条指令的变量使用和定义：

class UseDefProvider(Protocol):
    def uses(self, instr) -> AbstractSet[ValueId]: ...
    def defs(self, instr) -> AbstractSet[ValueId]: ...

    def edge_uses(
        self,
        pred: BlockId,
        succ: BlockId,
    ) -> AbstractSet[ValueId]:
        """返回 Phi 等仅在指定 CFG 边上发生的 use。"""

建议分析结果使用独立对象返回：

@dataclass(frozen=True)
class BlockLiveness:
    uses: frozenset[ValueId]
    defs: frozenset[ValueId]
    live_in: frozenset[ValueId]
    live_out: frozenset[ValueId]


@dataclass(frozen=True)
class LivenessResult:
    blocks: Mapping[BlockId, BlockLiveness]
    edge_live: Mapping[
        tuple[BlockId, BlockId],
        frozenset[ValueId],
    ]
    live_before: Mapping[InstructionId, frozenset[ValueId]]
    live_after: Mapping[InstructionId, frozenset[ValueId]]


def analyze_liveness(
    cfg: ControlFlowGraph,
    provider: UseDefProvider,
) -> LivenessResult:
    ...

指令 uses/defs 语义

• uses[B]：在基本块 B 内首次定义前被读取的值。
• defs[B]：在基本块 B 内被定义的所有值。
• 同一值先定义后使用时，不加入 uses[B]。
• 同一值先使用后定义时，同时属于 uses[B] 和 defs[B]。
• 显式和隐式 uses/defs 都必须纳入分析。
• label、立即数和跳转目标不得被识别为变量。
• CALL 的 clobber 集合由机器指令语义提供，但不能直接混入虚拟寄存器 defs。
• Phi 定义属于后继块入口，Phi operand 属于对应的前驱边。

数据流方程

没有 Phi 节点时：

live_out[B] = ⋃ live_in[S]
              S ∈ successors(B)

live_in[B] = uses[B] ∪ (live_out[B] - defs[B])

存在 Phi 节点时：

edge_live[B, S] =
    (live_in[S] - phi_defs[S]) ∪ phi_uses[B, S]

live_out[B] = ⋃ edge_live[B, S]

分析应使用 worklist 迭代至不动点，并满足：

• 正确处理循环和多条回边。
• 仅在某个块的结果变化后重新处理其前驱。
• 对相同输入产生确定且一致的结果。
• 明确空块和不可达块的处理规则。
• CFG 或指令修改后，旧分析结果必须失效或重新计算。

分析必须能够回答的结论

分析结果应能够用于判断：

• 哪些值需要从基本块入口传入。
• 哪些值需要在基本块出口继续保留。
• 每条 CFG 边实际需要传递哪些值。
• 每条指令执行前后有哪些值仍然活跃。
• join 和循环回边上需要保持一致位置的值。
• 哪些值可以在某条指令后安全释放寄存器。
• 哪些 live interval 必须扩展到基本块边界。
• spill rewrite 在块出口需要写回、在块入口需要恢复的值。
• CALL 后仍然活跃，并且位于 caller-saved/clobbered 寄存器中的值。
• 构建寄存器冲突关系和统计寄存器压力所需的活跃集合。

CFG 分析层只输出上述事实，不直接决定：

• 具体寄存器选择
• spill slot 分配
• spill/reload 插入位置
• caller-save 或 callee-save 策略

这些决策仍由寄存器分配器和 rewrite 阶段完成。

4. 提供可复用的数据流求解框架

活跃变量分析属于反向数据流分析。常量传播属于前向数据流分析，两者不能混用分析结论，但应复用同一套 worklist 基础设施。

建议允许具体分析提供：

class DataflowAnalysis(Protocol):
    direction: Literal["forward", "backward"]

    def boundary(self, block): ...
    def meet(self, values): ...
    def transfer(self, block, value): ...

常量分析需要另外计算：

• 每个基本块入口的常量状态。
• 每个基本块出口的常量状态。
• join 后仍能确定为同一常量的值。
• join 后必须退化为 unknown/overdefined 的值。
• 循环迭代后的稳定常量状态。
• 可以安全折叠的表达式和条件分支。

5. 明确控制流规则

• 条件分支：target + fallthrough
• J/JAL：只有静态 target
• JALR/return：无静态 successor
• CALL：保留 fallthrough，不是 terminator
• LABEL：基本块入口，不是可执行指令
• terminator 后的下一条指令必须开启新的基本块
• 即使 terminator 后代码不可达，也不能与前一个基本块合并

6. 明确 FOR/ENDFOR 处理方式

需要选择并固定一种规则：

• CFG builder 直接识别 FOR/ENDFOR 并建立循环边；或
• 在构建 CFG 前将其规范化为 BR/BR_IF 和 label。

不能让 IR CFG 与 Machine CFG 分别使用不同的隐式循环规则。

7. CFG 校验与诊断

CFG 构建完成后应校验：

• entry block 是否存在且唯一
• 基本块名称是否重复
• 跳转目标是否存在
• predecessor/successor 是否互相一致
• terminator 是否位于基本块末尾
• 无条件跳转后是否错误添加 fallthrough
• 每条指令是否只属于一个基本块
• Phi 的前驱集合是否与 CFG predecessor 一致

对于悬空 target、重复块名和无效 entry，应返回明确诊断，不能静默忽略。

8. 明确不可达代码接口

需要明确不可达代码处理属于哪一层：

• CFG 仅标记或返回不可达基本块；还是
• CFG 提供删除计划；还是
• 优化 pass 负责同步修改原始 IR。

CFG 查询接口本身不应在没有明确调用的情况下删除或重排原始 IR。

测试要求

CFG 拓扑测试

使用精确的节点集合、successor 集合和 predecessor 集合断言，覆盖：

• 线性控制流
• if/else
• diamond/join
• 单层循环
• 嵌套循环
• 多回边循环
• 条件分支
• 无条件跳转
• return
• call fallthrough
• 间接跳转
• terminator 后的不可达指令
• 空函数和空基本块
• 无效 target
• 重复块名
• 不可达基本块

活跃变量测试

使用精确集合断言，覆盖：

• use-before-def
• def-before-use
• redefinition 对旧值的 kill
• 跨基本块使用的值
• diamond/join 中跨两个分支存活的值
• 仅在单条分支上使用的值不会污染另一条边
• 单回边和多回边循环的不动点收敛
• Phi operand 的边相关活跃性
• label、立即数和 target 不进入活跃集合
• CALL 前后的 live_before/live_after
• live_after(CALL) 与 clobber 集合的组合
• 空块和不可达块
• CFG 修改后不会复用过期分析结果
• 同一 CFG 重复分析结果一致

集成测试

• IR CFG 降低到 Machine CFG 后，控制流拓扑保持一致。
• 常量分析在 diamond、join 和循环结构中得到正确结果。
• 两种寄存器分配器消费同一份 CFG 和 liveness 结果。
• 在较少物理寄存器下触发 spill/reload 后，分支和循环结果仍正确。
• live value 跨基本块边界时能够正确写回和恢复。
• CALL 只保存调用后仍活跃且可能被 clobber 的 caller-saved 值。
• 生成的 RISC-V 指令能够在现有模拟器中执行并得到预期结果。

验收标准

• 项目只有一个正式 CFG 核心实现
• IR 和 Machine IR 共用 CFG 数据结构与图算法
• 提供稳定的 IR adapter 和 Machine IR adapter
• adapter 能提供完整的控制流与指令 uses/defs 语义
• 提供独立、可复用的活跃变量分析接口
• 提供基本块、CFG 边和指令级活跃性结果
• 正确处理 join、循环、多回边和 Phi
• CFG 或 IR 修改后不会使用过期分析结果
• CFG 边、fallthrough 和 terminator 规则具有明确契约
• 核心测试使用精确节点、边和活跃集合断言
• 常量分析和两种寄存器分配器的集成测试通过
• 生成代码的模拟器执行测试通过
• 全量测试通过