跳转到正文
Retep's
返回

[TIL] IREE Dispatch 的创建过程

编辑文章

本文由英文原文翻译。代码、公式与技术名称保留原文。

IREE 的 dispatch-creation 阶段把张量计算划分成可以独立编译、调度的单元。关键是边界在哪里:哪些计算放在一起,哪些值跨边界传递,哪些生产者应复制到多个 dispatch。

1. 问题:如何切分张量图?

dispatch 是后续编译阶段可提取、为后端编译并调度的计算单位。

IREE 对图进行划分:操作是节点,张量依赖是边。将两个操作放进同一 dispatch,后续降级就有机会让中间计算保持局部;分开则必须通过接口传递结果。

目标相互竞争。更大分组可能减少中间物化和启动成本,但操作必须允许兼容分块、合法调度,后端也必须能在临时存储不过大的情况下完成降级。

贯穿本文的计算是:

A:    tensor<4x8xf32>
W:    tensor<16x8xf32>
bias: tensor<16xf32>

Y[m,n] = maximum(sum_k A[m,k] * W[n,k] + bias[n], 0)

初步逐元素融合后,相关图为:

flowchart LR
    A["A: 4 x 8"] --> M["M: matmul"]
    W["W: 16 x 8"] --> M
    E["E: empty"] --> F["F: zero fill"]
    Z["Z: zero"] --> F
    F --> M
    M --> G["G: bias + ReLU"]
    B["bias: 16"] --> G
    E --> G
    G --> R["result: 4 x 16"]

需要区分两种变换:

变换本例中的效果
逐元素融合broadcast、add、ReLU 合成一个名为 G 的 linalg.generic 体。
dispatch 分组matmul M 与 generic G 归入同一 dispatch,但仍是两个 Linalg 操作。

本文关注第二种。实现将规划与改写分开:先记录分组,再创建区域并移动操作。createFusionGroups 的开头明确体现这个顺序:

  // Step 1: Decide fusion groups (heuristic).
  FusionTracker tracker;
  decideFusableLinalgOps(funcOp.getFunctionBody(), dominanceInfo, options,
                         tracker);

2. 示例

为了分别观察两步融合,输入保留独立的 broadcast、add、ReLU generic。matmul 直接读取 W[n,k],在索引映射中表达转置访问,不额外创建 transpose。

// Y[m, n] = max(sum_k A[m, k] * W[n, k] + bias[n], 0).
// Start directly in IREE's tensor-level input IR to isolate dispatch creation.
module {
  util.func public @matmul_bias_relu(
      %a: tensor<4x8xf32>, %w: tensor<16x8xf32>,
      %bias: tensor<16xf32>) -> tensor<4x16xf32> {
    %zero = arith.constant 0.0 : f32
    %empty = tensor.empty() : tensor<4x16xf32>
    %init = linalg.fill ins(%zero : f32)
      outs(%empty : tensor<4x16xf32>) -> tensor<4x16xf32>
    %mm = linalg.matmul indexing_maps = [
      affine_map<(m, n, k) -> (m, k)>,
      affine_map<(m, n, k) -> (n, k)>,
      affine_map<(m, n, k) -> (m, n)>
    ] ins(%a, %w : tensor<4x8xf32>, tensor<16x8xf32>)
      outs(%init : tensor<4x16xf32>) -> tensor<4x16xf32>
    %broadcast = linalg.generic {
      indexing_maps = [affine_map<(m, n) -> (n)>,
                       affine_map<(m, n) -> (m, n)>],
      iterator_types = ["parallel", "parallel"]
    } ins(%bias : tensor<16xf32>) outs(%empty : tensor<4x16xf32>) {
    ^bb0(%b: f32, %unused: f32):
      linalg.yield %b : f32
    } -> tensor<4x16xf32>
    %sum = linalg.generic {
      indexing_maps = [affine_map<(m, n) -> (m, n)>,
                       affine_map<(m, n) -> (m, n)>,
                       affine_map<(m, n) -> (m, n)>],
      iterator_types = ["parallel", "parallel"]
    } ins(%mm, %broadcast : tensor<4x16xf32>, tensor<4x16xf32>)
      outs(%empty : tensor<4x16xf32>) {
    ^bb0(%x: f32, %b: f32, %unused: f32):
      %s = arith.addf %x, %b : f32
      linalg.yield %s : f32
    } -> tensor<4x16xf32>
    %result = linalg.generic {
      indexing_maps = [affine_map<(m, n) -> (m, n)>,
                       affine_map<(m, n) -> (m, n)>],
      iterator_types = ["parallel", "parallel"]
    } ins(%sum : tensor<4x16xf32>) outs(%empty : tensor<4x16xf32>) {
    ^bb0(%x: f32, %unused: f32):
      %r = arith.maximumf %x, %zero : f32
      linalg.yield %r : f32
    } -> tensor<4x16xf32>
    util.return %result : tensor<4x16xf32>
  }
}

第一个准备步骤合并三个逐元素操作。生成的 generic 使用 (m,n) -> (n) 读取 bias,并在同一区域包含两个标量操作:

%result = linalg.generic {
  indexing_maps = [
    affine_map<(m, n) -> (m, n)>,
    affine_map<(m, n) -> (n)>,
    affine_map<(m, n) -> (m, n)>
  ],
  iterator_types = ["parallel", "parallel"]
} ins(%mm, %bias : tensor<4x16xf32>, tensor<16xf32>)
  outs(%empty : tensor<4x16xf32>) {
^bb0(%x: f32, %b: f32, %unused: f32):
  %sum = arith.addf %x, %b : f32
  %relu = arith.maximumf %sum, %zero : f32
  linalg.yield %relu : f32
} -> tensor<4x16xf32>

全文沿用依赖图中的 E、Z、F、M、G。只有 M、G 执行主要张量计算,E、Z、F 准备目标张量和初始累加器。

3. 根操作

决定相邻操作能否加入之前,编译器需要起点。root 是融合组的锚点,提供参考计算和外层并行迭代空间,用来比较候选成员。

dispatch 分组的成员由约束最严格的成员决定。

matmul 的循环为 (m,n,k),m,n 并行,k 归约。后续若将输出 tile 分配到 workgroup,matmul 决定生成该 tile 所需的归约工作,bias 加法和 ReLU 则自然沿相同输出 tile 执行。

找到 root 后,以它创建 dispatch 分组:

  /// Create a new fusion group with `op` as the root.
  FusionGroup &createFusionGroup(MLIRContext *ctx, Operation *op) {
    fusionGroups.push_back(std::make_unique<FusionGroup>(op));
    opToGroup[op] = fusionGroups.back().get();
    return *fusionGroups.back();
  }

本例得到:

Group 0
  root: M
  members: {M}

追加消费者后,分组保存的 root 仍是 M。消费者可以成为下一步搜索节点,却不会替换组根。

如何找到根操作

候选首轮策略原因
matmul 等具名 Linalg 操作在未被先前规则排除时可选提供已识别的计算结构。
带归约循环的 generic除 unpack 生产者排除情形外可选提供归约结构。
全并行 generic G暂缓可成为邻居的 epilogue,之后也能创建后备分组。
Fill F排除初始化通过克隆处理。
类似位扩展的 generic排除合格实例稍后作为可克隆生产者处理。
已在 dispatch.workgroups 内的计算排除避免嵌套创建 dispatch。
static bool isRootLikeOp(Operation *op) {
  if (op->getParentOfType<IREE::Flow::DispatchWorkgroupsOp>()) {
    return false;
  }
  // Dequantization-like ops get cloned into dispatches later.
  if (IREE::LinalgExt::isBitExtendOp(op)) {
    return false;
  }
  // Any Linalg named op or generic op with reduction iterator types is a root
  // op.
  if (auto linalgOp = dyn_cast<linalg::LinalgOp>(op)) {
    if (isa<linalg::GenericOp>(op)) {
      return linalgOp.getNumReductionLoops() != 0 &&
             !hasFusableUnpackProducer(linalgOp);
    }
    return !isa<linalg::FillOp>(op);
  }
  if (isa<TilingInterface>(op)) {
    return !isa<IREE::LinalgExt::GatherOp, tensor::PadOp, tensor::ConcatOp,
                linalg::PackOp>(op);
  }
  return isa<linalg::UnPackOp>(op);
}

4. 上游搜索

root 确定后,要判断哪些周边计算能共用 dispatch。搜索分为两种:

两种搜索扩展同一个组,但并不对称:为 matmul 生成输入,与对其输出应用逐元素 epilogue,可能有不同调度与存储要求。

规划时还需要单一归属规则:一个原始操作只能属于一个已跟踪分组。加入第二组必须显式选择合并组或复制计算。

tracker 通过操作到组的映射执行这一规则:

// Membership storage in FusionTracker:
DenseMap<Operation *, FusionGroup *> opToGroup;

  void appendToFusionGroup(Operation *op, FusionGroup &fusionGroup) {
    assert(!isFusedOp(op) && "op already in a group");
    fusionGroup.insert(op);
    opToGroup[op] = &fusionGroup;
  }

  // Returns if `op` has been added to a FusionGroup in the tracker.
  bool isFusedOp(Operation *op) const { return opToGroup.contains(op); }

  // Returns if `op` is the root of a FusionGroup.
  bool isRootOp(Operation *op) const {
    return isFusedOp(op) && op == getFusionGroup(op).getRoot();
  }

上游搜索从 M 开始,检查定义各操作数的操作,接受合格生产者,再从它们继续 BFS。因为查找生产者,所以是向后工作列表遍历。

// Abbreviated traversal
SmallVector<Operation *> worklist;
worklist.push_back(root);
while (!worklist.empty()) {
  Operation *candidate = worklist.pop_back_val();
  for (OpOperand &operand : candidate->getOpOperands()) {
    Operation *producer = operand.get().getDefiningOp();
    if (!producer) continue;
    if (producer->getBlock() != root->getBlock()) continue;
    // ... ownership, edge-compatibility, and outside-user checks ...
    tracker.appendToFusionGroup(producer, fusionGroup);
    worklist.push_back(producer);
  }
}

检查分为三类:

检查目的
存在定义操作且位于同一 block确认支持范围内存在可移动生产者。
可克隆或已分组采用正确归属策略。
使用兼容性、多次使用策略、外部用户确保受支持并保持合法图边界。

M 的直接输入 %a、%w 是函数参数,累加器来自可克隆的 F,所以第一轮后分组仍为 {M}。

5. 目标传递风格(DPS)

操作既可以将值作为普通输入,也可以作为结果的初始目标。在围绕根迭代空间组合计算时,这种区别很重要。

目标传递风格显式表达第二种角色:操作接收与结果绑定的 init 操作数。张量语义下,每个 init 对应同类型且动态维度匹配的一个结果。之后缓冲区化有时可以为结果复用 init 的存储。

matmul 语法清楚体现了区别:

%mm = linalg.matmul
  ins(%a, %b : tensor<4x8xf32>, tensor<8x16xf32>)
  outs(%init : tensor<4x16xf32>) -> tensor<4x16xf32>

%a、%b 是 DPS 输入,%init 是 DPS init,其初始累加值参与数学计算:

mm[m,n] = init[m,n] + sum_k A[m,k] * B[k,n]

Init 侧生产者

init 侧生产者准备后续计算的目标,更容易融合。普通输入生产者可能要求不同 tile 域,或在主计算前引入临时存储,因此默认生产者融合路径对此较保守。

处理操作专用情形后,它要求:

  if (!isa<IREE::LinalgExt::LinalgFusionOpInterface>(consumer) ||
      !isa<IREE::LinalgExt::LinalgFusionOpInterface>(producer)) {
    return false;
  }

  if (!options.aggressiveFusion) {
    auto consumerFusionOp = dyn_cast<DestinationStyleOpInterface>(consumer);
    if (consumerFusionOp && !consumerFusionOp.isDpsInit(&operand)) {
      return false;
    }
  }

  if (!tracker.getFusionGroup(consumer).isFusable(producer)) {
    return false;
  }

  // Check operand limit before allowing fusion
  if (tracker.getFusionGroup(consumer).wouldExceedOperandLimit(producer)) {
    return false;
  }

  return true;
}

isDpsInit(&operand) 检查当前这条操作数边。非激进模式下,这条普通路径拒绝融合 DPS 消费者输入侧的生产者。

6. 克隆

某些生产者适合克隆,而非归属于一个组。分组归属适用于应只在选定 dispatch 中执行的实质计算;初始化、小常量和部分转换则更适合在每个使用它的 dispatch 内重建。

例如两个 matmul 共用一个 fill,强行将 fill 归入其中一组,会为另一组制造不必要接口。克隆让各 dispatch 独立初始化。原操作仍可供其他用户使用,直到清理时因无用而删除。

flowchart LR
    subgraph Before["Shared dependency"]
      F["Fill F"] --> M0["Matmul M0"]
      F --> M1["Matmul M1"]
    end
    subgraph D0["Dispatch 0"]
      F0["Cloned fill"] --> C0["M0"]
    end
    subgraph D1["Dispatch 1"]
      F1["Cloned fill"] --> C1["M1"]
    end

因此上游遍历故意跳过可克隆生产者:

if (IREE::Flow::isCloneableIntoDispatchOp(producer, cloneableOptions) ||
    tracker.isFusedOp(producer) || tracker.isRootOp(producer)) {
  continue;
}

各条件的含义如下:

条件当前遍历停止的原因
可克隆留给后续克隆策略,不立即分配原操作。
已融合已属于当前或其他组,不重复分配。
已是根在当前实现中已被 isFusedOp 覆盖,没有额外限制。

按前面的成员关系定义,最后一个条件确实冗余。它并非判断“适不适合作为根”,后者由 isRootLikeOp 查询。

克隆策略明确识别 fill 和 empty:

bool isCloneableIntoDispatchOp(Operation *op,
                               CloneableIntoDispatchOptions options) {
  if (isUncloneableOp(op)) {
    return false;
  }

  // TODO(#8637): `tensor.collapse_shape` and `tensor.expand_shape` are
  // trivially cloneable too, but they cause problems
  // with bufferization. Make them cloneable when fixed.
  if (isa<affine::AffineApplyOp, arith::IndexCastOp, linalg::FillOp,
          tensor::EmptyOp, tensor::ExtractOp, tensor::ExtractSliceOp,
          complex::CreateOp, IREE::Encoding::UnsetEncodingOp>(op)) {
    return true;
  }
  // ... other policy checks ...
  if (LinalgExt::isBitExtendOp(op)) {
    return true;
  }
  // ... remaining cases ...
}

dispatch 区域创建后,克隆辅助函数反复寻找合格生产者,并复制到区域内:

LogicalResult cloneProducersToRegion(RewriterBase &rewriter,
                                     IREE::Flow::DispatchRegionOp regionOp,
                                     CloneableIntoDispatchOptions options) {
  SmallVector<Operation *> cloneableOps;
  do {
    cloneableOps = getCloneableOps(regionOp, options);
    bool sortResult = mlir::computeTopologicalSorting(cloneableOps);
    (void)sortResult;
    assert(sortResult && "could not compute topological sorting");

    for (Operation *producer : llvm::reverse(cloneableOps)) {
      if (failed(clonePrecedingOpIntoDispatchRegion(rewriter, producer,
                                                    regionOp))) {
        return failure();
      }
    }
  } while (!cloneableOps.empty());

  return success();
}

本例中 F 在分组规划时被跳过,之后才复制进区域;其依赖 E、Z 也随之进入。因此,规划阶段跳过的生产者仍可能出现在最终 dispatch 体中。

7. 下游搜索

检查上游后,算法寻找消费分组结果的计算。对于 matmul,自然机会是逐输出元素执行的 epilogue,例如 bias 加法和 ReLU。

G 有两个并行维度 (m,n),读取 matmul 的一个结果,加上 bias[n],写出对应元素,可沿 matmul 输出域执行,无需新归约域。

普通消费者兼容路径检查全并行循环、兼容映射、接口和操作数数量要求:

  auto producerFusionOp =
      dyn_cast<IREE::LinalgExt::LinalgFusionOpInterface>(producer);
  auto consumerFusionOp =
      dyn_cast<IREE::LinalgExt::LinalgFusionOpInterface>(consumer);
  if (!producerFusionOp || !consumerFusionOp) {
    return false;
  }

  // Check that the consumer is all parallel.
  if (consumerFusionOp.getNumLoops() !=
      consumerFusionOp.getNumParallelLoops()) {
    return false;
  }

  if (!tracker.getFusionGroup(producer).isFusable(consumer)) {
    return false;
  }

  // Check operand limit before allowing fusion
  if (tracker.getFusionGroup(producer).wouldExceedOperandLimit(consumer)) {
    return false;
  }

搜索从各 root 开始,收集候选使用并按消费者分组。若同一消费者通过多个操作数读取生产者,每条相关边都必须兼容。接受后,消费者加入组并成为新的下游搜索节点。

核心循环直接实现该过程:

  for (Operation *root : roots) {
    SmallVector<Operation *> workList;
    FusionGroup &fusionGroup = tracker.getFusionGroup(root);
    workList.push_back(root);
    while (!workList.empty()) {
      Operation *currRoot = workList.pop_back_val();

      SmallVector<OpOperand *> fusableUses =
          getFusableUses(context, currRoot, dominanceInfo,
                         /*aggressiveFusion=*/options.aggressiveFusion);
      if (fusableUses.empty()) {
        continue;
      }

      // Group operands by owning consumer so the per-operand checks inside
      // `isFusableWithConsumer` are evaluated for every operand of a consumer.
      llvm::MapVector<Operation *, SmallVector<OpOperand *>> usesByConsumer;
      for (OpOperand *use : fusableUses) {
        usesByConsumer[use->getOwner()].push_back(use);
      }

      for (auto &[consumerOp, operands] : usesByConsumer) {
        if (tracker.isRootOp(consumerOp) || tracker.isFusedOp(consumerOp)) {
          continue;
        }

        // Ensure that fusing the consumer would not cause use-def violations.
        if (tracker.getFusionGroup(currRoot)
                .hasTransitiveDependencyOnFusionGroup(consumerOp,
                                                      dominanceInfo)) {
          continue;
        }

        if (!llvm::all_of(operands, [&](OpOperand *use) {
              return isFusableWithConsumer(*use, tracker, options);
            })) {
          continue;
        }
        tracker.appendToFusionGroup(consumerOp, fusionGroup);
        workList.push_back(consumerOp);
      }
    }
  }

虽然名为 currRoot,它只是当前搜索节点。将 G 加入工作列表,并不会把 FusionGroup::rootOp 从 M 改成 G。

非激进模式还要求只有一个不同的非 tensor.dim 消费者,限制向分叉图扩展的程度:

  // In non-aggressive mode, restrict fusion to producers whose results flow
  // to a single consumer. Count distinct consumers rather than operand uses
  // so that a single consumer reading multiple results from a multi-result
  // producer (e.g. OnlineAttentionOp) still qualifies.
  if (!aggressiveFusion) {
    llvm::SetVector<Operation *> consumers;
    for (Operation *user : op->getUsers()) {
      if (!isa<tensor::DimOp>(user)) {
        consumers.insert(user);
      }
    }
    if (consumers.size() != 1) {
      return {};
    }
  }

本例 matmul 只有 G 一个此类消费者,因此计划变为:

Group 0
  root: M
  members: {M, G}

注意与上游融合的不对称:G 将 matmul 结果作为普通输入,却仍可作为 epilogue 加入。消费者融合不重新应用 DPS-init 限制。

8. 分组必须保持合法图切分

局部兼容只是部分问题。dispatch 最终是带输入输出接口的独立调度单位,候选分组必须保持外围图的依赖顺序。

考虑向已有 M 的组添加 G:

flowchart LR
    M["M: inside group"] --> X["X: outside group"]
    X --> G["G: proposed member"]
    M --> G

直接边 M -> G 没问题,但若 X 留在组外,间接路径 M -> X -> G 就有问题:dispatch 需要 X 的结果作为输入,X 又需要该 dispatch 内的结果。只组合 {M,G} 会形成环。

消费者遍历在追加前拒绝这种情况:

if (tracker.getFusionGroup(currRoot)
        .hasTransitiveDependencyOnFusionGroup(consumerOp, dominanceInfo)) {
  continue;
}

辅助函数检查候选其他依赖的 backward slice。直接来自组内的操作数允许通过,检测的是经外部计算间接回到组内的路径。下面片段展示区别,省略了 slice 配置及全部操作数遍历:

    llvm::SetVector<Operation *> slice;
    auto populateSlice = [&](OpOperand *operand) {
      // It's okay if the consumer directly uses an operation in the fusion
      // group.
      if (loopMaps.contains(operand->get().getDefiningOp())) {
        return;
      }
      LogicalResult result = getBackwardSlice(operand->get(), &slice, options);
      assert(result.succeeded() && "expected a backward slice");
      (void)result;
    };

// ... visit all candidate operands and region captures ...
    return llvm::any_of(loopMaps.getArrayRef(),
                        [&](std::pair<Operation *, AffineMap> pair) {
                          return slice.contains(pair.first);
                        });

多个用户

共享生产者并非天然不能融合,它的结果可以作为 dispatch 输出供外部使用。但允许多次使用,并不代表所有放置都合法。

生产者遍历分别检查三项:

  1. 进入当前组的所有使用都兼容。
  2. 配置的多次使用策略允许该生产者。
  3. 外部用户不会阻止将计算移动到 dispatch。

第一个辅助函数故意忽略组外使用:

static bool areAllFusionGroupUsesFusableWithProducer(
    Operation *producer, const FusionGroup &fusionGroup,
    const FusionTracker &tracker, FormDispatchRegionsPassOptions const &options,
    bool fuseWithTruncate) {
  return llvm::all_of(producer->getUses(), [&](OpOperand &use) {
    Operation *useOwner = use.getOwner();
    Operation *useOwnerAtProducerLevel =
        producer->getBlock()->findAncestorOpInBlock(*useOwner);
    if (!useOwnerAtProducerLevel ||
        !fusionGroup.contains(useOwnerAtProducerLevel)) {
      return true;
    }
    return useOwnerAtProducerLevel == useOwner &&
           isFusableWithProducer(use, tracker, options, fuseWithTruncate);
  });

组外使用交给后续 hasExternalUserBlockingProducerFusion,它考虑 root 之前的外部用户、现有 dispatch 区域和候选组依赖。

计数也有区别:禁用多次使用生产者融合时,生产者路径统计非 tensor.dim 的操作数使用次数;非激进消费者路径统计不同的消费者操作数目。一个消费者两次读取同一值,可以通过后者却不满足前者。

兼容的迭代几何

成员迭代空间还必须能映射到根的外层并行维度。对于 matmul,初始映射可以写为:

root parallel coordinates: (m,n)
matmul iteration space:    (m,n,k)
mapping:                  (m,n) -> (m,n,0)

0 表示该维没有对应的 root 并行坐标,并非把归约索引固定为零。全并行 epilogue 的映射则是 (m,n) -> (m,n)。

兼容性要求映射无歧义。若候选不完全是外层并行,还会比较其映射与根映射。某些嵌套区域对组内值的隐式使用也会被拒绝,因为该算法支持的是经操作数边融合。映射部分如下:

    FailureOr<AffineMap> maybeMap = getRootParallelLoopToOpMap(op);
    if (failed(maybeMap)) {
      return false;
    }

    // If the candidate is not all parallel, then its loop configuration should
    // be the same as the root.
    auto candidateOuterParallelLoop = getOuterParallelLoops(op);
    if (candidateOuterParallelLoop.size() !=
        candidateOuterParallelLoop.count()) {
      return loopMaps.lookup(rootOp) == maybeMap.value();
    }
    return true;

汇总上游策略

上游遍历依次判断:是否存在受支持依赖边,是否符合归属与克隆策略,组内每次使用是否兼容,外部用户是否阻止融合。全部通过后才分配生产者并继续上游搜索。完整辅助函数如下:

/// Starting from the `root` op, traverse the operand use-def chain
/// in reverse to fuse with producers.
static void
fuseRootsWithProducers(MLIRContext *context, Operation *root,
                       FusionGroup &fusionGroup,
                       FormDispatchRegionsPassOptions const &options,
                       FusionTracker &tracker, bool fuseWithTruncate) {
  SmallVector<Operation *> worklist;
  worklist.push_back(root);
  IREE::Flow::CloneableIntoDispatchOptions cloneableOptions;
  cloneableOptions.aggressive = options.aggressiveFusion;
  while (!worklist.empty()) {
    Operation *candidate = worklist.pop_back_val();
    for (OpOperand &operand : candidate->getOpOperands()) {
      Operation *producer = operand.get().getDefiningOp();
      if (!producer) {
        continue;
      }
      // Only fuse producers in the same block as the root. Cross-block
      // fusion (e.g., producer at function scope, root inside scf.if)
      // would create dispatch results that don't dominate external uses.
      if (producer->getBlock() != root->getBlock()) {
        continue;
      }
      if (IREE::Flow::isCloneableIntoDispatchOp(producer, cloneableOptions) ||
          tracker.isFusedOp(producer) || tracker.isRootOp(producer)) {
        continue;
      }

      if (!areAllFusionGroupUsesFusableWithProducer(
              producer, fusionGroup, tracker, options, fuseWithTruncate)) {
        continue;
      }

      if (!options.fuseMultiUseProducers &&
          llvm::count_if(producer->getUses(), [](OpOperand &use) {
            return !isa<tensor::DimOp>(use.getOwner());
          }) != 1) {
        continue;
      }

      if (IREE::Flow::hasExternalUserBlockingProducerFusion(
              root, producer, fusionGroup.getFusedOperations())) {
        continue;
      }

      tracker.appendToFusionGroup(producer, fusionGroup);
      worklist.push_back(producer);
    }
  }
}

9. 搜索顺序

两个潜在分组可能同时需要同一操作。由于原操作只能分配一个组,搜索顺序就成为策略的一部分。

最明显的例子是精度缩窄:归约输出 f32,逐元素操作将其缩为 bf16,再由 scatter 消费:

P: reduction(f32) -> T: narrow(f32 to bf16) -> C: scatter

兼容时 {P,T} 和 {T,C} 都可能有用。将 T 与 P 放一起,可以让更窄的中间结果跨边界到 C,降低传输成本;若 C 立刻占有 T,P 就失去机会。

因此,初次上游搜索暂缓缩窄生产者,先执行消费者融合,再允许缩窄重试上游。这就是 fuseWithTruncate 参数和两次上游搜索的原因。

  if (!fuseWithTruncate && IREE::LinalgExt::isBitTruncateOp(producer)) {
    return false;
  }

扫描反向进行,所以可能先遇到 C,再遇到 P:

步骤效果
创建 C 的组fuseWithTruncate=false,暂缓 T。
创建 P 的组P 保留为上游锚点。
按程序顺序融合消费者P 有机会吸收 T。
允许缩窄并重试生产者融合若 T 尚未分配,C 可在通过其他检查后吸收它。

因此先执行禁止缩窄融合的反向扫描,再正向扫描,最后执行允许缩窄的重试。

  for (Block &block : region) {
  SmallVector<Operation *> roots;
    for (Operation &op : llvm::reverse(block)) {
      if (isa<scf::SCFDialect>(op.getDialect())) {
        for (auto &region : op.getRegions()) {
          decideFusableLinalgOps(region, dominanceInfo, options, tracker,
                                 numRootOps);
        }
        continue;
      }

      // Start with a root operation and fuse its producers.
      if (tracker.isFusedOp(&op) || !isRootLikeOp(&op)) {
        continue;
      }
      FusionGroup &newGroup = tracker.createFusionGroup(context, &op);
      fuseRootsWithProducers(context, &op, newGroup, options, tracker,
                             /*fuseWithTruncate=*/false);
      roots.push_back(&op);
    }
    roots = llvm::to_vector(llvm::reverse(roots));
    fuseRootsWithConsumers(context, roots, dominanceInfo, options, tracker);
    for (Operation *root : roots) {
      FusionGroup &fusionGroup = tracker.getFusionGroup(root);
      fuseRootsWithProducers(context, root, fusionGroup, options, tracker,
                             /*fuseWithTruncate=*/true);
    }
  }

反向扫描让靠后的 root 优先占有合格上游工作。之后翻转 roots,让下游搜索按 block 中程序顺序运行,使上游根在重试前有机会吸收缩窄消费者。

还有后备扫描:优先 root 无法覆盖全部图。函数如果只有独立逐元素 generic,没有 matmul 或归约可加入,仍需自己的 dispatch。后备扫描为剩余合格 Linalg、padding、packing 创建组,再应用相同的生产者、消费者、重试流程,排除已分组和可克隆操作。

    for (Operation &op : llvm::reverse(block)) {
      // If it is part of a fusion group or root op, ignore it.
      if (tracker.isFusedOp(&op) || tracker.isRootOp(&op)) {
        continue;
      }
      // Only look for Linalg ops here. Avoid moving `linalg.fill` that aren't
      // fused with anything else into their own dispatches since it is better
      // to convert them to splats. Also avoid moving dequantization-like ops
      // into their own dispatch since it is better to clone these ops and avoid
      // materializing large tensors between dispatches.
      if (!isa<linalg::LinalgOp, tensor::PadOp, linalg::PackOp>(op) ||
          IREE::Flow::isCloneableIntoDispatchOp(&op, cloneableOptions)) {
        continue;
      }
      // ... special gather-like exclusion, then create the group ...
    }

10. 物化为区域

分组完成后,编译器物化选定的图切分。初始表示刻意保持轻量:flow.dispatch.region 可以隐式捕获外部 SSA 值,便于移动操作并完善分组。

本例完整过程为:

阶段分组计划或区域内容
选择 M根 M,成员 {M}。
检查生产者F 留待克隆,函数参数终止其余路径。
添加 epilogue G根 M,成员 {M,G}。
后备扫描不需要额外计算分组。
创建区域将 M、G 移入同一区域,最初捕获 F。
克隆合格生产者将 F、E、Z 带入区域。
转换为 workgroups用显式输入输出接口替换捕获。

调用方围绕根创建区域,再按拓扑顺序移动其他组内操作。创建步骤为:

    // Create fusion group.
    IREE::Flow::DispatchRegionOp regionOp;
    auto maybeRegionOp = IREE::Flow::wrapOpInDispatchRegion(rewriter, root);
    if (failed(maybeRegionOp)) {
      return root->emitOpError("failed to move root into dispatch");
    }
    regionOp = *maybeRegionOp;

克隆初始化后,结构大致为:

// Schematic: types and indexing maps are omitted here.
%result = flow.dispatch.region -> (tensor<4x16xf32>) {
  %empty = tensor.empty() : tensor<4x16xf32>
  %zero = arith.constant 0.0 : f32
  %init = linalg.fill ...
  %mm = linalg.matmul ...
  %relu = linalg.generic ...  // bias + ReLU
  flow.return %relu : tensor<4x16xf32>
}

收尾

到这里,IREE dispatch 创建流水线的源码导读就完成了!


编辑文章
分享文章:

下一篇
[TIL] 优化 Paged Attention