computegraph

主线位置：traced 主线的底座。TracedTensor 的每个运算都往一张 computegraph 的 Graph 里加节点（见 TracedTensor），GraphCompiler 再用这个 crate 的 resolve / materialize_merge / compile 把它们压平（见编译）。本页只讲 computegraph 本身，以及 tenferro 的算子词汇表怎么接上来。

flowchart TB
  g1["Graph 1 叶子"] --> g3["Graph 3 一个节点"]
  g2["Graph 2 一个节点"] --> g3
  g3 -->|parents| rs["resolve"]
  rs --> view["ResolvedView 键到定义"]
  view --> mat["materialize_merge"]
  mat --> mg["MaterializedGraph 去重"]
  mg --> cp["compile"]
  cp --> prog["CompiledProgram SSA"]
  prog --> ev["eval 可选"]
  prog --> tf["tenferro 语义程序"]

computegraph 是 tensor4all 的单独仓库（tensor4all/computegraph-rs），crate 描述写的是「AD-agnostic tensor computation graph engine: construction, logical resolution, physical materialization, SSA compilation, and evaluation」。src 一共 9 个文件、约 1000 行（含文档注释）。版本说明：v0.8.0 的工作区 Cargo.toml 直接依赖 crates.io 上的 computegraph = "0.1.0"，这个包打包自 594cdcec，本页链接用它。（0.7.1 时用 git rev 691def2d 锁定，两个 commit 的 src 完全一样；提交 5f5f9b27 把所有 git 锁定换成了已发布的版本。）

本页的实验在 exp-tenferro8/rt-graph（依赖 computegraph = "=0.1.0" 和 tenferro =0.8.0），release，M2 Max、macOS 27、rustc 1.99.0。

两个 trait：元数据和求值分开

GraphOperation 是图里「运算」的全部要求：

pub trait GraphOperation: Clone + std::fmt::Debug + Hash + Eq + Send + Sync + 'static {
    type Operand: Clone + Send + Sync + 'static;
    type Context;
    type InputKey: Clone + std::fmt::Debug + Hash + Eq + Send + Sync + 'static;

    /// Returns the number of inputs consumed by this operation.
    fn input_count(&self) -> usize;

    /// Returns the number of outputs produced by this operation.
    fn output_count(&self) -> usize;
}

只有输入输出个数，没有形状、dtype、求导规则，也没有怎么算。Hash + Eq 是硬要求：运算本身要参与结构性身份（下一节）。求值放在另一个 trait EvaluableGraphOperation，只有一个 fn eval(&self, ctx: &mut Self::Context, inputs: &[&Self::Operand]) -> Vec<Self::Operand>。不实现它的运算照样能建图、编译，只是不能用 computegraph 自带的 eval 执行。tenferro 正是这样用的。

值的身份是结构

图里引用一个值有两种方式，ValueRef：

pub enum ValueRef<Op: GraphOperation> {
    Local(LocalValueId),
    External(ValueKey<Op>),
}

/// Cross-graph structural identity for a value.
#[derive(Clone, Debug)]
pub enum ValueKey<Op: GraphOperation> {
    Input(Op::InputKey),
    Derived {
        /// Shared structural identity of the operation that produced this value.
        operation: Arc<OperationKey<Op>>,
        output_slot: u8,
    },
}

Local 是本图里的下标，External 用一个 ValueKey 指向别的图里的值。ValueKey 不是编号，而是「这个值是怎么算出来的」：输入就是它的 InputKey；算出来的值是「哪个运算、吃了哪些输入键、第几个输出」，即 OperationKey 的 operation、inputs、role 三个字段，再加一个预先算好的 fingerprint。键是递归的，深度和图一样深；为了不在每次哈希时走完整棵树，ValueKey 的 Hash 只写入那个缓存的指纹，PartialEq 先比 Arc::ptr_eq，不是同一个 Arc 再比完整结构（指纹撞了也不会出错）。

结果是：在两张互不知道的图里各写一遍 x * y，得到的两个 ValueKey 相等。这是后面「公共子表达式消除」的全部基础。

Graph 自己只存本地的值和运算，外加一个 parents: Vec<Arc<Graph<Op>>>。父图在建图时就已经存在，所以父链不可能成环。GraphBuilder::add_operation 用 assert_eq! 检查输入个数，不对就 panic：computegraph 不返回错误，校验是调用方的事。tenferro 在调用前已经检查过，用户看到的是 Result（见 TracedTensor）。

resolve、materialize、compile、eval

四步各在一个文件里：

• resolve：从根图出发，沿 parents 深度优先走遍所有能到达的图（按图的指针去重），把每个值登记进一张 HashMap<ValueKey, ValueDef>。不复制节点，不排序，只是一个「键到定义」的查找表。
• materialize_merge：从要求的输出键出发做深度优先遍历，按后序把用到的输入和运算依次放进一张扁平的图。去重靠一张以 OperationKey 为键的 op_map：
• compile：把扁平图逐个运算抄成 Instruction，每个值对应一个槽（slot），每个槽只写一次（SSA）；输入槽是所有没有生产者的值，输出槽按输出键查出来。
• eval：开一个 Vec<Option<Operand>>，按指令顺序调用每个运算的 eval，把结果 clone 进输出槽。

materialize_merge 里去重的那段（materialize_produced）：

        let op_key = Arc::new(OperationKey::new(
            operation.clone(),
            input_keys.clone(),
            role.clone(),
        ));

        if self.op_map.contains_key(&op_key) {
            let output_key = ValueKey::Derived {
                operation: op_key,
                output_slot: output_slot as u8,
            };
            let val_index = self.val_map.get(&output_key).copied();
            // ...
        }

        let materialized_inputs = input_keys.iter().map(|input| self.visit(input)).collect();
        let op_index = self.operations.len();
        self.op_map.insert(Arc::clone(&op_key), op_index);

同一个结构的运算只进扁平图一次。先递归 visit 输入、再登记自己，所以运算的顺序天然是拓扑序。

实验 cg_basics 用一个三种运算（Mul、Add、Sub）、Operand = f64 的小枚举：图 1 有输入 x、y 和 p = x * y；图 2 以图 1 为父图，从头再写一遍 q = x * y，再算 r = p + q：

g1: values=3 ops=1
g2: values=2 ops=2 parents=1
p_key == q_key (structural identity): true
materialized: values=4 ops=2 inputs=["x", "y"]
  inst 0: Mul [0, 1] -> [2]
  inst 1: Add [2, 2] -> [3]
input_slots=[0, 1] output_slots=[3] n_slots=4
eval(x=3, y=4) = [24.0], instructions evaluated = 2

• 图 2 自己只有 2 个值（q、r），x、y、p 都通过 External 键引用父图。
• p 和 q 的键相等；扁平化之后只剩一个 Mul，Add 的两个输入是同一个槽 [2, 2]。eval 只执行了 2 条指令，结果 (3·4)+(3·4) = 24。
• 这就是 computegraph 唯一的「优化」：结构相同的子表达式只算一次。没有常量折叠，也没有代数化简。

它不懂求导

crate 的定位里写着「AD-agnostic」，代码里也确实没有任何求导逻辑。它给 AD 留的只有一个标签 OperationRole：Primary，或者 Linearized { active_mask: Vec<bool> }。这个标签进 OperationKey，参与指纹和相等比较，所以「原始的 Mul」和「线性化后、只对第二个输入线性的 Mul」不会被当成同一个运算合并；但 compile 生成的 Instruction 里没有 role 字段，过了这一步标签就丢了。

线性化、转置这些规则都在 tenferro 自己的 tenferro-internal-ops/src/ad/ 里。规则通过 PrimitiveRuleBuilder 往图里加节点，这个 trait 在 autodiff feature 下直接实现给了 GraphBuilder<StdTensorOp>。例如乘法里「一边固定、一边是切向量」的那一步（emit_linear_mul_fixed）：

fn emit_linear_mul_fixed(
    builder: &mut dyn PrimitiveRuleBuilder,
    fixed: ValueRef<StdTensorOp>,
    active: LocalValueId,
) -> LocalValueId {
    builder.add_operation(
        StdTensorOp::Mul,
        vec![fixed, ValueRef::Local(active)],
        OperationRole::Linearized {
            active_mask: vec![false, true],
        },
    )[0]
}

对 computegraph 来说这只是又一个运算节点。规则怎么写、grad 怎么在图上变换，见 primitive AD 和 traced AD。把图和求导拆开的好处是：图引擎可以单独测试（computegraph 的测试用的就是 f64 标量运算），求导规则换了也不用动图引擎。

tenferro 怎么接上来

tenferro 的运算类型是 StdTensorOp，定义在 tenferro-internal-ops，但枚举本身由 tenferro-core-ops 的宏 define_std_tensor_op! 生成。同一个 catalog.rs 里有一张 primitive_ops! 表，每行一个原语：名字、类别（Elementwise、Analytic、Structural、Reduction、Contraction、Indexing、Dynamic、Host）、dtype 规则、输入个数范围、是否只在主机上执行，一共 52 行（0.8.0 新增了 Erf）；执行层的 ExecOp 也由同一个文件的 define_exec_op! 生成。词汇表写一次，图层和执行层两个枚举从同一处展开。

两个枚举的最后一个变体都是 Extension(Arc<dyn ExtensionOp>)：einsum、线性代数、FFT 这些运算族不进核心表，而是实现 ExtensionOp trait，用 family_id、payload_hash、payload_eq 提供哈希和相等，于是也能参与结构性身份（见扩展算子）。

impl GraphOperation for StdTensorOp 的开头：

impl GraphOperation for StdTensorOp {
    // This graph is metadata-only; execution owns tensors in the runtime
    // submission layer rather than as graph operands.
    type Operand = ();
    type Context = ();
    type InputKey = TensorInputKey;

Operand = ()：tenferro 不用 computegraph 的 eval，图里只有结构。输入键 TensorInputKey 平时是 User { id }，id 取自一个全局原子计数器，每建一个叶子加一；开 autodiff 时多一个 Tangent { of, pass }，给前向模式的切向量输入用。形状和 dtype 不在图里，而在一张以 ValueKey 为键的全局元数据表里（见 TracedTensor）。

tenferro 用到的是 GraphBuilder、resolve、materialize_merge、compile 四样：TracedTensor 的每个运算用 GraphBuilder 建一张小图；GraphCompiler 用后三个把图压平，再把 CompiledProgram<StdTensorOp> 翻译成自己的语义程序。einsum 的 traced 入口另有一条路：tenferro-runtime 的 TraceContext 直接往语义程序的 builder 里加运算，不经过 computegraph。

和另外两卷对照：candle 的「图」就是每个结果张量里存的 Op（见计算图怎么记下来），burn 的融合后端记的是一串 OperationIr 描述（见 burn-ir），两者都没有 tenferro 这样独立的、按结构去重的图引擎。

上游文档和代码不一致的地方

tenferro 仓库里有一篇 docs/architecture/computegraph.md，traits、ValueKey、四步流水线的描述和代码一致，有三处和 594cdcec 的代码对不上：

• 文档说所有键都登记进一个全局的 ValueKeyInterner，比较用 ValueKeyId。代码里 ValueKeyInterner 存在，但 crate 内没有任何地方调用它，tenferro 里也没有；实际做法是 OperationKey 里缓存的指纹。
• 文档第 V 节说 computegraph「caches compiled programs keyed by graph structure」。代码里没有缓存；缓存在 tenferro 的 Runtime 里（见执行与缓存）。
• 文档里的 ResolvedView::resolver 是 Arc<dyn Resolver>，代码是 Box<dyn Resolver<Op>>。

动脑筋答案

graph3 declared input order = [Input("x"), Input("y")]
graph3 materialized input order = ["y", "x"]
graph3 eval(&[10, 1]) = [9.0]  (y - x with the first operand bound to y)

结果是 9：10.0 绑到了 y。compile 的 input_slots 是「扁平图里所有没有生产者的值」，按扁平图里的顺序排；扁平图又是从输出出发、按 Sub 的输入顺序深度优先建的，先遇到 y。图里 add_input 的顺序不起作用。所以只看 CompiledProgram 是不知道第 i 个输入是谁的，调用方得自己记住键的顺序。tenferro 的 CompiledGraph 为此单独存了一份 input_keys，传给 Runtime::prepare 和 Runtime::run 的输入同样要按这个顺序排（见执行与缓存里的实验）。

小结

• computegraph 只管图：GraphOperation 只要求输入输出个数和 Hash + Eq，求值是可选的 EvaluableGraphOperation。
• 值的身份是结构性的 ValueKey：同样的运算吃同样的输入，在哪张图里写都相等；哈希只用缓存的指纹。
• resolve 建查找表，materialize_merge 从输出深度优先压平并按 OperationKey 去重（公共子表达式消除），compile 生成 SSA 指令；输入顺序由压平顺序决定，不由 add_input 决定。
• 它不懂求导，只有 OperationRole 一个标签；求导规则在 tenferro-internal-ops，通过实现给 GraphBuilder 的 PrimitiveRuleBuilder 发射节点。
• tenferro 的 StdTensorOp 由 tenferro-core-ops 的宏从一张 52 行的原语表生成，Operand = ()，从不用 computegraph 执行；运算族以 Extension 变体接入。