第 45 题：编译器如何处理control flow（if/while）？tracing vs `symbolic executi…
题目
编译器如何处理control flow（if/while）？tracing vs symbolic execution？
完整讲解
一、Control flow 带来的挑战
Control flow（if/while、动态分支）在 静态图 里不好直接表示：图是 DAG，而 if/while 有 环与分支。编译器要么用 专用节点（如 If/While 子图）、要么把控制流 线性化/展开，才能做优化与 codegen。难点：一、 捕获时要知道 走哪条分支（依赖数据或 shape）；二、 优化时不能错误地假设「只走一条路径」；三、 不同路径可能对应不同 shape，需能表达或特化。
二、Tracing（追踪）
Tracing：用 一次或若干次 具体输入 跑一遍 程序，按 实际执行路径 记录 op 序列，得到 一条线性化的子图（无分支、无环，只有实际走过的 op）。优点：实现简单、图简单、易优化。缺点：只记录到走过的路径——若运行时走了 未追踪过的分支（如 if 的另一边），图就错或需 guard 失效重捕获；循环 会被 展开成有限次，循环次数变或未知时难以正确。
三、Symbolic execution（符号执行）
Symbolic execution：用 符号（如符号变量表示 shape、或布尔表示条件）去 推理 分支与循环，生成 带条件 的图或 多路径 的表示（如「若 cond 则 A 否则 B」）。优点：能表达 未执行到的分支、依赖符号的循环，更完整。缺点：实现复杂、路径/状态可能爆炸、与后端优化器的结合难（很多后端偏好线性图）。
四、实践中的折中
- PyTorch Dynamo：偏 tracing（按执行追踪），用 guards（如 shape、dtype）保证「当前图仅当 guard 成立时有效」；分支或 shape 变则 break 并重捕获，或交给 fallback。
- TorchScript / FX：可 部分符号（如 Tensor 的 shape 符号）、部分 trace；控制流用 显式 If/Loop 节点 保留，后端再 lower 成具体实现。
- 编译器侧：若图里已有 If/While 节点，lowering 时转成 目标后端的控制流（如 MLIR 的 scf.if、scf.while，或 LLVM 的 branch/loop）；若来自 tracing，则图本身已无分支，只需处理「guard 失效」与重编。
面试要点
- Control flow 难在：图要表达分支/环、捕获要知道走哪条路、优化不能误假设单路径。
- Tracing：按执行记 op 序列，图简单但只含走过路径；未走分支或循环次数变会失效，需 guard 或重捕获。
- Symbolic execution：用符号推理分支/循环，图更完整但实现复杂；实践中多 tracing + guard，或显式 If/Loop 节点。
记忆要点
- 控制流要专用节点或线性化；tracing 得线性子图，symbolic 得带条件/多路径。
- Tracing = 只记走过路径，简单但路径变则失效；symbolic = 符号推理，完整但复杂。
- Dynamo 用 tracing + guards；图中有 If/Loop 时 lowering 成后端控制流。