编译

主线位置：traced 主线的中间一步。左边是 TracedTensor 建好的图，右边是执行与缓存里的 Runtime::prepare 和 Runtime::run。tenferro 的「编译」分成两段：GraphCompiler::compile 只做与后端无关的那一半，另一半在 prepare 时才做，因为它要知道程序放在哪个引擎上。本页两段都讲。

flowchart TB
  tt["输出 TracedTensor"] --> rs["resolve"]
  rs --> mm["materialize_merge 去重"]
  mm --> cp["compile 成 SSA"]
  cp --> pr["裁剪扩展输出"]
  pr --> sp["SemanticProgram 和绑定"]
  sp --> cg["CompiledGraph"]
  cg -->|prepare| st["降级成 ExecProgram"]
  st --> opt["优化 pass"]
  opt -->|缓存未命中| fold["折叠元数据视图"]
  fold --> sch["ScheduledGraph"]
  sch --> reg["逐元素区"]

第一段在 graph/compiler.rs 和 program/；第二段在 compiler/、segment.rs、runtime/schedule.rs、runtime/region.rs，入口是 runtime/preparation.rs。本页实验在 exp-tenferro8/rt-graph，release，M2 Max、macOS 27、rustc 1.99.0，引擎是 CpuEngine::serial()。

第一段：GraphCompiler 不碰后端

GraphCompiler 只有两个字段：一个扩展缓存仓库和 CompilerOptions。compile(&y) 就是 compile_many(&[&y])，后者先从各输出的 inputs_map 收集默认张量（同一个输入键出现两次但张量不同时返回 DuplicateBinding），再进 compile_many_with_descriptors。中间那几行就是上一页 computegraph 的三步：

        let view = resolve(roots);
        let graph = if checkpoint_aliases.is_empty() {
            materialize_merge(&view, &output_keys)
        } else {
            // ...
        };
        let mut compiled = compile(&graph);
        prune_compiled_extension_outputs(&mut compiled)?;

之后的工作：

1. 裁剪扩展输出。 prune_compiled_extension_outputs 从输出往回标记活的槽；一个扩展运算（比如一次返回 U、S、V 的 SVD）如果只有部分输出被用到，就问它的 prune_outputs 能不能换成一个输出更少的版本。
2. 给每个输入一个描述。 descriptor_for_input：有默认张量就用张量的 dtype 和形状，并按叶子是具体还是符号形状，把输入形状写成 Const 或 InputDim；没有默认张量、也没在 compile_with_input_specs 里说明的输入，返回 UnboundPlaceholder。输入的顺序就是 materialize_merge 的压平顺序，只有 compile_with_input_specs 会按调用方给的顺序重排（它还会拒绝输出用不到的占位符，见 TracedTensor）。
3. 翻译成语义程序。 compile_materialized_semantic_program 按指令顺序把每个 StdTensorOp 换成封闭的 CoreSemanticOp（扩展运算走 add_extension），逐个推断输出的 dtype 和形状，把扩展运算声明的形状等式化简成「形状守卫」挂到输出上，最后 SemanticProgramBuilder::finish。

产物 CompiledGraph 里是一个 FrozenProgram（Arc<SemanticProgram> 加 ProgramBindings）、编译选项和输入键的顺序。语义程序是不可变的 SSA：值是不透明的 ProgramValue，只能在同一个程序里查询；默认张量放在 ProgramBindings 里，不进程序的结构身份。finish 时还会算一个 128 位的 SemanticFingerprint：编码输入的元数据、每个运算、输出、形状守卫，值的编号先归一化。

整个第一段没有任何地方用到引擎，GraphCompiler::new() 也不需要参数。同一个 CompiledGraph 可以交给只注册了 CPU 引擎的 Runtime，也可以交给注册了 CUDA 引擎的 Runtime（CUDA 本机跑不了，见 CUDA）。

实验 traced_structure 打印编译结果（y = sum(x*x)，x 是 3 个 f64 的具体形状叶子）：

y = sum(x*x): inputs=1 outputs=1 ops=2 bindings=1 fingerprint=[7a, 2a, ae, f0]
  op 0: Mul  in=[ProgramValue(<opaque>), ProgramValue(<opaque>)] out=[ProgramValue(<opaque>)] dtype=F64 shape=[Exact(Const(3))]
  op 1: ReduceSum { axes: [0] }  in=[ProgramValue(<opaque>)] out=[ProgramValue(<opaque>)] dtype=F64 shape=[]
Debug: CompiledGraph { inputs: 1, outputs: 1, input_keys: 1, bindings: 1, semantic_fingerprint: SemanticFingerprint([122, 42, 174, 240, 161, 110, 225, 59, 46, 128, 90, 77, 12, 69, 45, 163]) }
same structure, other data: fingerprint equal = true, semantic_eq = true
same structure, shape [4]: fingerprint equal = false

两个运算，一个输入，一个绑定（x 的数据）。换一份数据、同样结构建出来的程序指纹相同，semantic_eq 也为真：数据不在结构里。换成 4 个元素的具体形状叶子，输入元数据从 Const(3) 变成 Const(4)，指纹就不同了。下一页会看到，Runtime 的准备缓存正是按这个指纹查的。

GraphCompiler 还有一个 ExtensionCacheStore 和 cache_stats()、clear_extension_caches()。上游指南 parallelism-and-caching.md 说它「retains graph lowering and static extension planning caches」；在 v0.8.0 的 graph/compiler.rs 里，这个字段只在构造、clear_extension_caches、cache_stats 和两个访问器里出现，compile 的路径不读也不写它。

做了哪些优化

第一段唯一的优化是 computegraph 带来的公共子表达式消除。实验同一段：分别建两次 x * x 再相加，

(x*x) + (x*x), built separately: inputs=1 outputs=1 ops=2 bindings=1 fingerprint=[38, f8, d5, 70]
  op 0: Mul  in=[ProgramValue(<opaque>), ProgramValue(<opaque>)] out=[ProgramValue(<opaque>)] dtype=F64 shape=[Exact(Const(3))]
  op 1: Add  in=[ProgramValue(<opaque>), ProgramValue(<opaque>)] out=[ProgramValue(<opaque>)] dtype=F64 shape=[Exact(Const(3))]

程序里只剩一个 Mul。求导变换后的图也受益于这一点（变换本身见 traced AD）。

第二段的优化 pass 在 optimize_exec_program，作用在执行 IR ExecProgram 上：

pub fn optimize_exec_program(
    program: &mut ExecProgram,
    input_dtypes: &[DType],
    input_shapes: &[Vec<DimExpr>],
    config: OptimizerConfig,
) -> Result<()> {
    super::conj_sinking(program, input_dtypes, input_shapes)?;
    super::dot_dimension_sorter(program);
    if config.algebraic_layout_simplifier {
        super::algebraic_layout_simplifier(program, input_shapes)?;
    }
    super::transpose_folding(program);
    super::dot_conj_folding(program)?;
    // Degenerate forms never reach a backend, whether or not the
    // canonicalization below is enabled.
    super::rewrite_degenerate_dots(program, input_shapes)?;
    if config.dot_decomposer {
        super::dot_decomposer(program, input_shapes)?;
        if config.algebraic_layout_simplifier {
            super::algebraic_layout_simplifier(program, input_shapes)?;
        }
    }
    super::eliminate_dead_code(program);
    super::populate_last_use(program)?;
    Ok(())
}

开关在 OptimizerConfig，默认值在同一个文件的 impl Default：algebraic_layout_simplifier: true、dot_decomposer: false，用 GraphCompiler::with_compiler_options 改。rewrite_degenerate_dots 和 dot_decomposer 共用一套实现，前者只改写退化形式、不做规范化，所以不受开关控制。没有常量折叠，没有代数化简（x * 1 不会被删），也没有运算重排。

上游的 docs/spec/optimizer-passes.md 落后于代码：它的「Pass Order」在 staging 阶段只列 DotDimensionSorter、TransposeFolding、DotDecomposer、DeadCodeElimination、populate_last_use 五步；代码里多了 conj_sinking、algebraic_layout_simplifier、dot_conj_folding、rewrite_degenerate_dots，dot_decomposer 默认是关的。它把准备阶段的第 6 步 MetadataViewFolding 写对了（下文）。

第二段：降级在 prepare 里，而且每次都做

ExecProgram 不在 CompiledGraph 里。它由 stage_semantic_program 生成：把语义程序重新编成槽位形式，交给 compile_std_to_exec_with_options_and_constraints 逐条推断输出形状（形状是 DimExpr，执行时代入真实输入求值），转成 ExecOp，再跑上面的 pass。调用它的生产位置是 Runtime::prepare 一路下去的 resolve_preparation_context：

    let candidates = executable_candidates;
    let staging = Arc::new(
        stage_semantic_program(&frozen.program, compiler_options).map_err(|source| {
            Arc::new(PrepareError::Engine {
                source: Arc::new(source),
            })
        })?,
    );

这一步在查准备缓存之前：缓存键要用到按运算选出的引擎和放置，而选引擎要看降级后的指令。所以每次 prepare 都会重新降级、重跑一遍 pass，即使缓存命中；run 不经过这里。实测一个 41 个运算的程序，缓存命中的 prepare 约 88 µs，3 个运算的约 12 µs（执行与缓存）。所以要把 Prepared 留着反复 run，而不是每次都 prepare。

缓存未命中时，PreparedProgramRoot::new 再做三件事，结果和缓存条目存在一起：

• 折叠元数据视图。 Transpose、Reshape、BroadcastInDim、Slice 这类只改元数据的指令，如果只有一个读它的消费者、两者在同一个位置、引擎声明自己能直接读视图（folds_metadata_views，CPU 声明了，GPU 注册保持默认的否），就不再单独成为一条命令，而是作为「输入视图」挂到消费者身上。它放在这里而不在优化 pass 里，是因为规则要看放置：跨引擎的值得先物化再传输。
• 调度。 ScheduledGraph::from_exec_program 按 ExecProgram 的指令顺序逐条生成节点，每个节点带一个执行位置（哪个引擎、哪个事件域）；如果某个输入不在这个位置上，先插一个 Transfer 节点，找不到传输提供者就报 MissingTransferProvider。它不重排指令，「调度」指的是定位置、补传输、记依赖；同时记下整张图是不是只在一个位置上（flat），执行时据此走更省事的路径（见下一页）。
• 规划逐元素区。 下一节。

实验 regions 第 3 段看折叠：(tᵀ + mt).sum() 的 3 个运算只有 2 条命令（置换折进了加法）；同一个 tᵀ 被两个运算读时，6 个运算 6 条命令，置换照常单独执行。

  t(m) + mt, sum: ops=3 regions(count, covered)=(0, 0) commands=2 fused/fallback=(0, 0)
  t used twice: ops=6 regions(count, covered)=(0, 0) commands=6 fused/fallback=(0, 0)

分段与逐元素区

segment_exec_program 把指令切成三种 Segment：主机指令（shape_of、dynamic_truncate、pad_to_match、constant，在主机上算）和 FFI 指令（dot_general 和扩展运算，交给外部库）各自单独成段，其余连续的指令合成一个 Fused 段；「广播 + 乘法」的两三条指令另有特判。plan_elementwise_regions 再对每个 Fused 段做三道检查：至少 2 条指令；外部输入不超过引擎声明的上限（CPU 的 max_fused_region_inputs 是 4）；build_elementwise_fusion_plan 认可：段里每条指令都得是同一个 dtype、单输出，而且要么是 BroadcastInDim，要么有对应的逐元素融合运算，否则整段返回 None，不成区。成区的段在执行时作为一条命令交给引擎；引擎也可以拒绝，那就退回逐条执行。

实验 regions 第 1、2 段（acc = acc * x + x 重复 20 次的链，各跑一次）：

== 1. chain depth 20, with and without a trailing reduce_sum (one run each)
  reduce=true n=16: ops=41 regions(count, covered)=(0, 0) commands=41 fused/fallback=(0, 0)
  reduce=true n=100000: ops=41 regions(count, covered)=(0, 0) commands=41 fused/fallback=(0, 0)
  reduce=false n=16: ops=40 regions(count, covered)=(1, 40) commands=1 fused/fallback=(0, 1)
  reduce=false n=100000: ops=40 regions(count, covered)=(1, 40) commands=1 fused/fallback=(1, 1)
== 2. five distinct inputs summed, n=100000
  4 inputs: ops=4 regions(count, covered)=(1, 4) commands=1 fused/fallback=(1, 0)
    out[0] = 6
  5 inputs: ops=5 regions(count, covered)=(0, 0) commands=5 fused/fallback=(0, 0)
    out[0] = 10

• 链的末尾多一个 reduce_sum，规约没有逐元素融合运算，整段都不成区：41 条命令。去掉规约，40 条指令成 1 个区、1 条命令。分段不会把规约前面的部分单独切出来。
• 成了区也不一定融合。CPU 引擎在元素数少于 16 * 1024 时拒绝，退回逐条执行：16 个元素时是 fallback，10 万个元素时融合。（计数挂在准备好的程序上：两个 n 的程序结构相同、输入都是符号形状，命中的是同一个条目，所以第二行是累加的 (1, 1)。）
• 读 5 个外部输入的段超过 CPU 的上限，不规划成区，5 条命令逐条执行，结果正确。

融合内核怎么执行、为什么有那个元素数门槛、融合和逐条执行哪个快，归 逐元素运算与融合 那一页。

动脑筋答案

grad of sum(x*x): inputs=2 outputs=1 ops=3 bindings=2 fingerprint=[91, c7, 17, 4c]
  op 0: BroadcastInDim { shape: [Const(3)], dims: [] }  in=[ProgramValue(<opaque>)] out=[ProgramValue(<opaque>)] dtype=F64 shape=[Exact(Const(3))]
  op 1: Mul  in=[ProgramValue(<opaque>), ProgramValue(<opaque>)] out=[ProgramValue(<opaque>)] dtype=F64 shape=[Exact(Const(3))]
  op 2: Add  in=[ProgramValue(<opaque>), ProgramValue(<opaque>)] out=[ProgramValue(<opaque>)] dtype=F64 shape=[Exact(Const(3))]

3 个运算，2 个输入：一个是 x，另一个是 grad 引入的种子：一个值为 1 的标量，带着默认张量，所以 bindings=2。reduce_sum 的反向规则把标量种子 BroadcastInDim 回长度 3；Mul 的反向规则对两个操作数各产生一份「种子 × 另一个操作数」，两个操作数都是 x，两份结构完全相同，被 materialize_merge 合成一个 Mul；最后 Add 把两份梯度相加，两个输入是同一个值。前向的 Mul 和 ReduceSum 不在程序里：只要梯度，前向结果用不到，没有被压平进来。

小结

• GraphCompiler::compile 只做与后端无关的一半：resolve → materialize_merge → compile → 裁剪扩展输出 → 翻成 SemanticProgram，默认张量放在不参与结构身份的绑定里，算一个 128 位语义指纹。
• 第一段唯一的优化是按结构去重；第二段的 pass 有共轭下沉、收缩维排序、布局化简、置换折叠、共轭折叠、退化点积改写、死代码消除和最后使用标记，dot_decomposer 默认关；没有常量折叠。
• 降级成 ExecProgram 和跑 pass 在 prepare 里进行，而且在查缓存之前，所以每次 prepare 都重做；run 不重做。
• 缓存未命中时再折叠单消费者的元数据视图（CPU 才开）、排调度、规划逐元素区；调度不重排，只定位置、补传输。
• 逐元素区要求整段都是逐元素运算、外部输入不超过引擎上限（CPU 是 4）；CPU 在 16384 个元素以下拒绝融合，退回逐条执行。