Bundle 模调度

地址适用于 libtpu-0.0.40-cp314 wheel 中的 libtpu.so（build-id 89edbbe81c5b328a958fe628a9f2207d）。其他版本会不同。所有 .text 地址都是虚拟地址；对此二进制，.text VMA == 文件偏移 0xe63c000。

摘要

TPUMachinePipeliner 是 TPU 后端在指令选择之后、LLO/MachineInstr bundle packer 之前，对内层循环运行的 LLVM 侧软件流水线器。它是第三个正交的调度机器，不同于 XLA 侧列表调度器，也不同于逐周期 bundle packer：packer 回答的是*“每个 op 在一个周期中占用哪个 VLIW slot？”，而模调度器回答的是“稳态循环内核横跨多少个周期，以及每个 op 的哪次迭代副本位于哪个周期？”*。这个跨度是启动间隔（II），即相邻循环迭代进入流水线之间的周期数；每个 op 的迭代偏移是 stage。一旦找到 II 和 stage 分配，expander 会把循环重写成 prologue / steady-state kernel / epilogue（或者在硬件计数的代际上，把内核留给硅上的循环计数器驱动）。

熟悉 LLVM 的读者应记住一个类比和两个差异。类比是：这是经典的 Lam 风格迭代模调度，即从资源和递归下界选取最小 II，尝试把每个节点放进该 II 的循环调度中；如果放置失败，就增大 II 并重试。第一个差异是：每个 II 的合法性测试是模预约表（ModuloHazardRecognizer），它把每个已调度周期 c 映射到列 c mod II，并拒绝两个会在同一列预订同一功能单元的 op。与上游 MachinePipeliner 的差异在于，TPU recognizer 复用了 bundle packer 和 bundle-aware cost model 读取的同一张 MCWriteProcResEntry proc-resource 表，但粒度是逐周期而非逐 bundle。第二个差异是：存在两个 TPU 模 DAG（一个贪心的 swing 调度器和一个基于 force 的 slack fallback）以及六个 expander，而且 expander 的选择由循环是硬件计数的 BarnaCore 循环还是软件回边来门控（见 hardware loop-counter）。

本页是第 VIII 部分中 II 搜索和模预约检查的锚点：initialize 中 min-II = max(5 calculators) 的组合、findSchedule 中 for (II = lower; II < upper; ++II) 的递增循环、ModuloHazardRecognizer 中 slot = cycle mod II 的预约测试、checkPostModuloSchedule 结构验证器及其由返回码驱动的 ++II（以及单 stage 的 rc=2 情况，它会放弃该循环的流水线化），以及已接受的 II 如何流入 emitScheduleForLoop 的 expander 分发。每个已调度周期最终变成的逐周期 bundle 由 bundle packer 负责；各计算器消耗的 proc-resource 周期数来自 bundle-aware cost model。

对于重新实现，契约是：

min-II = max(ResourceMII, FillResourceMII, SuperPassMII, LargestLatencyMII, per-gen-floor, RecurrenceMII)：在 initialize（0x13c36160）中为每个循环计算一次。资源下界是 ceil(busiest-FU cycles / units)；递归下界是 ceil(cycle-latency / iteration-distance)。这些累积到 [dag+0xebc]（下界）。上界 [dag+0xeb8] 是来自 fastBundlePackingCost 的 bundle-packing-cost 估计，可被覆盖为 IIUpperBound + 1。
II 搜索是 for (II = lowerII; II < upperII; ++II)（findSchedule，0x13c367c0）。对每个 II，它重置 hazard recognizer（setII(II)），按优先级顺序调度每个 SU，运行结构验证器，并接受第一个通过资源、stage 数、FIFO 和寄存器压力检查的 II。一个重排序失败的节点可以在同一 II 上最多重试 swing-modulo-retry-same-node（=64）次，然后 II 才会增大。
每个 II 的合法性测试是模预约表：ModuloHazardRecognizer::canEmitInstructionResourceInternal（0x13c14d60）计算 slot = cycle mod II（用 II = [hr+0x40] 做 idiv），遍历该 op 的 proc-resource 条目，并在按 slot 作为键的逐 slot 预约位图 DenseMap<int,uint> 中，如果 FU bit 已经被置位则拒绝（return 0）。
checkPostModuloSchedule（0x13c149c0）返回驱动循环的代码：2 = 单 stage（没有跨迭代重叠，因此没有可流水线化内容；findSchedule 返回 no-schedule 哨兵，该循环保持未流水线化），3 = stage 数超过 pipeliner-max-stages → ++II，4 = split-live-range 重试，1 = FIFO 检查通过 → 进入寄存器压力门；干净通过则接受该 II。
已接受的 II 流向 emitScheduleForLoop（0x13ba0ac0），它构建 ModuloSchedule 并分发到六个 expander 之一：面向硬件计数循环的 expandScheduleForBarnaCore，V5+ 上的 rotating-predicate expander（由 EnableRotatingPredicate 门控），或者其他情况下的 peeling / predicated-epilogue expander。


Pass driver	`TPUMachinePipeliner::runOnMachineFunction` @ `0x13ba15e0`
逐循环 emit	`TPUMachinePipeliner::emitScheduleForLoop` @ `0x13ba0ac0`
Swing DAG（主路径）	`TPUScheduleDAGSwingModulo` — ctor `0x13c35ce0`，`initialize` `0x13c36160`，`findSchedule` `0x13c367c0`
Slack DAG（fallback）	`TPUScheduleDAGSlackModulo` — ctor `0x13c23840`，`findSchedule` `0x13c27560`
Min-II driver	`TPUScheduleDAGModulo::startModuloSchedule` @ `0x13c041c0`（upper-II 经 `fastBundlePackingCost` @ `0x13b67ea0`）
Resource MII	`calculateResourceMII` @ `0x13c0bee0` — `ceil(FU-cycles / units)`，对 FU 做 `vpmaxud`
Recurrence MII	`calculateRecurrenceMII` @ `0x13c0ccc0` — `Recurrence[+0x28]` 的最大值，步幅 `0x58`
预约表	`ModuloHazardRecognizer::canEmitInstructionResourceInternal` @ `0x13c14d60`（`slot = cycle mod II`）
`setII`	`ModuloHazardRecognizer::setII` @ `0x13c14d00` → `[hr+0x40] = II`
结构验证器	`checkPostModuloSchedule` @ `0x13c149c0`；FIFO `checkFifoOverflow` @ `0x13c0da00`；stage-0 `checkForStageZeroInstructions` @ `0x13c14900`
DAG 字段偏移	upper-II `[dag+0xeb8]`，lower/min-II `[dag+0xebc]`，current-II `[dag+0xec0]`，Res/Fill-MII scratch `[dag+0xec4]`，Rec-MII `[dag+0xec8]`，stageCount `[dag+0x410]`
置信度	CONFIRMED（字节锚定），除非某行另有说明

Pipeliner 所在位置：三个调度器，一个资源模型

TPU 编译流水线在 LLVM-MIR 侧包含三个独立的调度机器，而模调度器是在其接受的循环上最先运行的一个：

text

instruction selection → MachineInstr
  → TPUMachinePipeliner            (THIS PAGE: software-pipeline inner loops)
       per accepted loop: choose II, assign stages, expand prologue/kernel/epilogue
  → BundlePacker MachineFunctionPass   (per-cycle VLIW packing — see llo-bundle-packing.md)
  → TPUMCCodeEmitter                   (raw bundle bytes)
```text

pipeliner **只**运行在 `analyzeLoopForPipelining`（`0x13c03f00`）→ `TPUInstrInfo::analyzeLoopForTPUPipelining`（`0x13b804c0`）接受的循环上，后者把每个循环分类为硬件计数（BarnaCore / AddressHandler，由硅上的循环计数器驱动回边）或软件计数（TensorCore / SparseCore，显式 IV/compare/branch 回边）。该分类记录在 [hardware loop-counter](../isa/slot-loop.md) 页面上；它选择调度器携带哪个 `PipelinerLoopInfo` 子类，并在下游选择运行哪个 expander。被 pipeliner 拒绝的循环会落回普通列表调度器，并在没有软件流水线化的情况下逐周期打包。

关键的复用事实是：模调度器**没有发明新的资源模型**。它的资源下界（`calculateResourceMII`）和逐周期预约表（`ModuloHazardRecognizer`）都读取 LLVM `MCSchedClassDesc` proc-resource 列表（`MCWriteProcResEntry` 记录：`{ProcResourceIdx, Cycles}`），也就是 bundle packer 的 `ResourceSolver` 和 [bundle-aware cost model](../cost/bundle-aware-cost.md) 消耗的同一张 `TPUStages` 表。差异在于粒度：cost model 把一个 *bundle* 归约成周期数，packer 统计*一个周期中的 slot*，而模调度器为*横跨 II 列的循环内核中的占用*定价。

driver `runOnMachineFunction`（`0x13ba15e0`）构建逐循环 proc-resource 深度模型（`addProcResourceDepths`，`0x13c14ae0`），然后按 preorder 对每个循环运行**主** swing 调度器（`TPUScheduleDAGSwingModulo`）；如果达到的 II 相对 `min-ii-slack` 门太松，它会撤销 swing 结果，并重新运行**fallback** slack 调度器（`TPUScheduleDAGSlackModulo`）。后者是一个基于 force 的调度器，能以 eject/retry 工作为代价找到更紧的放置。`TPUMachinePipelinerSuperPass`（`0x13ba6280`）可选地克隆函数，发现某个循环所有副本之间的共同 II，并通过 `getSuperPassMII` 反馈回来，让每个副本共享同一个 II。

---

## 步骤 1：最小 II（`initialize` 和 `startModuloSchedule`）

II 的下界是若干独立下界的最大值，任何合法循环调度都必须满足这些下界。`TPUScheduleDAGSwingModulo::initialize`（`0x13c36160`）调用 `startModuloSchedule` 设置上界，枚举 recurrences，然后组合五个下界计算器。下面是从 `initialize` 反编译出的组合（DWORD 字段索引相对于 `TPUScheduleDAGSwingModulo` 对象；`this + N` 是字节偏移 `4*N`）：

```c
// TPUScheduleDAGSwingModulo::initialize(MBB)  @ 0x13c36160   (field offsets in DWORDs)
startModuloSchedule(dag, MBB, MLI, AA, FifoFillAnalysis);   // sets upper-II at this[942] (0xeb8)
findBackedges(dag, MBB, AA);                                // loop-carried SDeps
findRecurrences(dag, MBB, /*flag=*/0);                      // enumerate dependency cycles

this[946] = calculateRecurrenceMII(dag, MBB, recurrences);  // [dag+0xec8] RecMII
this[945] = calculateResourceMII(dag, MBB, /*flag=*/0);     // [dag+0xec4] scratch = ResMII
this[945] = calculateFillResourceMII(dag, MBB, ResMII);     // [dag+0xec4] scratch = FillResMII

this[943] = max(FillResMII, RecMII);                        // [dag+0xebc] lower-bound seed
this[943] = max(this[943], getSuperPassMII(dag, MBB));      // [dag+0xebc] max= SuperPassMII
if (!subtarget_is_barnacore /* [subtarget+290]==0 */) {     // largest-latency + gen-floor are NOT-BarnaCore-only
    this[943] = max(this[943], calculateLargestLatencyMII(...));  // max= LargestLatencyMII
    if (unk_224E34D0 == 1)                                  // per-gen virtual floor: (*subtarget+0x308)()+2
        this[943] = max(this[943], subtargetMIIFloor() + 2);
}
if (unk_224E3518)                                           // second optional floor (dword_224E3588)
    this[943] = max(this[943], dword_224E3588);
// this[943] (0xebc) is the LOWER bound; this[942] (0xeb8) is the UPPER bound.

// TPUScheduleDAGModulo::startModuloSchedule(...)  @ 0x13c041c0  (tail)
dag[10 /*+0x28*/] = fastBundlePackingCost(MBB, ...);   // bundle-packing-cost upper estimate
if (word_224E3180 /* IIUpperBound cl::opt present */)
    dag[10] = dword_224E31F0 /*IIUpperBound*/ + 1;     // override the upper bound
// this inner-DAG [+0x28] becomes the SwingModulo this[942] (0xeb8) upper bound.
```text

> **注：偏移标签已按反编译校正。** 累积的字节锚点如下：`[dag+0xebc]`（`this[943]`）是**lower / minimum** II（累积 resource、fill-resource、super-pass、largest-latency 和 per-gen-floor 的最大值），而 `[dag+0xeb8]`（`this[942]`）是**upper** bound（`fastBundlePackingCost` 估计，或 `IIUpperBound+1`）。`this[944]`（`0xec0`）是运行中的 current II；`this[945]`（`0xec4`）是 resource/fill scratch；`this[946]`（`0xec8`）是 recurrence MII。

### Resource MII — `calculateResourceMII`（`0x13c0bee0`）

资源下界由最繁忙的功能单元施加：如果循环体中的所有 op 合计需要某个拥有 `U` 个并行单元的功能单元执行 `C` 个周期，那么任何调度都不可能比每 `ceil(C / U)` 个周期发射一次更快，因此 `II >= ceil(C / U)`。反编译会遍历每个 SU（跳过 `G_PHI`（`SchedClass` 字段 == 74）以及通过 `MachineInstr::hasPropertyInBundle(0x400)` 检测到的 bundle-marker op），从 sched-class 表读取其 `MCWriteProcResEntry` 列表，并为每个 proc-resource 递增逐 FU 使用计数器。单元数来自 proc-resource unit mask 的 `__popcnt`，下限为 1：

```c
v33 = __popcnt(unit_mask);          // number of parallel units of this FU
if ((unsigned)v33 < 2) v33 = 1;     // getProcResourceUnits: 1 if zero/one unit
ResMII_for_FU = ceil(usage[FU] / v33);

最终归约是对所有 FU bucket（[r14+0x270]..[r14+0x354]）做 SIMD vpmaxud 级联，再加上少量标量最大值；也就是 ResMII = max over FUs of ceil(usage[FU] / units[FU])。FillResourceMII 路径通过 MCBundleInfoFactory::create 在其上叠加 FIFO-fill 占用，计入跨迭代 FIFO 驻留（与验证器的 checkFifoOverflow 保护的硬件 FIFO 相同）。两者都写入 [dag+0xec4] scratch，结果折入 [dag+0xebc] 下界。

Recurrence MII — `calculateRecurrenceMII`（`0x13c0ccc0`）

一个总延迟为 L、跨越 D 次迭代的循环携带依赖环，不能比 ceil(L / D) 更快地发射；该循环依赖必须在 D 个内核内闭合。findRecurrences（0x13c07ae0）使用来自 findBackedges 的回边枚举依赖环，并对每个环调用 computeMinDist（0x13c06ea0），后者是 Bellman-Ford 风格的最长路径松弛，产生该环的 latency-vs-distance 比率。该比率按 recurrence 存储；calculateRecurrenceMII 随后取最大值：

// calculateRecurrenceMII @ 0x13c0ccc0  (Recurrence struct stride = 0x58 = 88 bytes)
int RecMII = 0;
for (Recurrence &r : recurrences)          // SIMD vpmaxsd over r[+0x28]
    RecMII = max(RecMII, *(int*)((char*)&r + 0x28));   // per-recurrence MII at +0x28
return RecMII;                              // 0 if no recurrences
```text

字节证据是：SIMD 路径每个元素步进 `88` 字节并读取偏移 `+40`（`0x28`）处的 DWORD，用 `vpmaxsd` 归约；尾部循环做同样的标量 max。recurrence 结构体为 `0x58` 字节；每个 recurrence 的 MII 位于 `[Recurrence+0x28]`。

因此 `min-II = max(ResMII, FillResMII, SuperPassMII, RecMII, [if not BarnaCore: LargestLatencyMII, per-gen-floor])`。该累积在 `initialize` 中字节精确：`[dag+0xebc]` 以 `max(FillResMII, RecMII)` 为种子，然后无条件折入 `getSuperPassMII`；只有**在非 BarnaCore subtarget**（`[subtarget+290]==0`）上，才会加入 `calculateLargestLatencyMII` 和每代虚拟 floor（`unk_224E34D0` 路径，一个 subtarget 虚调用 `+2`）；第二个可选 floor（`unk_224E3518` → `dword_224E3588`）最后折入。最大延迟下界（`calculateLargestLatencyMII`，`0x13c0b840`）是所有 SDep 边的 `getEdgeLatency` 最大值：最长的单条依赖延迟必须能放入一个 kernel window，除非它跨 stage 被隐藏；super-pass 下界（`getSuperPassMII`，`0x13c0ba40`）是 super-pass 若发现了跨函数共享 II 则返回该值，否则返回 `-1`。

---

## 步骤 2：II 递增循环（`findSchedule`，`0x13c367c0`）

`findSchedule(MBB, retries, lowerArg, upperArg)` 把调用方的边界钳制到已计算的 min/max-II，然后向上遍历 `II`，尝试在每个值上构建有效循环调度。压缩后的反编译如下（SwingModulo 对象为 `this`；`this[N]` 是 DWORD 索引 `N`）：

```c
// TPUScheduleDAGSwingModulo::findSchedule(MBB, retries=a3, lowerArg=a4, upperArg=a5)  @ 0x13c367c0
initializeSUnitsComposed(dag.fifo, MBB, ...);
if (decomposed_fifo) decomposeModuloFifo(dag.fifo, MBB);

if (this[942] /*upper-II*/ < upperArg) upperArg = this[942];   // clamp upper down
if (this[943] /*lower-II*/ > lowerArg) lowerArg = this[943];   // clamp lower up
if (lowerArg >= upperArg) return /*fail*/ 0;                   // empty search window

calculateASAPAndALAP(this);                                    // ASAP/ALAP per SU window
ModuloHazardRecognizer *hr = new ModuloHazardRecognizer(maxSchedLatency,
                                                         TwistStageZeroOrdering);
findPriorityOrder(this);                                       // height/mobility order

unsigned II = max(lowerArg, 1);          // II >= 1   ( (a4==0)+a4 )
this[944] = II;                          // [dag+0xec0] current II
int sameNodeRetry = 0;
while (II < upperArg) {
    hr->reset();
    hr->setII(this[944]);                // [hr+0x40] = II
    hr->setPipelinerInfo(this[475]);     // loop-info for stage gating
    schedule_map.clear();
    this[912] = 0;
    resetMinMaxCycle(this);

    bool placed_all = true;
    for (SUnit *su : this->priorityOrder) {           // this[922] count, this[460] array
        if (!scheduleSU(this, su)) {                  // per-II reservation-table placement
            // reordering failure for this node at this II:
            if (++retriesSameNode[su] > MaxRetriesSameNode /*=64, dword_224E4058*/)
                return 0;                             // give up entirely
            placed_all = false; break;                // else fall through to ++II
        }
    }
    if (placed_all) {
        if (decomposed_fifo) scheduleDecomposedFifo(dag.fifo, MBB, ...);
        createScheduleByCycle(this, ...);             // materialize cycle schedule
        if (checkForStageZeroInstructions(dag, MBB, ...) != 1) goto next_II;
        int rc = checkPostModuloSchedule(dag, MBB, ..., /*splitRetry=*/sameNodeRetry==4);
        if (rc == 3) { sameNodeRetry = 0; goto next_II; }     // stage-count exceeded → ++II
        if (rc == 4) {                                        // split-live-range retry
            if (sameNodeRetry != 4) { --this[944]; sameNodeRetry = 4; } else sameNodeRetry = 0;
        } else if (rc == 2) {
            return 0;                                          // single-stage: nothing to pipeline → no-schedule sentinel (loop left un-pipelined)
        } else {                                               // rc == 1: FIFO passed
            // BarnaCore live-register-pressure gate (prolog + epilog windows):
            if (subtarget_is_barnacore) {
                BarnaCoreLiveRegPressure p0(MF, kernel, prolog, this[1192], ...);
                if (p0.s <= 32/this[1192] && p0.v <= 32/this[1192]) {
                    BarnaCoreLiveRegPressure p1(MF, kernel, epilog, this[1192], ...);
                    if (p1.s <= 8/this[1192] && p1.v <= 8/this[1192])
                        return this[944] | 0x100000000;         // ACCEPTED: pack II in low 32
                }
            } else return this[944] | 0x100000000;              // ACCEPTED
        }
    }
next_II:
    this[944] = ++II;                     // grow II and retry
    if (II >= upperArg) return 0;         // exhausted window → fail
}

要点如下：

搜索窗口是 [lowerII, upperII)，并且 II 从 max(lowerII, 1) 开始；(a4==0)+a4 惯用法保证 II >= 1。如果钳制后的窗口为空（lowerII >= upperII），搜索立即失败。
每个 II 都会重置预约表（hr->reset(); hr->setII(II)）后再调度，因此每个候选 II 的模列都从空开始。
无法在此 II 放置的节点会先重试（重排优先级），最多 MaxRetriesSameNode（swing-modulo-retry-same-node，默认 64）次；只有耗尽重试后，搜索才会放弃该 II 并递增。
返回值把已接受的 II 打包到低 32 位，并在 bit 32 放入 “found” 标志（II | 0x100000000）；0 表示窗口中没有可用 II。

Slack fallback（`findSchedule` @ `0x13c27560`）

slack 调度器在结构上相同，但基于 force：它把 upperII = min(upperII, lowerII + slack-modulo-limit-ii-range)（默认范围 256），并且不使用纯贪心 scheduleSU，而是使用 determineCriticalInstructions + forceScheduleSU + ejectInstruction（放置并回溯）。它的冲突检测显式体现模算术：identifySlotConflicts（0x13c25860）和 identifyResourceConflicts（0x13c26180）直接用 % *(_DWORD*)(dag + 0xd90) 计算 cycle mod II（slack 调度器把 II 存在 [dag+0xd90]）：

// TPUScheduleDAGSlackModulo::identifySlotConflicts (excerpt)  @ 0x13c25860
int II = *(int*)(dag + 0xd90);
v23 = (int)cycleA % II;                       // slot of candidate A
v24 = cycleB    % II;                          // slot of candidate B
conflict = (v23 != v24) ? ...                  // different columns may still alias under latency
         : ((cycleA + latency) % II != cycleB % II);
```text

---

## 步骤 3：模预约表（`ModuloHazardRecognizer`）

在周期 `c` 放置一个 op 的逐 II 合法性由**模预约表**决定：在周期 `c` 发射的 op，会在每次迭代的 `c mod II` 列占用同一个物理功能单元。两个映射到同一个 `(FU, c mod II)` 单元格的 op 构成结构 hazard；要么该 op 必须移动到列为空的周期，要么 II 必须增大。recognizer 在 `[hr+0x40]` 保存 II（由 `setII`，`0x13c14d00` 写入；`*((_DWORD*)this + 16) = II`），并把预约表保存为 `DenseMap<int /*slot*/, uint /*FU-bitmask*/>`。

```c
// ModuloHazardRecognizer::canEmitInstructionResourceInternal(SU, cycle, table)  @ 0x13c14d60
// returns 1 if the op can be emitted at `cycle` without an FU-column conflict, else 0.
char canEmit(SU *su, int cycle, DenseMap<int,uint> &reservation) {
    if (!su->schedClassDesc) return 1;                    // no resources → always legal
    int II = *((int*)this + 16);                          // [hr+0x40]
    MCWriteProcResEntry *e   = procResBegin(su);          // 6-byte records {idx, cycles}
    MCWriteProcResEntry *end = procResEnd(su);
    for (; e != end; ++e) {
        int FU      = e->ProcResourceIdx;                 // *e (the FU index, a byte)
        int cycles  = *((u16*)e + 1);                     // record +2: occupancy-cycle count
        if (II < cycles) continue;                        // skip if II < that same field (occupancy > II)
        int slot = cycle;
        do {
            uint booked = reservation.lookupOrInsert(slot).value;  // FU bitmask at this column
            if (_bittest(&booked, FU)) return 0;          // FU already booked in this column
            if (cycles == 0) break;
            slot = (slot + 1) % II;                       // advance one modulo column
        } while (slot != (cycle + cycles) % II);          // span the op's occupancy window
    }
    // fixed-latency structural-hazard variant repeats with getMaxSchedLatency window:
    if (su->mi->getDesc().SchedClass & 0x3F) {
        int maxLat = TPUSubtarget::getMaxSchedLatency(MF, su->latency);   // @ 0x13c5b420
        for (each proc-res entry; same modulo walk anchored at cycle + maxLat) { ... }
    }
    return 1;
}

反编译确认的字节精确机制如下：两个 (slot + 1) % v13 / % v22 归约中的除数是 *(_DWORD*)(a1 + 64) = [hr+0x40] = II；列索引 slot 初始化为 cycle（v30[0] = a3）并按 II 取模步进；FU 测试是对通过 DenseMap::lookupOrInsertIntoBucket 取得的逐 slot 位图执行 _bittest(&booked, *v10)；占用窗口在 (cycle + cycles) mod II 处终止。后半部分会以 cycle + getMaxSchedLatency(...) 为锚点重新运行同样的模步进，以捕捉固定延迟结构 hazard（伴随的 canEmitInstructionHazardInternal，0x13c14f80，对 hazard table 做等价处理）。emitInstructionResource（0x13c155a0）是在周期被接受后设置 FU bit 的提交动作。

这是教科书式的模预约表，也是每个 II 测试的核心：只有当 canEmitInstructionResourceInternal 对该 op 触及的每个模列都返回 1 时，scheduleSU 才会接受某个 SU 的周期。

完整的逐 II 有效性测试结合五个门，按顺序应用；第一个失败要么重新调度该节点，要么重试同一 II，要么增大 II：

门	函数	失败时
模预约（FU 列冲突）	`canEmitInstructionResourceInternal` @ `0x13c14d60`	重新放置节点；若没有周期可用，则重试/`++II`
Stage-0 可达性（每个 op 都适配一个 stage）	`checkForStageZeroInstructions` @ `0x13c14900`	`++II`
Stage 数 / split / 结构	`checkPostModuloSchedule` @ `0x13c149c0`	`rc=3` → `++II`；`rc=4` → split 重试
FIFO 深度未超限	`checkFifoOverflow` @ `0x13c0da00`（经验证器）	`++II`
Live-register 压力（prolog/epilog window）	`BarnaCoreLiveRegPressure`（内联在 `findSchedule` 中）	最多重试 64×，然后 `++II`

结构验证器：`checkPostModuloSchedule`（`0x13c149c0`）

当每个 SU 都已放置并物化出周期调度后，验证器判断该调度在此 II 上是否结构合法，而它的整数返回码驱动搜索。反编译很小且精确：

// TPUScheduleDAGModulo::checkPostModuloSchedule(MBB, schedule, ..., maxStages a8, splitOK a9, splitRetry a10)  @ 0x13c149c0
int checkPostModuloSchedule(...) {
    int stageCount = *((int*)this + 260);          // [dag+0x410] = ceil(span / II)
    if (stageCount == 1) return 2;                 // single stage → no overlap, trivially done
    if (stageCount <= maxStages) {
        long capStages = *((long*)this + 131);     // [dag+0x418] configured stage cap (-1 = none)
        if (capStages != -1 && capStages < stageCount) return 3;     // exceeds cap → ++II
        if (!EnableExperimentalCopyRotate /*224E42C8*/ && splitOK && EnableSplitLiveRanges /*224E3868*/
            && manualSplitLiveRange(this, MBB, ...)) {
            undoManualSplitLiveRange(this, MBB);
            return 3 + splitFlag;                  // 4 → retry with split live ranges
        }
        if (checkFifoOverflow(this, MBB, schedule)) {   // @ 0x13c0da00 — hardware FIFO depths
            undoManualSplitLiveRange(this, MBB);
            return 3;                              // FIFO overflow → ++II
        }
        return 1;                                  // FIFO OK → proceed to reg-pressure gate
    } else {                                       // stageCount > maxStages
        if (!subtarget_is_barnacore && !EnableRotatingPredicate /*224E1278*/)
            report_fatal_error("Max stage count too low.");   // needs more stages than allowed
        return 3;                                  // ++II
    }
}
```text

返回码及其在 `findSchedule` 中的效果：

| 代码 | 含义 | `findSchedule` 动作 |
|---|---|---|
| `1` | stage 数在界内，FIFO 检查通过 | 进入寄存器压力门；通过 → **接受 II** |
| `2` | 单 stage：没有可利用的跨迭代重叠 | `findSchedule` 返回 **no-schedule 哨兵**（`v18 = 0`，与窗口耗尽同值），循环保持未流水线化 |
| `3` | stage 数超过 `pipeliner-max-stages` 或 stage cap，或 FIFO 溢出 | 重置 same-node retry，**`++II`** |
| `4` | `manualSplitLiveRange` 成功：用 split live range 重试此 II | 将 II 减一，设置 split-retry 标志，重新尝试 |

`stageCount` 是 `[dag+0x410]` = `ceil(span / II)`，即 pipeline stage 数 = 稳态内核中飞行中的迭代数。`"Max stage count too low."` fatal 只在调度确实需要比 `pipeliner-max-stages` 允许更多的 stage，且在非 BarnaCore 代际上禁用了 rotating-predicate expansion（它可以在一个 body 中运行所有 stage 而无需 peeling）时触发。`checkFifoOverflow` 在每代硬件 FIFO（DRF / V2SF / SFRF / HMF）上构造 `FifoAnalysis`，并验证流水线化调度在重叠迭代之间从不超过任何 FIFO 深度。

返回 `1` 后，`findSchedule` 会运行内联的 `BarnaCoreLiveRegPressure` 门：它根据每类寄存器文件限制（prolog 为 `32 / lanes`，epilog 为 `8 / lanes`，其中 `lanes = this[1192]`），计算 prolog window 以及（若通过）epilog window 的 live scalar/vector 寄存器压力。只有两种压力都在预算内时，II 才会被接受（`return II | 0x100000000`）。

---

## 步骤 4：发射调度（`emitScheduleForLoop`，`0x13ba0ac0`）

有了已接受的 II 和 stage 分配后，`emitScheduleForLoop` 记录每个 MBB 的 II 和 stage 数，构建一个 `llvm::ModuloSchedule`（`{instruction order, per-instr cycle, per-instr stage}` 三元组），并分发到六个 expander 之一。反编译出的分发如下：

```c
// TPUMachinePipeliner::emitScheduleForLoop(MF, loop, dag, II, MBB)  @ 0x13ba0ac0
int stageCount = *((int*)dag + 260);           // [dag+0x410]
record_per_MBB_stageCount(MBB, stageCount);
record_per_MBB_II(MBB, II);                    // II stored for the super-pass map
ModuloSchedule sched = dag->createModuloSchedule(MF, loop, scheduleByCycle);   // vtable +0x20 → 0x13c045e0

byte *subtarget = MF->subtarget;
if (subtarget[290] == 1) {                      // BarnaCore: hardware-counted loop
    expandScheduleForBarnaCore(sched, this);    // @ 0x13c37bc0 — reorder kernel only, HW counter drives back-edge
} else if (EnableRotatingPredicate /*224E11C0*/ == 1
           && !flag_224E1278 && !flag_224E1108) {
    TPURotatingPredicateModuloExpander::expand(sched, II);   // @ 0x13bf1f00 — V5+ rotating predicates
} else {
    // peeling / predicated-epilogue / SSI / stitching expander (selected by PipelinerStrategy)
    ...
}

expander 选择是 hardware loop-counter 分类发挥作用的地方：

Expander	地址	何时	如何处理 II
`expandScheduleForBarnaCore`	`0x13c37bc0`	硬件计数的 BarnaCore 循环（`subtarget[290]==1`）	只重排 kernel；硅上 `bcLOOP` 计数器处理 prolog/epilog 边界，因此无需软件 peeling
`TPURotatingPredicateModuloExpander::expand`	`0x13bf1f00`	启用 `EnableRotatingPredicate` 的 V5+	用 rotating predicate 寄存器门控每个 stage 的 op，使所有 stage 在一个 body 中运行而无需展开；迭代 `i` 的 stage `k` 由 `ring[i-k]` 谓词化
`TPURotatingPredicateEmuModuloExpander::expand`	`0x13bf0c20`	缺少 predicate ring 的代际	用软件模拟 rotating ring
`TPUPredicatedEpilogModuloExpander::expand`	`0x13bd2860`	其他情况	peeling prolog + predicated epilog
`TPUSSIModuloExpander::expand`	`0x13bf5dc0`	单 stage interval 循环	LICM-hoisted prolog，speculative-code predication
`TPUPeelingModuloExpander`（基于通用 `PeelingModuloScheduleExpander` @ `0x190592a0`）	`0x13bc01c0`（markPrologEpilogs）	fallback	peeling `stageCount-1` 个 prolog 和 epilog 副本，留下 II 周期的稳态 kernel

扩展之后，emitScheduleForLoop 运行 optimizeScheduleLateSwap（0x13c0d1c0）、cleanupSideEffectMoves（0x13c0cee0）和 addBundleLimiters（0x13c0d540），然后把重写后的循环交给 bundle packer。

选定的 II 如何到达 bundle packer

模调度器产生一个周期调度：稳态内核的每个周期现在都持有一组应一起发射的 MI（可能来自不同迭代，按其 stage 偏移）。随后 bundle packer 使用同一 proc-resource 模型，把每个周期中调度的 MI 打包成合法 VLIW bundle。两个 pass 共享资源表，但在不同粒度上操作：模调度器保证横跨循环内核没有周期过度订阅某个功能单元（模预约表），packer 保证一个周期中的 op 符合每代 slot 限制。一个 worked example：某个 Viperfish 循环包含两个 matmul、两个 vector load、一个 loop-carried accumulate、一个 exp 和一个 store，其 ResMII = max(ceil(2/2 MXU), ceil(1/4 VALU), ceil(2/3 loads), ceil(1/2 XLU)) = 1，并且来自 accumulate 自环的 recurrence MII 为 2，因此 min-II = 2；II=2 时的预约表有两列，七个 op 分布在其中且没有 FU 冲突，验证器接受，所得 kernel 每两个周期运行一个迭代，并在 pipeline stage 之间隐藏 matmul 的长延迟。

配置旋钮

全部都是 LLVM cl::opt statics；值的 byte/word 位于 static_addr + 0x78。

`cl::opt`	Static addr	默认值	作用
`min-ii`（IILowerBound）	—	—	强制 lower II bound
(IIUpperBound)	`0x224e3178`	—	强制 upper II bound（存在时 `II = IIUpperBound + 1` cap）
`min-ii-slack`（MinIISlack）	`0x224e1370`	—	swing→slack fallback retry 的门
`slack-modulo-limit`	`0x224e3d00`	—	slack-scheduler 迭代上限
`slack-modulo-limit-ii-range`（LimitRangeII）	`0x224e3c48`	256	slack upper-II clamp = `lowerII + range`
`swing-modulo-limit`	`0x224e4098`	—	swing-scheduler 迭代上限
`swing-modulo-retry-same-node`（MaxRetriesSameNode）	`0x224e3fe0`	64	对单个节点在 `++II` 前的重排序重试次数
`pipeliner-max-stages`（MaxPipeliningStages）	`0x224e1428`	—	fatal / `++II` 之前允许的最大 pipeline stage 数
`tpu-use-swing-modulo-sched`（UseSwingModuloPipeliner）	`0x224e4198`	—	swing 与通用 `MachinePipeliner` 的选择
`tpu-pipeliner-strategy`（PipelinerStrategy）	`0x224e0fb0`	—	选择哪个 expander
`tpu-enable-pipeliner-super-pass`	`0x224e4530`	—	跨函数共享 II 发现
`EnableRotatingPredicate`	`0x224e1200`（flag word `0x224e1278`）	—	rotating-predicate expander 与 peeling 的选择
`TwistStageZeroOrdering`	`0x224e3f28`	—	hazard recognizer 中的 stage-0 op 排序
`EnableSplitLiveRanges`	`0x224e38f0`（flag `0x224e3868`）	—	启用 `manualSplitLiveRange`（验证器 `rc=4`）

搜索发出的诊断字符串：

字符串	地址	何时
`"Invalid Minimal Initiation Interval: 0"`	`0x9fd0b4c`	min-II 计算为 0
`"Minimal Initiation Interval too large: "`	`0xa27bd56`	min-II 超过上界
`"Schedule found with Initiation Interval: "`	`0xa265fcf`	成功，记录已接受的 II
`"Max stage count too low. ... -pipeliner-max-stages."`	`0x9fe03bb` / `0xa025008`	stage 数 > `pipeliner-max-stages` 且没有 rotating predicate
`"Use the tpu-specific swing-modulo scheduler instead of the MachinePipeliner."`	`0xa03a22b`	调度器选择

函数映射

函数	地址	身份
`TPUMachinePipeliner::runOnMachineFunction`	`0x13ba15e0`	pass driver；每个循环先 swing 后 slack
`TPUMachinePipeliner::emitScheduleForLoop`	`0x13ba0ac0`	构建 `ModuloSchedule`，分发 expander
`TPUMachinePipelinerSuperPass::runSuperPass`	`0x13ba6280`	跨函数共享 II 发现
`TPUScheduleDAGSwingModulo::initialize`	`0x13c36160`	min-II 组合
`TPUScheduleDAGSwingModulo::findSchedule`	`0x13c367c0`	II 递增循环
`TPUScheduleDAGSlackModulo::findSchedule`	`0x13c27560`	基于 force 的 fallback II 循环
`TPUScheduleDAGModulo::startModuloSchedule`	`0x13c041c0`	upper-II 经 `fastBundlePackingCost`
`TPUScheduleDAGModulo::calculateResourceMII`	`0x13c0bee0`	`ceil(FU-cycles / units)`
`TPUScheduleDAGModulo::calculateRecurrenceMII`	`0x13c0ccc0`	`Recurrence[+0x28]` 的最大值
`TPUScheduleDAGModulo::calculateFillResourceMII`	`0x13c0bb00`	FIFO-fill resource MII
`TPUScheduleDAGModulo::calculateLargestLatencyMII`	`0x13c0b840`	最长单边延迟
`TPUScheduleDAGModulo::getSuperPassMII`	`0x13c0ba40`	每 MBB super-pass II 查找
`TPUScheduleDAGModulo::findRecurrences`	`0x13c07ae0`	枚举依赖环
`TPUScheduleDAGModulo::computeMinDist`	`0x13c06ea0`	Bellman-Ford latency/distance
`ModuloHazardRecognizer::setII`	`0x13c14d00`	`[hr+0x40] = II`
`ModuloHazardRecognizer::canEmitInstructionResourceInternal`	`0x13c14d60`	`slot = cycle mod II` 预约测试
`ModuloHazardRecognizer::canEmitInstructionHazardInternal`	`0x13c14f80`	固定延迟 hazard 变体
`ModuloHazardRecognizer::emitInstructionResource`	`0x13c155a0`	提交 FU bit
`TPUScheduleDAGModulo::checkPostModuloSchedule`	`0x13c149c0`	结构验证器、返回码
`TPUScheduleDAGModulo::checkForStageZeroInstructions`	`0x13c14900`	每个 op 都到达有效 stage
`TPUScheduleDAGModulo::checkFifoOverflow`	`0x13c0da00`	硬件 FIFO 深度检查
`TPUScheduleDAGSlackModulo::identifySlotConflicts`	`0x13c25860`	`cycle mod II` slot hazard（slack）
`expandScheduleForBarnaCore`	`0x13c37bc0`	硬件计数循环 expander
`TPURotatingPredicateModuloExpander::expand`	`0x13bf1f00`	V5+ rotating-predicate expander
`TPUInstrInfo::analyzeLoopForTPUPipelining`	`0x13b804c0`	硬件与软件循环分类

交叉引用

LLO → Bundle Packing — 此调度器驱动的逐周期 VLIW packer；模内核的每个周期在那里变成一个已打包 bundle，并共享 proc-resource 模型。
LatencyHidingScheduler Core — HLO 级列表调度器；模调度器是其只针对循环的 LLVM 侧对应物，并运行在不同 IR 层级。
Bundle-Aware Cost — MII 计算器和预约表消耗的 MaxResourceCycles bundle 成本与 MCWriteProcResEntry proc-resource 周期。
Hardware Loop-Counter — 每代硬件与软件循环分类（analyzeLoopForTPUPipelining），它选择模 expander 并驱动回边。
Bundle Model — VLIW bundle 是什么、每代 slot 分类，以及 packer 对调度器产生的每个周期强制执行的 slot 限制。
二进制： extracted/libtpu-0.0.40-cp314-cp314-manylinux_2_31_x86_64/libtpu/libtpu.so（build-id 89edbbe81c5b328a958fe628a9f2207d）
索引项： Part VIII — Instruction Scheduling & Bundle Packing — 返回索引

Bundle 模调度 ​

摘要 ​

Pipeliner 所在位置：三个调度器，一个资源模型 ​

Recurrence MII — calculateRecurrenceMII（0x13c0ccc0） ​

Slack fallback（findSchedule @ 0x13c27560） ​

结构验证器：checkPostModuloSchedule（0x13c149c0） ​

选定的 II 如何到达 bundle packer ​

配置旋钮 ​

函数映射 ​

交叉引用 ​