DialectConversion Legalizer

本页中的所有地址、符号和偏移都适用于来自 libtpu-0.0.40-cp314 wheel 的 libtpu.so（build-id 89edbbe81c5b328a958fe628a9f2207d，781,691,048 字节，未 strip，.text VA == 文件偏移）。其他版本会不同；请将每个 VA 都视为绑定到该版本。

摘要

当 tpu 方言程序下降到 LLO（tpu → LLO 降低）、到 Mlo DMA 表示（LowerToMlo DMA 桥），或当 SparseCore kernel 下降到 LLVM（LowerToSparseCoreLlvm）时，实际运行转换 pattern 的引擎不是扁平 benefit 的贪心 driver。它是 MLIR 的 DialectConversion 机制，其私有分发器是匿名命名空间中的 OperationLegalizer。该分发器与贪心的 GreedyPatternRewriteDriver（ConversionPatternRewriter）正好有一个结构性差异，本页的目的就是将它钉住：它是深度感知的。贪心 driver 按原始 PatternBenefit 降序尝试 pattern，而 legalizer 按合法化深度升序尝试 pattern，也就是每个候选 pattern 的输出在 IR 完全合法之前还会触发的后续 lowering 链长度。

legalizer 与贪心 driver 共享 PatternApplicator 核心和 Pattern vtable ABI；唯一注入的差异是它传给 PatternApplicator::applyCostModel 的成本函数。因此，重新实现者需要而各个 pass lowering 页面没有携带的两块内容是：整数深度递推（computeOpLegalizationDepth / applyCostModelToPatterns，下文按字节解码）和 ConversionTarget 合法性模型，即 LegalizationAction enum、递归合法 packed bit，以及三个 TPU lowering 的每 pass legal/illegal/dynamically-legal 声明。消费两者的递归 legalize 到不动点 driver 将本页串在一起。

读者应持有教科书式的 MLIR DialectConversion 框架，即 ConversionTarget、TypeConverter、RewritePattern、applyFullConversion，并将本页读作对该框架中 legalizer 如何排序和应用 pattern 的字节级恢复。凡恢复出的行为与朴素的“先试最高 benefit”直觉不同之处（不是这样；深度优先，benefit 只用于打破平局），都会明确指出。

对于重新实现，契约是：

深度递推。 legalizationDepth(op) = min over patterns P rooted at op of (1 + max over ops Q that P produces of legalizationDepth(Q))，其中 legal / 无 pattern 的 op 满足 legalizationDepth(Q)=0，带 memoization，并用 in-progress sentinel 打断环。
排序 + 成本注入。 Pattern 按深度升序 stable-sort，平局用 Pattern+0xc 处的 PatternBenefit 打破；这是与贪心 driver 成本模型的唯一差异。
合法性模型。 LegalizationAction {Legal=0, Dynamic=1, Illegal=2}、48 字节的 LegalizationInfo 记录、isLegal 的 16-bit 返回值及递归合法 bit 0x100，以及 setOpAction/setDialectAction/markOpRecursivelyLegal/setLegalityCallback。
合法化 driver。 OperationLegalizer::legalize 作为递归下降到不动点：一个 pattern 只有在它产生的子树本身也完全可合法化时才算“成功”；深度成本会把最浅的子树放到前面。


分发器	`(anon)::OperationLegalizer`（MLIR 的 `DialectConversion.cpp` 私有）
深度递推	`OperationLegalizer::computeOpLegalizationDepth(OperationName, DenseMap<OperationName,unsigned>&, DenseMap<OperationName,SmallVector<Pattern const*,1>>&)` — `0x1c9607c0`
成本函数	`OperationLegalizer::applyCostModelToPatterns(...)` — `0x1c960940`（返回最小深度，排序 pattern）
排序比较器	`__stable_sort_move` 内部的 `applyCostModelToPatterns::$_0` — `0x1c9614a0`（主键为深度，平局用 benefit 打破）
Legalize driver	`OperationLegalizer::legalize(Operation*)` — `0x1c953820`；`legalizeWithFold` — `0x1c95baa0`
合法性查询	`ConversionTarget::isLegal` — `0x1c957ce0`；`setOpAction` — `0x1c957780`；`markOpRecursivelyLegal` — `0x1c9580a0`
合法性 enum	`ConversionTarget::LegalizationAction {Legal=0, Dynamic=1, Illegal=2}`
Drivers	`mlir::applyFullConversion`（mode=1）— `0x1c958ac0` · `mlir::applyPartialConversion`（mode=0）— `0x1c958a60`
置信度	深度递推 + 合法性模型为 CONFIRMED（字节锚定）；行内另有说明处为 HIGH

两个分发器，一个 Applicator

目的

legalizer 很容易被误读为“应用到 conversion pattern 上的贪心 driver”。它不是。二者共享机制，但按相反的键排序 pattern。本单元先于公式固定二者关系，因为公式只有在这种对比下才有意义。

共享核心与唯一差异

贪心 rewriter 和 conversion legalizer 都在同一个 frozen Pattern 集上驱动同一个 PatternApplicator（0x1c9965c0），并且都通过相同的 Pattern vtable ABI（ConversionPatternRewriter）到达每个 pattern 的 matchAndRewrite。applicator 按 root op 对 pattern 分桶，并在每个桶内按传给 PatternApplicator::applyCostModel 的成本函数所固定的顺序应用它们。两个引擎之间唯一的结构性差异是它们注入哪个成本函数；并且在此之后，legalizer 会递归处理 pattern 产生的 op，而不是运行单个贪心 worklist pass。

分发器	传给 `applyCostModel` 的成本函数	桶内排序顺序	平局处理	引擎
`GreedyPatternRewriteDriver`	`applyDefaultCostModel`（`Pattern+0xc` 处的原始 `PatternBenefit`）	原始 benefit 降序	stable	`mlir::applyPatternsGreedily` `0x1c968400`（驱动 `(anon)::GreedyPatternRewriteDriver` 类）
`OperationLegalizer`（conversion）	`computeLegalizationGraphBenefit::$_0`	合法化深度升序	`Pattern+0xc` 处的 `PatternBenefit`	`0x1c953820`

注意 — legalizer 的偏好反转了贪心 driver 的偏好。 贪心：先尝试最有 benefit 的 pattern，单次 pass。Legalizer：先尝试通向完全合法 IR 的最短链，然后递归处理该 pattern 产生的任何内容。重新实现者如果为 conversion pass 复用贪心成本模型，会产生正确 IR（任何完整路径都能合法化），但会先探索更深的子树，使 legalize driver 所依赖的递归爆炸。深度模型是 conversion 引擎的性能不变量，而不是正确性不变量，但 TPU pass 的 pattern 集是在假设它存在的前提下构建的。

Pattern 结构布局（benefit 在 +0xc，不在 +0x8）

深度排序的平局处理会读取 PatternBenefit，所以必须钉住 Pattern 布局。相关偏移从 Pattern ctor 恢复，并由排序比较器的字节读取确认：

text

Pattern+0x00  rootValue          (RootKind-discriminated pointer / TypeID)
Pattern+0x08  RootKind           (uint32 discriminator; == 1 ⇒ fixed root op)
Pattern+0x0c  PatternBenefit     (uint16)         ← benefit lives HERE
Pattern+0x10  context            (MLIRContext*)
Pattern+0x18  generatedOps.data  (ArrayRef<OperationName>.data)   ← the produced-op set
Pattern+0x20  generatedOps.size  (ArrayRef<OperationName>.size)
```text

> **注意 — `PatternBenefit` 位于 `Pattern+0xc`，而 `+0x8` 是 `RootKind` 判别器，不是 benefit。** 排序比较器（`0x1c9614a0` 处的 `__stable_sort_move`）把平局键读作 `*(_WORD *)(*pair + 12)`，即 `Pattern+0xc` 处的 `uint16`。`Pattern+0x8` 是 `RootKind`（`uint32`），graph builder 和 `computeLegalizationGraphBenefit::$_0` 用 `cmp [Pattern+0x8], 0x1` 测试它，以判定“是否有固定 root op”。（误把 `+0x8` 当成 benefit 很容易发生：在另一个 `SmallDenseMap<Pattern*,PatternBenefit>` 成本缓存 pair 中，该偏移*确实是* benefit，但在 `Pattern` 结构本身中不是。）`impossibleToMatch` sentinel 是全 1 的 `uint16` `0xFFFF`（`PatternBenefit(unsigned)` ctor 会原样存储 raw value，不 clamp）。

`Pattern+0x18`/`+0x20` 处的 `generatedOps` 数组是整个深度递推的输入：它是 pattern 声明自己会创建的 `OperationName` 集合，而一个 pattern 的深度是一加这些 op 中的最坏深度。

---

## 深度递推

### 目的

这就是公式。它是“legalizer”为何独立于“rewriter”存在的核心内容，并且完全从两个成本函数按字节解码得到。该递推是带 memoization 的 DAG 遍历，并用 sentinel 打断环。

### 公式

```text
legalizationDepth(op) =
    0                                            if op is already legal OR has no pattern
    min over patterns P rooted at op of
        ( 1 + max over ops Q that P generates of
                  legalizationDepth(Q) )         otherwise

  · memoized in depthMap (DenseMap<OperationName, unsigned>), each op computed once
  · cycles broken by the in-progress sentinel 0xFFFFFFFF (= effectively +inf,
    so a back-edge to an op under computation never wins the min)

用文字表述：一个已经合法（conversion target 接受它）或没有以它为 root 的 pattern 的 op 深度为 0，它是合法化 graph 的叶子。否则它的深度是将它合法化的最便宜（最小）方式，而单个 pattern 的成本是 1 加上该 pattern 发出的 op 中最坏（最大）的后续合法化深度。因此，深度就是所选 pattern 的输出所触发的后续 lowering 最长链的长度，再对 pattern 选择取最小值。

`computeOpLegalizationDepth` — 每 op driver

OperationLegalizer::computeOpLegalizationDepth(OperationName op, DenseMap<OperationName,unsigned>& depthMap, DenseMap<OperationName, SmallVector<Pattern const*,1>>& graph) 位于 0x1c9607c0。按字节解码的控制流：

// computeOpLegalizationDepth(op, depthMap, graph)   @ 0x1c9607c0
unsigned computeOpLegalizationDepth(OperationName op, depthMap, graph):
    // 1. MEMOIZATION LOOKUP — probe depthMap (DenseMap<OperationName,unsigned>)
    //    linear-probe bucket = ((opHash>>4) ^ (opHash>>9)) & (cap-1)
    if op found live in depthMap:
        return bucket->value           // mov eax,[bucket+8] ; cached depth, done

    // 2. GRAPH LOOKUP — probe graph (op -> SmallVector<Pattern*,1>)
    if op NOT in graph  ||  graph[op].patternCount == 0:
        return 0                       // xor eax,eax ; legal / pattern-less ⇒ depth 0

    // 3. RECURSE — mark in-progress, then cost the patterns
    depthMap.insert(op, 0xFFFFFFFF)    // sentinel: "currently computing" cycle-breaker
    unsigned d = applyCostModelToPatterns(graph[op].patterns, depthMap, graph)
    depthMap[op] = d                   // store final depth back into the bucket
    return d
```text

步骤 1 是缓存命中（`return *((unsigned int *)bucket + 2)`，bucket 值在 `+0x8`）。步骤 2 在 op 不在 graph 中*或*其 pattern-list 计数（`graph-bucket+0x10`）为零时返回 `0`：**合法或无 pattern 的 op 是深度 0 的叶子。** 步骤 3 是关键部分：它先插入 `op → 0xFFFFFFFF`（供给 `lookupOrInsertIntoBucket` 的 `v25[0] = -1` store），然后才递归，因此如果递归再次进入 `op`（A 的 pattern 产生 B，而 B 的 pattern 又产生 A），内部查找会命中 sentinel；由于它是最大 `unsigned`，永远无法赢得 `min`，所以会终止环而不会堆栈溢出。随后来自 `applyCostModelToPatterns` 的真实深度会覆盖 sentinel。

### `applyCostModelToPatterns` — 成本 + 排序

`OperationLegalizer::applyCostModelToPatterns(SmallVector<Pattern const*,1>& patterns, depthMap, graph)` 位于 `0x1c960940`。这是*那个*深度感知成本函数。它运行三趟，并返回每 pattern 深度的最小值。

```c
// applyCostModelToPatterns(patterns, depthMap, graph)   @ 0x1c960940
unsigned applyCostModelToPatterns(patterns, depthMap, graph):
    SmallVector<pair<Pattern*,unsigned>, 4> local;
    unsigned minDepth = 0xFFFFFFFF;                  // running global min (r14d)

    // PASS 1 — per-pattern depth
    for Pattern* p in patterns:
        unsigned d = 1;                              // base: a pattern is at least depth 1
        for OperationName gen in p->generatedOps:    // Pattern+0x18 data / Pattern+0x20 count
            unsigned childDepth = computeOpLegalizationDepth(gen, depthMap, graph);
            d = max(d, childDepth + 1);              // inc + cmova
        // (if generatedOps is empty, d stays 1)
        local.emplace_back({p, d});                  // growAndEmplaceBack pair
        minDepth = min(minDepth, d);                 // cmovb

    // PASS 2 — stable sort (ascending depth, then ascending PatternBenefit)
    std::stable_sort(local, $_0);                    // 0x1c9611c0 -> 0x1c9614a0

    // PASS 3 — rebuild the input `patterns` vector in sorted (depth-cheapest-first) order
    patterns.clear();
    for (p, d) in local: patterns.push_back(p);
    return minDepth;                                 // = legalizationDepth(op)

每一步都在反编译中得到确认：每 pattern 的 d = 1 初始化（v37[0] = 1）、内部的 childDepth + 1 然后取 max（v11 = computeOpLegalizationDepth(...) + 1; if (d > v11) v11 = d）、空 generatedOps 分支保持 d = 1、{pattern, depth} pair 的 growAndEmplaceBack<Pattern const*&, unsigned&>、运行中的 min（if (depth < minDepth) minDepth = depth，种子为 0xFFFFFFFF）、__stable_sort、输入 vector 重建（patterns+0x8 处的计数被清零后重新 push），以及 return minDepth。

排序比较器 — 两个键

比较器 $_0（内联进 0x1c9614a0 处的 __stable_sort_move）是在 pair<Pattern*, unsigned depth> 上的双键 strict-weak ordering：

// $_0(lhs, rhs) — strict weak ordering, byte-decoded from the 2-element base case
bool less(pair lhs, pair rhs):
    if (lhs.depth != rhs.depth)            // primary key: unsigned depth at pair+0x8
        return lhs.depth < rhs.depth;      //   cmp [lhs+8], [rhs+8]
    // depths equal ⇒ tie-break on PatternBenefit (uint16 at Pattern+0xc)
    return lhs.pattern->benefit < rhs.pattern->benefit;   // movzx WORD [pat+0xc]; cmp; jb
```text

反编译中的 2 元素 base case 精确展示了这一点：它将 `*((_DWORD *)lhs + 2)` 与 `*((_DWORD *)rhs + 2)` 比较（`pair+0x8` 处的 `unsigned` depth），并且*只有在二者相等时*才落到比较 `*(_WORD *)(lhs->pattern + 12)` 与 `*(_WORD *)(rhs->pattern + 12)`（`Pattern+0xc` 处的 `uint16` benefit）。结果是：**通向完全合法 IR 的最短转换链排在最前**，而在相同深度的 pattern 之间，存储的较低 benefit 排在最前。

> **注意 — 深度始终支配 benefit。** 深度为 1、benefit 为 0 的 pattern 会排在深度为 2、benefit 为 `0xFFFE` 的 pattern 前面，因为深度是主键。这就是 legalizer “深度感知”的具体含义：声明的 `PatternBenefit` 再大也无法把更长的 lowering 链提升到更短的链之前。Benefit 只在相同深度候选之间打破平局。（`0x1c961d60` 处的 `computeLegalizationGraphBenefit::$_0` 如何把结果深度编码回 applicator 的 stable-sort 所消费的 16-bit `PatternBenefit`，即直接深度还是反转的 `maxDepth-depth`，其结构已恢复，但精确的 `depth→uint16` 算术没有追踪到 store：该编码步骤为 **LOW**。这不影响上面的排序语义，后者由 legalizer 自己的比较器按字节确认。）

### `buildLegalizationGraph` — 递推的输入

递推遍历的两个 `DenseMap` 在合法化开始前构建。`buildLegalizationGraph::$_0`（`0x1c95eea0`，每 pattern visitor）通过 `PatternApplicator::walkAllPatterns` 遍历 frozen 集中的每个 native `Pattern`。对于每个 pattern，它读取 root `OperationName`（当 `Pattern+0x8` 处的 `RootKind == 1` 时），询问 `ConversionTarget`（`getOpInfo`，`0x1c957a20`）该 op 是否已经合法（graph *叶子*），并将 pattern 插入：

```text
graph : DenseMap<OperationName, SmallVector<Pattern const*,1>>
        op  ->  patterns rooted at op            (consumed by computeOpLegalizationDepth)
        pattern -> generated ops                 (from Pattern+0x18 / +0x20)

这是深度递推遍历的有向依赖 graph（op → {patterns} → {produced ops}）。computeLegalizationGraphBenefit::$_0（0x1c961d60）是 legalizer 传给 PatternApplicator::applyCostModel 的 function_ref：它读取 pattern 的 RootKind，在 graph 中查找 root op，并返回由深度派生的 PatternBenefit，这正是把共享 applicator 变成深度感知 applicator 的注入点。

ConversionTarget 合法性模型

目的

深度递推的深度 0 基例（“op 已经合法”）由 ConversionTarget 决定。本单元钉住合法性 enum、存储记录、isLegal 的 packed 返回值，以及三个 TPU pass 用来声明其 legal/illegal/dynamically-legal 集合的 API。

LegalizationAction enum

ConversionTarget::LegalizationAction 是一个真实的嵌套 enum（mangled 名称 ConversionTarget::LegalizationAction 出现在 setOpAction/setDialectAction/setLegalityCallback 签名中）。从 setOpAction（0x1c957780）、getOpAction（0x1c9579a0）和 isLegal（0x1c957ce0）钉住：

值	动作	`isLegal` 行为
`0`	Legal	静态合法；`isLegal` 返回 `0x1`（如果递归合法则加 `+0x100`）
`1`	Dynamic	调用每 op 的 `std::function<optional<bool>(Operation*)>` 合法性 callback；`isLegal` 执行 `call [OpInfo+0x28]`，然后测试 optional-has-value bit 和低位（legal）bit
`2`	Illegal	`isLegal` 返回 `0` ⇒ 该 op 必须匹配 conversion pattern

LegalizationInfo 记录 + 存储

target 将合法性存储为 SmallVector<pair<OperationName, LegalizationInfo>>，并由旁侧 DenseMap<OperationName, unsigned> 建索引。setOpAction（0x1c957780）确认该记录为 48 字节，字段如下：

text

LegalizationInfo (48 bytes, per op)
  +0x00  OperationName             (the keyed op)
  +0x08  uint32  action            (LegalizationAction 0/1/2)     ← setOpAction writes here
  +0x18  (zeroed on insert)
  +0x20  std::function legalityCallback storage (policy fn pointer + data)
  +0x28  legalityCallback invocable (default = __empty_func on a static-only entry)
  recursivelyLegal flag is packed into the getOpInfo return
```text

`setOpAction` 在 index map 中查找 op；如果是新 op，则增长 `SmallVector`（`growAndEmplaceBack<piecewise_construct_t, tuple<OperationName const&>, tuple<>>`），将 callback `std::function` 零初始化为 empty policy func；然后把 action `a3` 写入 `info+0x8`。48 字节 stride（`48 * index`）和 action store `*(_DWORD *)(result + 8) = a3` 都在字节层面可见。

### 合法性 API

| 函数 | VA | 作用 |
|---|---|---|
| `ConversionTarget::setOpAction(OperationName, LegalizationAction)` | `0x1c957780` | 设置单个 op 的 action |
| `ConversionTarget::setDialectAction(ArrayRef<StringRef>, LegalizationAction)` | `0x1c957880` | 按名称设置整个 dialect 的 action（例如将 `llo` 标记为 Legal） |
| `ConversionTarget::getOpAction(OperationName)` | `0x1c9579a0` | 读取一个 op 的 action |
| `ConversionTarget::getOpInfo(OperationName)` | `0x1c957a20` | 取出 `LegalizationInfo`（同时 pack 递归合法 flag） |
| `ConversionTarget::isLegal(Operation*)` | `0x1c957ce0` | 16-bit packed 合法性查询（见下） |
| `ConversionTarget::markOpRecursivelyLegal(OperationName, std::function<optional<bool>(Operation*)>)` | `0x1c9580a0` | 标记递归合法 + 可选 callback |
| `ConversionTarget::setLegalityCallback(ArrayRef<StringRef>, std::function<optional<bool>(Operation*)>)` | `0x1c9583c0` | 安装动态合法性 predicate |
| `ConversionTarget::addLegalOp<...>` / `addIllegalOp<...>` | many（可变参数模板） | 固定 op 包上对 `setOpAction` 的语法糖 |

可变参数 `addLegalOp<...>` / `addIllegalOp<...>` 实例化在二进制中很多（例如 `0x167508a0` 处的 `addIllegalOp<scf::ForOp, IfOp, IndexSwitchOp, ParallelOp, WhileOp, ExecuteRegionOp>`），每个都是对包内每个 op 调用 `setOpAction` 的薄转发器。

### isLegal 的 packed 16-bit 返回值

`isLegal`（`0x1c957ce0`）返回一个 legalize driver 作为 16-bit word 读取的值：

```text
bit 0   (0x001)  legal-now
bit 8   (0x100)  recursively-legal  (the op's whole sub-tree is legal; do not descend)

对于 Dynamic op，isLegal 调用 LegalizationInfo+0x28 处的每 op callback，并测试 eax & 0x100 作为 optional-has-value bit，然后读取低位。legalize driver 用 cmp ecx, 0x100; jae 在递归合法 bit 上分支，即大于等于 0x100 表示“递归合法，遍历 children 然后停止”。

每 Pass 合法性声明

三个 TPU conversion pass 各自构造一个 ConversionTarget 并声明自己的合法集合。这些声明从每个 pass body 中的 setOpAction/setDialectAction/markOpRecursivelyLegal/addDynamicallyLegalOp 调用统计恢复而来。三者都使用 applyFullConversion，残留的 illegal op 会中止 pass。

LowerToLLO

createLowerToLLOPass（tpu → LLO 降低）；合法性声明已根据 addDynamicallyLegalOp<…> typeinfo 名称重新钉住：

实体	动作	机制
`llo` dialect（整体）	Legal	`setDialectAction(["llo"], 0)`
`scf.{If,For,While,Condition,Yield}`	Dynamic	`addDynamicallyLegalOp` — 当 region/yield 类型在已转换集合中时合法
`func.{FuncOp,ReturnOp}`	Dynamic	`addDynamicallyLegalOp` — 当 arg + result 类型已转换时合法
`builtin.unrealized_conversion_cast`	Legal	允许在中转过程中存在（最后 reconcile）
所有 `tpu` / `arith` / `math` / `vector` / `cf` / ...	Illegal	默认 ⇒ 必须匹配 pattern

Driver：applyFullConversion（mode = 1）—— 如果任何 tpu.* op 存活则中止。

LowerToMlo

LowerToMloPass::runOnOperation（0x1322b200）。legal-dialect 集是 MloConversionTarget（ctor 已确认：mlir::tpu::MloConversionTarget::MloConversionTarget(MLIRContext&)；insertLegalDialects(DialectRegistry&) 已确认）：

实体	动作	机制
`MloConversionTarget` legal dialects	Legal	ctor `SmallDenseMap<TypeID>`：Builtin、`LLVM::LLVMDialect`、`sparse_core::LlvmTpuDialect`、`arith`、`cf`、`func`、`math`、`memref`、`scf`、`sparse_core::ScDialect`、`vector`
`func.FuncOp`	Dynamic	`addDynamicallyLegalOp<func::FuncOp>` — 当 arg/result 类型已转换时合法
`builtin.unrealized_conversion_cast`	Dynamic	`addDynamicallyLegalOp<UnrealizedConversionCastOp>`
2× `setOpAction` + 2× `setLegalityCallback`	mixed	每 op override（具体 op 名称 + predicate 未逐 lambda 解码）

Type converter：共享的 populateTypeConverter，包含 10 个 registerConversion 条目（TupleType、IndexType、FloatType、LLVM::LLVMPointerType、tpu::DMASemaphoreType、tpu::SemaphoreType、sparse_core::WordType、IntegerType、VectorType、MemRefType），外加 3 个 registerTypeAttributeConversion（BaseMemRefType ↔ {tpu::MemorySpaceAttr, sparse_core::MemorySpaceAttr, IntegerAttr}）。Patterns：populateTpuToMloConversionPatterns（0x1322c920，约 180）+ populateSCFStructuralTypeConversions。Driver：applyFullConversion（mode = 1）。详情：LowerToMlo DMA 桥。

sparse_core → LLVM

LowerToSparseCoreLlvmPass::runOnOperation（0x13566d00；CreateLowerToSparseCoreLlvmPass 已确认）。该 pass 运行两次 applyFullConversion，先是 SCF→CFG leg（lowerScfToCfg），然后是 LLVM leg：

实体	动作	机制
`LLVMConversionTarget`（`llvm` dialect）	Legal	`mlir::LLVMConversionTarget(ctx)` 将 LLVM dialect 标记为合法
`scf.{for,if,parallel,while,index_switch}`	Recursively-Legal	`markOpRecursivelyLegal` ×5（op-name 字符串按字节精确读出：`scf.for`、`scf.if`、`scf.parallel`、`scf.while`、`scf.index_switch`）
`scf.{If,Parallel,While,IndexSwitch}`	Dynamic	`addDynamicallyLegalOp<scf::IfOp, ParallelOp, WhileOp, IndexSwitchOp>`
4× `setOpAction` + 2× `setLegalityCallback`	mixed	每 op override
arith/math packed-operand ops（40+）	Dynamic	`PackedOperandsLowering::AddDynamicallyLegalAluEpOps<Op, UnpackFOp, PackFOp>` / `AddDynamicallyLegalCmp<Op, {UnpackFOp,PackFOp} or {UnpackSIOp,PackSIOp}>` — 当且仅当 operands 已经 unpacked 时合法

Type converter：mlir::LLVMTypeConverter(ctx, LowerToLLVMOptions) + 针对 SparseCore 类型的自定义 registerConversion：I32PairType（1:N → 2×i32）、TupleType（1:N → element types）、VectorType、Float8E4M3B11FNUZ/Float8E4M3FN/Float8E5M2、WordType，外加 registerTypeAttributeConversion BaseMemRefType ↔ sparse_core::MemorySpaceAttr。Patterns：populateSCFToControlFlowConversionPatterns + populateFinalizeMemRefToLLVMConversionPatterns + 115 个 SCConvertOpToLLVMPattern<Op>。详情：LowerToSparseCoreLlvm。

注意 — SparseCore pass 是唯一大量使用 1:N 类型路径的地方。 I32PairType → 2×i32 和 TupleType → element types 是真正的一对多转换；populateSCFStructuralTypeConversions 会为产生的 ValueRange 适配 SCF region 签名。TensorCore LowerToLLO/Mlo 类型集合绝大多数是 1:1（vector → 一个 vreg、i1 → predicate、index → i32、semaphore → llo.semaphore）。关于 ConversionPattern slot4（1:1 ArrayRef<Value>）与 slot5（1:N ArrayRef<ValueRange>）分发，请参见 ConversionPatternRewriter。

合法化 Driver

目的

深度成本和合法性模型供给同一个递归函数。本单元钉住 legalize 如何消费它们：它是递归下降到不动点，其中 pattern 只有在它产生的子树本身可合法化时才“成功”，而深度成本存在的目的就是让该递归保持浅层。

`OperationLegalizer::legalize`

OperationLegalizer::legalize(Operation* op) 位于 0x1c953820：

// OperationLegalizer::legalize(op)   @ 0x1c953820
LogicalResult legalize(Operation* op):
    if ConversionPatternRewriterImpl::isOpIgnored(op):       // 0x1c94e680
        return success                                       // already handled

    uint16 leg = target.isLegal(op)                          // 0x1c957ce0
    if leg >= 0x100:                                         // recursively-legal bit
        walk(op.children)                                    // mlir::detail::walk 0xea2c5e0
        return success                                       // children need no visit

    // not-yet-legal: read the OpConversionMode (set by applyConversion, below)
    mode = rewriterImpl[+0x178][+0x2c]                       // Partial=0, Full=1, Analysis=2
    if mode == 1 (Full):
        legalizeWithFold(op)                                 // 0x1c95baa0, try constant fold first

    // legalizeWithPattern, inlined via three lambdas:
    if PatternApplicator::matchAndRewrite(op, rewriter,      // 0x1c9971e0
                                          canApply=$_0,       //   0x1c95c100
                                          onSuccess=$_1,      //   0x1c95c1a0
                                          onRecurse=$_2):     //   0x1c95c6e0
        return success
    if mode == 2 (Analysis): legalizeWithFold(op) (again)
    else:
        return op.emitError("failed to legalize operation '<name>'")   // 0x1c953a12
```text

三个 lambda 是 `legalizeWithPattern` 的核心（它们的 mangled 符号，即 `OperationLegalizer::legalizeWithPattern::$_1` 和 `$_2`，存在于二进制中，确认了内联）：

- **`$_0` canApply（`0x1c95c100`）** — 测试 `Pattern+0x10` bit `0x4`（`hasBoundedRewriteRecursion`），并维护 in-flight pattern 的 `SmallPtrSet`，用于检测并拒绝将同一 pattern 无界递归应用到同一 op。
- **`$_1` onSuccess（`0x1c95c1a0`）** — 成功匹配后的 rewriter 状态 bookkeeping：`Operation::erase`、`resetState`（`0x1c95bf60`）、清空跟踪 map `DenseSet<UnrealizedConversionCastOp>` 和 `DenseMap<Operation*>`。
- **`$_2` onRecurse（`0x1c95c6e0`）** — 遍历 pattern 产生的*新* op（`mlir::detail::walk<ForwardIterator>`，`0x0ea2c5e0`），并**对每一个递归调用 `legalize`**（两个调用点回到 `0x1c953820`）；如果某个产生的 op 无法合法化，则路由到 `reportNewIrLegalizationFatalError`（符号已确认；失败消息由对 offending op 名称执行 `llvm::join` 组装，而不是作为单个静态字符串发出）。只有当**每个**产生的 op 本身都被合法化时才返回 `success`。

### `legalizeWithFold`

`legalizeWithFold`（`0x1c95baa0`）是常量折叠尝试：`startOpModification` → `OpBuilder::tryFold`（`0x1d8563e0`）→ `finalizeOpModification` → `replaceOp`；成功时它会**递归合法化**物化出的 constant op，而 `cancelOpModification` 会在 fold 失败时回滚。

> **陷阱 — pattern 并不是只要 matched 就“成功”。** 只有当所选 pattern 产生的*整个子树*本身完全合法化时，`legalize` 才会对一个 op 返回 success（`$_2` recurse 只有在每个 produced op 都 legalize 时才返回 success）。这就是深度成本重要的原因：legalizer 无论如何都会递归进入 produced op，因此把 produced 子树*最浅*（KF depth）的 pattern 放到前面，可以最小化预期递归深度，也减少更深候选路径走入 dead-end 时必须回滚的 speculative rewriting 数量。重新实现者如果按任意顺序应用 pattern，会得到正确 IR，但在有多条合法 lowering 链的 op 上会出现病态递归。

### applyFullConversion / applyPartialConversion → mode

pass driver 选择 legalizer 读取的 mode：

| Driver | Mode | 行为 |
|---|---|---|
| `mlir::applyFullConversion(op, target, patterns, config)` | `Full = 1` | 尝试 fold；对任何未合法化 op **报错** |
| `mlir::applyPartialConversion(op, target, patterns, config)` | `Partial = 0` | 将未合法化 op 留在原处，并记录它们 |
| （internal）Analysis | `Analysis = 2` | 分析可合法化性而不提交 |

`applyConversion` 将 `OpConversionMode` 存入 `OperationConverter` frame（`legalize` 读取的字段是 `rewriterImpl[+0x178][+0x2c]`），并在注册了 action handler 时用 `MLIRContext::executeActionInternal<ApplyConversionAction>` 包裹整个运行。**所有三个 TPU lowering pass 都使用 `applyFullConversion`**，残留的 `tpu.*` / `mlo.*` op 会中止 pass。`mlir::applyFullConversion(Operation*, ConversionTarget const&, FrozenRewritePatternSet const&, ConversionConfig)`（`0x1c958ac0`）和 `mlir::applyPartialConversion(...)`（`0x1c958a60`）都是对 `0x1c958840` 处内部 driver `applyConversion(ArrayRef<Operation*>, ConversionTarget const&, FrozenRewritePatternSet const&, ConversionConfig, (anon)::OpConversionMode)` 的薄 wrapper，后者把 `OpConversionMode` 作为尾随参数携带。

---

## 函数映射

| 函数 | VA | 作用 |
|---|---|---|
| `OperationLegalizer::computeOpLegalizationDepth` | `0x1c9607c0` | 每 op 深度递推（memoized，用 sentinel 断环） |
| `OperationLegalizer::applyCostModelToPatterns` | `0x1c960940` | 每 pattern 深度 + stable sort + min |
| `applyCostModelToPatterns::$_0`（在 `__stable_sort_move` 中） | `0x1c9614a0` | 比较器：主键为深度，平局用 benefit `+0xc` 打破 |
| `buildLegalizationGraph::$_0` | `0x1c95eea0` | 构建 `op → patterns → produced ops` graph |
| `computeLegalizationGraphBenefit::$_0` | `0x1c961d60` | 注入到 `applyCostModel` 的成本 `function_ref` |
| `OperationLegalizer::legalize` | `0x1c953820` | 递归 legalize-to-fixpoint driver |
| `OperationLegalizer::legalizeWithFold` | `0x1c95baa0` | `tryFold` + 对物化 constant 递归 |
| `ConversionTarget::setOpAction` | `0x1c957780` | 将 `LegalizationAction` 写入 48 字节 `LegalizationInfo+0x8` |
| `ConversionTarget::setDialectAction` | `0x1c957880` | 按名称设置整个 dialect 的 action |
| `ConversionTarget::getOpAction` | `0x1c9579a0` | 读取 op 的 action |
| `ConversionTarget::getOpInfo` | `0x1c957a20` | 取出 `LegalizationInfo`（+ 递归合法 pack） |
| `ConversionTarget::isLegal` | `0x1c957ce0` | 16-bit packed 合法性（bit0 legal，bit8 recursive） |
| `ConversionTarget::setLegalityCallback` | `0x1c9583c0` | 安装动态合法性 predicate |
| `mlir::applyFullConversion` | `0x1c958ac0` | mode=1 driver（对残留报错） |
| `mlir::applyPartialConversion` | `0x1c958a60` | mode=0 driver（记录残留） |
| `applyConversion`（internal） | `0x1c958840` | 携带 mode 的 conversion 入口 |
| `MloConversionTarget` ctor / `insertLegalDialects` | confirmed symbols | LowerToMlo legal-dialect 集 |
| `LowerToSparseCoreLlvmPass::runOnOperation` | `0x13566d00` | SparseCore → LLVM driver（2× full conversion） |

---

## 本页未涵盖内容

- **`computeLegalizationGraphBenefit::$_0`（`0x1c961d60`）中精确的 `depth→uint16` `PatternBenefit` 算术**，即它是直接存储深度，还是存储反转的 `maxDepth - depth` 以便 applicator 的降序 stable-sort 产生升序深度。结构已恢复；store 未追踪到（**LOW**）。legalizer 自己的比较器顺序（深度主键，benefit 平局）已按字节确认，不受影响。
- **LowerToMlo 每 op 动态合法性 lambda body**（2× `setLegalityCallback` / 2× `setOpAction` 的 op 名称 + predicate）。调用统计已恢复；lambda body 未逐个反编译（**MEDIUM**）。参见 [DMA 桥](lower-to-mlo-dma-bridge.md)页面上提出的 follow-up。
- **materialization 机制**，即 `buildUnresolvedMaterialization`、`builtin.unrealized_conversion_cast` 桥、`reconcileUnrealizedCasts`，以及 1:N `convertTypeImpl` 双缓存。这些属于 rewriter/type-converter substrate；参见 [ConversionPatternRewriter](conversion-pattern-rewriter.md)。
- **`ConversionConfig` 结构字段偏移**（`applyFullConversion` 的 by-value arg：`buildMaterializations`、`legalizableOps`/`unlegalizedOps` 集合、`notifyCallback`、`allowPatternRollback`）。按值传递（≥0x40 字节）；这里只钉住 `OpConversionMode`。
- **每 op rewrite body**，即每个 `tpu.*` 降低到什么，是 [tpu → LLO 降低](tpu-to-llo-ods.md)、[LowerToMlo DMA 桥](lower-to-mlo-dma-bridge.md) 和 [LowerToSparseCoreLlvm](lower-to-sparsecore-llvm.md) 的主题，不属于本页。

---

## 交叉引用

- [TPU 编译器](overview.md) — 该 legalizer 在 Phase 2a 内驱动的五阶段 dialect 下降。
- [tpu MLIR 方言](tpu-dialect-and-ops.md) — 源 dialect，其 op 由 legalizer 排序并应用 pattern。
- [tpu → LLO 降低](tpu-to-llo-ods.md) — LowerToLLO conversion target，其合法性声明由表 2 第 1 行概括。
- [LowerToMlo DMA 桥](lower-to-mlo-dma-bridge.md) — `MloConversionTarget` legal-dialect 集与共享的 `populateTypeConverter`。
- [LowerToSparseCoreLlvm](lower-to-sparsecore-llvm.md) — SparseCore → LLVM target、唯一繁重的 1:N 路径，以及 `markOpRecursivelyLegal` SCF 集合。
- [ConversionPatternRewriter](conversion-pattern-rewriter.md) — 共享的 `PatternApplicator` 核心、`Pattern` vtable ABI、rollback/rewrite-log substrate，以及 1:1 与 1:N `ConversionPattern` slot 分发。
- **Binary:** `extracted/libtpu-0.0.40-cp314-cp314-manylinux_2_31_x86_64/libtpu/libtpu.so`（build-id `89edbbe81c5b328a958fe628a9f2207d`）
- **索引条目:** Part V — Compiler: Lowering & Optimization Passes / MLIR lowering chain — [返回索引](../index.md)

DialectConversion Legalizer ​

摘要 ​

两个分发器，一个 Applicator ​

目的 ​

共享核心与唯一差异 ​

Pattern 结构布局（benefit 在 +0xc，不在 +0x8） ​

computeOpLegalizationDepth — 每 op driver ​

排序比较器 — 两个键 ​

ConversionTarget 合法性模型 ​

目的 ​

LegalizationAction enum ​

LegalizationInfo 记录 + 存储 ​

每 Pass 合法性声明 ​

LowerToLLO ​

LowerToMlo ​

sparse_core → LLVM ​

合法化 Driver ​

目的 ​

OperationLegalizer::legalize ​

DialectConversion Legalizer

摘要

两个分发器，一个 Applicator

目的

共享核心与唯一差异

Pattern 结构布局（benefit 在 +0xc，不在 +0x8）

`computeOpLegalizationDepth` — 每 op driver

排序比较器 — 两个键

ConversionTarget 合法性模型

目的

LegalizationAction enum

LegalizationInfo 记录 + 存储

每 Pass 合法性声明

LowerToLLO

LowerToMlo

sparse_core → LLVM

合法化 Driver

目的

`OperationLegalizer::legalize`